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.
p067_triangle.txt
now. Is the result supposed to be 732506? \$\endgroup\$