Project Euler: Problem 32 – Pandigital products

Problem 32:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
 
The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
 
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
 
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Idea:

Right away, the problem is nice enough to state that I’ll encounter duplicates, so right off the bat, I know I want a data type that doesn’t permit duplicates.
 
Not knowing the range of the multiplicand and multiplier, I just took a guess at something I knew was relatively overkill for not wanting to have to go back and adjust my bounds. Expecially when all I’m doing is multiplying numbers together. Concatenate all the numbers together and check to see if it’s pandigital.

int answer = 0;
HashSet<Integer> products = new HashSet<Integer>();

for(int left = 1; left < 10000; left++) {
   for(int right = left; right < 10000; right++) {
      int product = left * right;
      String number = ""+product+""+left+""+right;
      if(isPandigital(number)){
         products.add(product);
      }
   }
}

for(Integer product:products) {
   answer += product;
}

System.out.println("Answer: "+answer);

Very inefficient brute-force, but hey, it worked. Initial attempt had the loop boundary too low.

Project Euler: Problem 18 – Maximum path sum I

Problem 18:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
 7 4
 2 4 6
 8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
 
Find the maximum total from top to bottom of the triangle below:

75
 95 64
 17 47 82
 18 35 87 10
 20 04 82 47 65
 19 01 23 75 03 34
 88 02 77 73 07 63 67
 99 65 04 28 06 16 70 92
 41 41 26 56 83 40 80 70 33
 41 48 72 33 47 32 37 16 94 29
 53 71 44 65 25 43 91 52 97 51 14
 70 11 33 28 77 73 17 78 39 68 17 57
 91 71 52 38 17 14 91 43 58 50 27 29 48
 63 66 04 68 89 53 67 30 73 16 69 87 40 31
 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Idea:

Before I noticed the note at the bottom, I was going to use a brute-force method. However, seeing recurring themes / patters in these problems (i.e. especially with prime numbers), and given the fact that this same problem occurs again in Problem 67, I figured might as well do it right the first time.
 
Thinking back to Problem 14, I realized I could make it more efficient by only computing the Collatz chain for a given number once, storing it, then just retrieving it whenever another number produced a chain that landed on that number. I figured I’d try a similar approach with this problem. However, I couldn’t do it from a top down approach (as that would be relatively equivalent to a brute-force method).
 
I decided to start from the base and work my way up, keeping track of the maximal path to the bottom for each node as I went. By the time I get to the top, I’ll have the maximal path to the bottom at that particular node (the starting node), which itself is the answer. I chose to use a custom data type to store not only the path length, but also a reference to the next node along the path to help me visualize the path from top to bottom, just in case I needed something like that for future problems.

int answer = -1;

int[][] tree = readTree("Problem_18.txt");  //Reads the tree into a 2D array
//In the form of a right triangle, max element is [i][i] per row

//SumTreePath is a helper class that stores the current value, the total sum
//thus far, and the reference to the next SumTreePath node
Euler.SumTreePath path = treePath(tree,true);
answer = path.getSum();

System.out.println("Answer: "+answer);
//==========================================
private static Euler.SumTreePath treePath(int[][] tree, boolean maximal) {
   Euler.SumTreePath[][] sumTree;

   boolean MAXIMAL = maximal;
   sumTree = new Euler.SumTreePath[tree.length][];

   //initialize last row of sums
   sumTree[tree.length-1] =
         new Euler.SumTreePath[tree[tree.length-1].length];
   for(int i = 0; i < tree[tree.length-1].length; i++) {
      sumTree[tree.length-1][i] =
      new Euler.SumTreePath(tree[tree.length-1][i],tree[tree.length-1][i], 0);
   }

   //ignore last row, already populated
   for(int i = tree.length-2; i >= 0; i--) {
      sumTree[i] = new Euler.SumTreePath[tree[i].length];
      for(int j = 0; j < tree[i].length; j++) {
         //calculate cumulative sum of left choice
         int sum1 = tree[i][j] + sumTree[i+1][j].getSum();
         //calculate cumulative sum of right choice
         int sum2 = tree[i][j] + sumTree[i+1][j+1].getSum();

         Euler.SumTreePath sumTreeValue =
                  new Euler.SumTreePath(tree[i][j],sum1,tree[i+1][j]);
         if(sum2 > sum1 && MAXIMAL) {
            sumTreeValue =
                  new Euler.SumTreePath(tree[i][j],sum2,tree[i+1][j+1]);
         }

         sumTree[i][j] = sumTreeValue;
      }
   }

   //Return root node (current value, current sum, reference to next node)
   return sumTree[0][0];
}