Problem statement of PE18 is :
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
And PE67 is the very same question but,
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 is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. It cannot be solved by brute force, and requires a clever method! ;o)
My Implementation :
public class Euler_18{
// A custom data structure used to store
// the array so that I can seperate the
// logic from the storage
static class TriangularArray{
HashMap<Integer, int[]> map;
int someInt;
int size;
// All the elements will be stored in
// HashMap according to their order
public TriangularArray(int size){
this.size = size;
map = new HashMap<Integer, int[]>();
// Initialise the array
for(int i=1; i<=size; i++){
int[] currArray = new int[i];
map.put(i, currArray);
}
}
// Accept the array
public void acceptArray(Scanner in){
for(int i=1; i<=size; i++){
int[] currArray = map.get(i);
for(int j=0; j<currArray.length; j++){
currArray[j] = in.nextInt();
}
map.put(i, currArray);
}
}
// Display the array
public void displayArray(){
for(int i=1; i<=size; i++){
int[] currArray = map.get(i);
System.out.println("Array " + i + " : " + Arrays.toString(currArray));
}
}
// Finds the maximum using Memoization.
public void findMaximum(){
for (int i=size-1; i>0; i--) {
int[] currArray = map.get(i);
int[] belowArray = map.get(i+1);
for (int j=0; j<currArray.length; j++) {
// The value of current element will be the maximum of the 2 values
// of the array directly below it
currArray[j] = Math.max(belowArray[j], belowArray[j+1]) + currArray[j];
}
}
System.out.println("The maximum route is of length : " + map.get(1)[0]);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int size = in.nextInt();
TriangularArray theArray = new TriangularArray(size);
theArray.acceptArray(in);
theArray.displayArray();
theArray.findMaximum();
}
}