Project Euler: Problem 52 – Permuted multiples

Problem 52:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
 
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Idea:

I felt like being lazy for this one, partly because the method I had in mind would fail quickly for each incorrect answer, and partly because I already have a method to see if a number is a permutation thanks in part to Problem 24. I just did what the problem said:
 
Pick a number, multiply it by 2, see if it’s a permutation. If not, continue to the next number, otherwise, repeat with 3x, 4x, 5x, and 6x.

int answer = -1;

boolean found = false;

int number = 1;
while(!found) {
   if(EulerUtils.Permutation.isPermutation(number, number*2)) {
      if(EulerUtils.Permutation.isPermutation(number, number*3)) {
         if(EulerUtils.Permutation.isPermutation(number, number*4)) {
            if(EulerUtils.Permutation.isPermutation(number, number*5)) {
               if(EulerUtils.Permutation.isPermutation(number, number*6)) {
                  found = true;
                  answer = number;
               }
            }
         }
      }
   }
   number++;
}

Project Euler: Problem 53 – Combinatoric selections

Problem 53:

There are exactly ten ways of selecting three from five, 12345:
 
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
 
In combinatorics, we use the notation, 5C3 = 10.
 
In general,

nCr =
n!
r!(n-r)!
,where r <= nn! = nx(n-1)x…x3x2x1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
 
How many, not necessarily distinct, values of  nCr, for 1 <= n <= 100, are greater than one-million?

Idea:

I recognized this as another repeat of Binomial Coefficients as seen in Problem 15. I just needed to plug in the numbers in a nested loop and count how many times the answer was greater than 1 million.

int answer = 0;

final BigInteger ONE_MILLION = BigInteger.valueOf(1000000);

for(int n = 1; n <= 100; n++) {
   for(int r = 1; r <= n; r++) {
      if(ONE_MILLION.compareTo(EulerUtils.nChooseM(n, r)) < 0) {
         answer++;
      }
   }
}

Project Euler: Problem 54 – Poker hands

Problem 54:

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

  • High Card: Highest value card.
  • One Pair: Two cards of the same value.
  • Two Pairs: Two different pairs.
  • Three of a Kind: Three cards of the same value.
  • Straight: All cards are consecutive values.
  • Flush: All cards of the same suit.
  • Full House: Three of a kind and a pair.
  • Four of a Kind: Four cards of the same value.
  • Straight Flush: All cards are consecutive values of same suit.
  • Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.
 
If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.
 
Consider the following five hands dealt to two players:

Hand Player 1 Player 2 Winner
1 5H 5C 6S 7S KD

Pair of Fives
2C 3S 8S 8D TD

Pair of Eights
Player 2
2 5D 8C 9S JS AC

Highest card Ace
2C 5C 7D 8S QH

Highest card Queen
Player 1
3 2D 9C AS AH AC

Three Aces
3D 6D 7D TD QD

Flush with Diamonds
Player 2
4 4D 6S 9H QH QC

Pair of Queens
Highest card Nine
3D 6D 7H QD QS

Pair of Queens
Highest card Seven
Player 1
5 2H 2D 4C 4D 4S

Full House
With Three Fours
3C 3D 3S 9S 9D

Full House
with Three Threes
Player 1

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1’s cards and the last five are Player 2’s cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player’s hand is in no specific order, and in each hand there is a clear winner.
 
How many hands does Player 1 win?

Idea:

This problem was probably easier than it should’ve been for me, given my experience with Poker Hands in my Texas Hold’em senior capstone project at PLU.
 
I started off creating a Poker class that contained an enum of the Suits and HandRanks, a subclass of Poker called Hand that represents a poker hand, and a subclass of Poker called Card that represents individual cards. I made both the Card and Hand comparable so I could easily determine which cards were superior to which, and subsequently which hands were superior to which.
 
The compareTo method for the Hand class was a bit more involved since I had to determine what type of hand it was, but also in the event of a tie, who won based on higher card values.
 
Once I got that set up, just read the text file of hands, and compare them to each other, counting how many times Player 1 won.

int answer = 0;

try {
   BufferedReader in = new BufferedReader(new FileReader("Problem_54.txt"));
   String line = in.readLine();
   while(line != null) {
      String hand1 = line.substring(0, 14);
      EulerUtils.Poker.Hand player1 = new EulerUtils.Poker.Hand(hand1);
      String hand2 = line.substring(15);
      EulerUtils.Poker.Hand player2 = new EulerUtils.Poker.Hand(hand2);

      if(player1.compareTo(player2) > 0) {
         answer++;
      }
      line = in.readLine();
   }
   in.close();
} catch (IOException e) {
   e.printStackTrace();
}

Project Euler: Problem 55 – Lychrel numbers

Problem 55:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
 
Not all numbers produce palindromes so quickly. For example,
 
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
 
That is, 349 took three iterations to arrive at a palindrome.
 
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
 
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
 
How many Lychrel numbers are there below ten-thousand?
 
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

Idea:

This is a pretty straight forward problem: reverse the number via method of choice, add it to the original number, check to see if it’s a palindrome, and repeat up to 49 more times if it’s not.
 
Since I already have a palindrome method from Problem 4, the only hurdle is reversing the number. I chose to convert it to a string and reverse it that way since I’m using BigIntegers (never can be too careful with these problems). Once I made the “isLychrel(int)” method, I was practically done.

int answer = 0;

for(int i = 1; i < 10000; i++) {
   if(EulerUtils.isLychrel(i)) {
      answer++;
   }
}

Project Euler: Problem 56 – Powerful digit sum

Problem 56:

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
 
Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

Idea:

I was wondering how long it was going to be until googol came up in a problem (although I was part expecting googolplex)
 
I didn’t see any easy way to do this, as it’s pretty straight forward, raise a to the power of b, for all possible combinations of a and b < 100, take the sum of the digits, and repeat until you reach 9999, keeping track of the maximal sum.

int answer = -1;

for(int a = 1; a < 100; a++) {
   for(int b = 1; b < 100; b++) {
      BigInteger base = BigInteger.valueOf(a);
      BigInteger result = base.pow(b);
      int[] digits = EulerUtils.numberToDigits(result.toString());
      int sum = 0;
      for(int i : digits) {
         sum+=i;
      }
      if(sum > answer) answer = sum;
   }
}