Project Euler #59 XOR decryption - Java

import java.util.Scanner;

public class Solution {

    private static boolean[] FIRST = new boolean['z' - 'a' + 1];
    private static boolean[] SECOND = new boolean['z' - 'a' + 1];
    private static boolean[] THIRD = new boolean['z' - 'a' + 1];

    public static void main(String[] args) {
        for (int i = 0; i < 'z' - 'a' + 1; i++) {
            FIRST[i] = true;
            SECOND[i] = true;
            THIRD[i] = true;
        }
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        for (int i = 0; i < N / 3; i++) {
            int i1 = scanner.nextInt();
            for (char c = 'a'; c <= 'z'; c++) {
                if (!FIRST[c - 'a']) {
                    continue;
                }
                if (!isValid(c, i1)) {
                    FIRST[c - 'a'] = false;
                }
            }
            int i2 = scanner.nextInt();
            for (char c = 'a'; c <= 'z'; c++) {
                if (!SECOND[c - 'a']) {
                    continue;
                }
                if (!isValid(c, i2)) {
                    SECOND[c - 'a'] = false;
                }
            }
            int i3 = scanner.nextInt();
            for (char c = 'a'; c <= 'z'; c++) {
                if (!THIRD[c - 'a']) {
                    continue;
                }
                if (!isValid(c, i3)) {
                    THIRD[c - 'a'] = false;
                }
            }
        }
        scanner.close();
        StringBuilder sb = new StringBuilder();
        for (char c = 'a'; c <= 'z'; c++) {
            if (FIRST[c - 'a']) {
                sb.append(c);
            }
        }
        for (char c = 'a'; c <= 'z'; c++) {
            if (SECOND[c - 'a']) {
                sb.append(c);
            }
        }
        for (char c = 'a'; c <= 'z'; c++) {
            if (THIRD[c - 'a']) {
                sb.append(c);
            }
        }
        System.out.println(sb.toString());
    }

    private static boolean isValid(char c, int i) {
        int xor = (c ^ i);
        if ((xor >= 'a' && xor <= 'z') || (xor >= 'A' && xor <= 'Z') || (xor >= '0' && xor <= '9')
                || (xor == '(' || xor == ')') || (xor == ';' || xor == ':') || (xor == ',' || xor == '.')
                || (xor == '\'' || xor == '?') || (xor == '-' || xor == '!' || xor == ' ')) {
            return true;
        }
        return false;
    }
}

Project Euler #58 Spiral primes - Java

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        if (n < 8 || n > 60) {
            throw new IllegalArgumentException("Invalid percenrage");
        }
        getAnswer(n);
    }

    private static void getAnswer(int n) {
        long primeCount = 0;
        long totalCount = 1;
        long n1 = 1;
        long gap = 2;
        for (int shell = 1;; shell++) {
            // update total count
            totalCount += 4;
            // update primeCount
            for (int i = 0; i < 4; i++) {
                n1 += gap;
                if (isPrime(n1)) {
                    primeCount++;
                }
            }
            gap += 2;
            // System.out.println((double) primeCount / totalCount + " total:" + totalCount);
            double percentage = (primeCount * 100) / totalCount;
            if (percentage < n) {
                System.out.println(2 * shell + 1);
                return;
            }
        }
    }

    private static boolean isPrime(long n) {
        if (n <= 1 || n == 4) {
            return false;
        }
        if (n <= 3) {
            return true;
        }
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static boolean isPrime(long n, int k) {
        if (n <= 1 || n == 4) {
            return false;
        }
        if (n <= 3) {
            return true;
        }
        long d = n - 1;
        while (d % 2 == 0) {
            d /= 2;
        }
        for (int i = 0; i < k; i++) {
            if (miillerTest(d, n) == false) {
                return false;
            }
        }
        return true;
    }

    private static boolean miillerTest(long dl, long n) {
        long al = (long) (2 + (Math.random() % (n - 4)));
        BigInteger a = BigInteger.valueOf(al);
        BigInteger nMinusOne = BigInteger.valueOf(n - 1);
        BigInteger x = a.modPow(BigInteger.valueOf(dl), BigInteger.valueOf(n));
        if (x.equals(BigInteger.ONE) || x.equals(nMinusOne)) {
            return true;
        }
        BigInteger d = BigInteger.valueOf(dl);
        while (!d.equals(nMinusOne)) {
            x = x.multiply(x);
            x = x.mod(BigInteger.valueOf(n));
            d = d.multiply(BigInteger.valueOf(2l));
            if (x.equals(BigInteger.ONE)) {
                return false;
            }
            if (x.equals(nMinusOne)) {
                return true;
            }
        }
        return false;
    }

}

Project Euler #57 Square root convergents - Java

