Project Euler 67 - Max path through triangle

Question

This is a response to this brute-force version where the algorithm was not intended for review.

In this challenge you are prompted to find the path through a large triangular set of numers, similar to:

     75
    13 92
   43 77 12
  11 55 86 7
 ....

The goal is to find a path from the top to the bottom while summing the values as you go, where the sum of the items on the path must be the maximum sum possible. Using the top-4 lines in the example above, the path would be 75 + 92 + 77 + 86. The goal is to report the sum of the path, or 330

I decided to use some Java 8-based idioms to parse and process the triangle. This is where I hope to get some focus for the review as well, whether there are better Java-8 ways to do this.

To parse the data in to a 2-dimensional int array:

private static int[][] getTriangle(Path source) throws IOException {
    try(Stream<String> lines = Files.lines(source)) {
        return lines.map(String::trim)
                .filter(line -> !line.isEmpty())
                .map(level -> parseLevel(level))
                .toArray(sz -> new int[sz][]);
    }
}

private static int[] parseLevel(String level) {
    return Stream.of(level.split("\\s+"))
                 .mapToInt(Integer::parseInt)
                 .toArray();
}

Then, to compute the maximum path:

private static int maxPath(final int[][] triangle) {

    // start at the bottom, and work to the top.
    // maintain a 'current' array which is the maximum value
    // possible at the current line for the specified values.
    // swap that with the 'previous' line when a line is complete.

    int[] previous = new int[triangle.length + 1];
    int[] current = new int[previous.length];

    for (int row = triangle.length - 1; row >= 0; row--) {
        for (int col = 0; col <= row; col++) {
            current[col] = Math.max(previous[col], previous[col + 1]) + triangle[row][col];
        }
        int[] tmp = previous;
        previous = current;
        current = tmp;
    }

    // the first value of the top row is the maximum path sum.
    return previous[0];
}

When I run with the following main method:

public static void main(String[] args) throws IOException {
    for (String p : args) {
        Path path = Paths.get(p);
        int[][] triangle = getTriangle(path);
        long nanos = System.nanoTime();
        int maxpath = maxPath(triangle);
        nanos = System.nanoTime() - nanos;
        System.out.printf("Maxpath for %s is %d (in %.3fms)\n", p, maxpath, nanos / 1000000.0);
    }
}

I get the results for #18 in 0.030ms and for #67 in 0.203ms on my computer.

Answer 1

I guess, you haven't got an answer until now, as there's hardly anything to say. So I must be very critical in order to get a non-empty answer.

getTriangle

Despite Java 8, it's nicely readable. I'm not sure about

            .filter(line -> !line.isEmpty())

as it may hide errors like when someone decides to put multiple input triangles into one file. We know, it won't happen, but still. All I'd do is to drop leading and trailing blank lines, so that such a problem gets immediately detected. However, I can't see a simple way how to achieve this.

The method is called getTriangle, but makes no checks about really reading a triangle. That's mostly fine as it'll blow later anyway, but I'd call it maybe getSourceAsInts in order not to suggest that the result must be a triangle.

maxPath

It ideally should start by checking that the input is indeed a triangle. Otherwise, it may be hard to find the cause of the exception thrown later. int[] previous = new int[triangle.length + 1]; int[] current = new int[previous.length];

Given that the triangle already takes O(n*n), I wouldn't bother with saving memory here (speed-wise it hardly matters). When optimizing hard, I'd consider to overwrite the original triangle. That said, your choice is surely not bad.

You could also use long in order to prevent overflow (Not needed, I know).

// the first value of the top row is the maximum path sum.
return previous[0];

It's a bit confusing as when the top element is previous, what's then current? Maybe using the name combo current and next would be clearer (and maybe not).

main

Nothing to say.

---

I get the results for #18 in 0.030ms and for #67 in 0.203ms on my computer.

For #67 it's about the same time as mine, with #18 I'm much slower as my solution uses my other utilities which leads to loading many classes. But I wouldn't care about such small times at all.

(from a comment)

I don't believe it will be. Even Dijkstra has to visit every node once

Agreed. Your solution is optimized for the given input graph shape, much simpler and faster than general Dijkstra.