Project Euler 18/67 : Maximum Path using Memoization

Question

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();
}
}

Answer 1

Storage

A Map is most useful when the key values are not in a sequence, but sparse, with smaller and bigger gaps between key values.

In this example, the key corresponds to a row of the triangle, taking on values from 0 to size, and using all values in the range. An array would be a more natural choice for storage, in this example an int[][].

Note that a hash map has some storage overhead. Also, accessing array elements is simpler to write than .get(...) and .put(...) calls.

Encapsulation

This is a bit unfortunate:

TriangularArray theArray = new TriangularArray(size);
theArray.acceptArray(in);
theArray.displayArray();
theArray.findMaximum();

Since findMaximum will modify the underlying storage, if you call theArray.findMaximum() one more time, it will produce different output, which is unexpected.

It's best when you can call a method multiple times and get the same result consistently. Unless of course it is by design that the call manipulates state, for example in an iterator. The name "findMaximum" doesn't hint at manipulating state, which is misleading.

In fact, findMaximum is designed for one-time use. It would be better to rewrite this in a way that the state manipulation becomes obvious. Or throw an exception if the method is called a second time. Or encapsulate the logic in a way that calling findMaximum repeatedly would produce the same result consistently.

I would also recommend to make findMaximum return the maximum instead of printing text.

Pointless statements

This variable is unused (and poorly named):

int someInt;

The map.put(i, currArray) statement at the end is unnecessary:

int[] currArray = map.get(i);
for(int j=0; j<currArray.length; j++){
    currArray[j] = in.nextInt();
}
map.put(i, currArray);

Because currArray comes from map.get(i), and it is not reassigned.

Other redundancies

TriangleArray.size is redundant. The same information is available through the underlying storage, whether using a map or an array.

Instead of initializing the arrays in the constructor, you could do it at the same time as parsing from Scanner, to iterate over the lines only once.

Most of the comments are completely redundant, noise, for example:

// Display the array
public void displayArray() {

This helps nobody, omit such redundant comments.

Naming

acceptArray is a strange name for a method that parses numbers from a Scanner. How about parseFromScanner ?

displayArray is a strange name for method that prints the content of the triangle. How about simply print ? As the method is on the TriangleArray class, it's implied that it will print the triangle itself.

Alternative implementation

Consider this alternative implementation:

static class TriangularArray {
    private final int[][] rows;

    public TriangularArray(int size) {
        rows = new int[size][];
    }

    public void parseFromScanner(Scanner scanner) {
        for (int i = 0; i < rows.length; i++) {
            rows[i] = new int[i + 1];
            for (int j = 0; j < rows[i].length; j++) {
                rows[i][j] = scanner.nextInt();
            }
        }
    }

    // Finds the maximum using Memoization.
    public int findMaximum() {
        int[] below = rows[rows.length - 1];
        for (int i = rows.length - 2; i >= 0; i--) {
            int[] current = rows[i].clone();
            for (int j = 0; j < current.length; j++) {
                current[j] = Math.max(below[j], below[j + 1]) + current[j];
            }
            below = current;
        }
        return below[0];
    }
}