Fast log10 calculation of BigInteger was borrowed from here

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        getAnswer(n);
    }

    private static void getAnswer(int n) {
        BigInteger numerator = BigInteger.valueOf(3);
        BigInteger denominator = BigInteger.valueOf(2);
        for (int i = 0; i < n; i++) {
            // if (numerator.toString().length() > denominator.toString().length()) {
            if (log10(numerator) > log10(denominator)) {
                System.out.println((i + 1));
            }
            BigInteger newDenominator = numerator.add(denominator);
            BigInteger newNumerator = newDenominator.add(denominator);
            numerator = newNumerator;
            denominator = newDenominator;
        }
    }

    private static int log10(BigInteger huge) {
        int digits = 0;
        int bits = huge.bitLength();
        // Serious reductions.
        while (bits > 4) {
            // 4 > log[2](10) so we should not reduce it too far.
            int reduce = bits / 4;
            // Divide by 10^reduce
            huge = huge.divide(BigInteger.TEN.pow(reduce));
            // Removed that many decimal digits.
            digits += reduce;
            // Recalculate bitLength
            bits = huge.bitLength();
        }
        // Now 4 bits or less - add 1 if necessary.
        if (huge.intValue() > 9) {
            digits += 1;
        }
        return digits;
    }
}

Project Euler #56 Powerful digit sum - Java

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        int ret = getAnswer(n);
        System.out.println(ret);
    }

    private static int getAnswer(int n) {
        int ret = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 2; i--) {
            for (int j = n - 1; j >= 2; j--) {
                int base = i;
                BigInteger bi = BigInteger.valueOf(base);
                String str = bi.pow(j).toString();
                char[] cs = str.toCharArray();
                int count = 0;
                for (int k = 0; k < str.length(); k++) {
                    count += cs[k] - '0';
                }
                if (count > ret) {
                    ret = count;
                }
            }
        }
        return ret;
    }
}

Project Euler #55 Lychrel numbers - Java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        HashMap<BigInteger, Integer> answer = new HashMap<BigInteger, Integer>();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        for (int i = 1; i <= n; i++) {
            BigInteger cur = BigInteger.valueOf(i);
            for (int j = 0; j < 60; j++) {
                if (isPanlindrome(cur)) {
                    if (answer.containsKey(cur)) {
                        int count = answer.get(cur);
                        answer.put(cur, count + 1);
                    } else {
                        answer.put(cur, 1);
                    }
                    break;
                }
                cur = cur.add(getReverse(cur));
            }
        }
        int max = Integer.MIN_VALUE;
        BigInteger maxi = BigInteger.ZERO;
        for (BigInteger bi : answer.keySet()) {
            int ans = answer.get(bi);
            if (ans > max) {
                max = ans;
                maxi = bi;
            }
        }
        System.out.println(maxi + " " + max);
    }

    private static BigInteger getReverse(BigInteger n) {
        String ns = String.valueOf(n);
        StringBuilder sb = new StringBuilder(ns);
        return new BigInteger(sb.reverse().toString());
    }

    private static boolean isPanlindrome(BigInteger n) {
        if (n.compareTo(BigInteger.TEN) < 0) {
            return true;
        }
        String ns = String.valueOf(n);
        char[] nsc = ns.toCharArray();
        int start = 0;
        int end = ns.length() - 1;
        while (start < end) {
            if (nsc[start++] != nsc[end--]) {
                return false;
            }
        }
        return true;
    }
}

Project Euler #54 Poker hands - Java

For this particular problem, I borrowed scoring scheme from nayuki.io (https://github.com/nayuki/Project-Euler-solutions/blob/master/java/p054.java)

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

    public enum LEVEL {
        TWO(1), THREE(2), FOUR(3), FIVE(4), SIX(5), SEVEN(6), EIGHT(7), NINE(8), TEN(9), JACK(10), QUEEN(11), KING(12), ACE(13);

        private final int level;

        private LEVEL(int level) {
            this.level = level;
        }
    }

    public enum TYPE {
        CLOVER(1), HEART(2), DIAMOND(3), SPADE(4);

        private final int level;

        private TYPE(int level) {
            this.level = level;
        }
    }

    private static class Card {

        public LEVEL mLevel;
        public TYPE mType;

        public Card(LEVEL level, TYPE type) {
            mLevel = level;
            mType = type;
        }
    }

    private static class Player {

        private ArrayList<Card> mInHands = new ArrayList<Card>();

        private boolean mIsFlush = false;
        private boolean mIsRoyal = false;

        public void addCard(Card card) {
            mInHands.add(card);
        }

        /**
         * Borrowed idea from Nayuki.io
         * https://github.com/nayuki/Project-Euler-solutions/blob/master/java/p054.java
         */
        public int checkPower() {
            int[] countByCard = new int[13];
            mIsFlush = true;
            TYPE flushCheck = mInHands.get(0).mType;
            for (Card card : mInHands) {
                countByCard[card.mLevel.level - 1]++;
                if (card.mType != flushCheck) {
                    mIsFlush = false;
                }
            }
            int[] countByLevel = new int[6];
            for (int count : countByCard) {
                countByLevel[count]++;
            }
            int bestCards = get5FrequentHighestCards(countByCard, countByLevel);
            int straightHighRank = getStraightHighRank(countByCard);
            mIsRoyal = (countByCard[12] != 0) && (countByCard[11] != 0) && (countByCard[10] != 0) && (countByCard[9] != 0) && (countByCard[8] != 0);

            if (mIsFlush && mIsRoyal)
                return 9 << 20 | bestCards; // Royal flush
            else if (straightHighRank != -1 && mIsFlush)
                return 8 << 20 | straightHighRank; // Straight flush
            else if (countByLevel[4] == 1)
                return 7 << 20 | bestCards; // Four of a kind
            else if (countByLevel[3] == 1 && countByLevel[2] == 1)
                return 6 << 20 | bestCards; // Full house
            else if (mIsFlush)
                return 5 << 20 | bestCards; // Flush
            else if (straightHighRank != -1)
                return 4 << 20 | straightHighRank; // Straight
            else if (countByLevel[3] == 1)
                return 3 << 20 | bestCards; // Three of a kind
            else if (countByLevel[2] == 2)
                return 2 << 20 | bestCards; // Two pairs
            else if (countByLevel[2] == 1)
                return 1 << 20 | bestCards; // One pair
            else
                return 0 << 20 | bestCards;
        }

        private static int get5FrequentHighestCards(int[] ranks, int[] ranksHist) {
            int result = 0;
            int count = 0;
            for (int i = ranksHist.length - 1; i >= 0; i--) {
                for (int j = ranks.length - 1; j >= 0; j--) {
                    if (ranks[j] == i) {
                        for (int k = 0; k < i && count < 5; k++, count++)
                            result = result << 4 | j;
                    }
                }
            }
            return result;
        }

        private static int getStraightHighRank(int[] ranks) {
            outer: for (int i = ranks.length - 1; i >= 3; i--) {
                for (int j = 0; j < 5; j++) {
                    if (ranks[(i - j + 13) % 13] == 0)
                        continue outer; // Current offset is not a straight
                }
                return i; // Straight found
            }
            return -1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            Player p1 = new Player();
            for (int i = 0; i < 5; i++) {
                String input = scanner.next();
                TYPE type = getType(input);
                LEVEL level = getLevel(input);
                Card card = new Card(level, type);
                p1.addCard(card);
            }
            Player p2 = new Player();
            for (int i = 0; i < 5; i++) {
                String input = scanner.next();
                TYPE type = getType(input);
                LEVEL level = getLevel(input);
                Card card = new Card(level, type);
                p2.addCard(card);
            }
            if (p1.checkPower() < p2.checkPower()) {
                System.out.println("Player 2");
            } else {
                System.out.println("Player 1");
            }
        }
        scanner.close();
    }

    private static TYPE getType(String input) {
        TYPE type;
        char c = input.charAt(1);
        switch (c) {
            case 'S':
            case 's':
                type = TYPE.SPADE;
                break;
            case 'D':
            case 'd':
                type = TYPE.DIAMOND;
                break;
            case 'H':
            case 'h':
                type = TYPE.HEART;
                break;
            case 'C':
            case 'c':
            default:
                type = TYPE.CLOVER;
                break;
        }
        return type;
    }

    private static LEVEL getLevel(String input) {
        LEVEL level;
        char lc = input.charAt(0);
        switch (lc) {
            case '2':
                level = LEVEL.TWO;
                break;
            case '3':
                level = LEVEL.THREE;
                break;
            case '4':
                level = LEVEL.FOUR;
                break;
            case '5':
                level = LEVEL.FIVE;
                break;
            case '6':
                level = LEVEL.SIX;
                break;
            case '7':
                level = LEVEL.SEVEN;
                break;
            case '8':
                level = LEVEL.EIGHT;
                break;
            case '9':
                level = LEVEL.NINE;
                break;
            case 'T':
            case 't':
                level = LEVEL.TEN;
                break;
            case 'J':
            case 'j':
                level = LEVEL.JACK;
                break;
            case 'Q':
            case 'q':
                level = LEVEL.QUEEN;
                break;
            case 'K':
            case 'k':
                level = LEVEL.KING;
                break;
            case 'A':
            case 'a':
            default:
                level = LEVEL.ACE;
                break;
        }
        return level;
    }
}