Min triangle path - bottom-up

I got a bit intrigued with the recent question DP solution to min triangle path and after a certain chat message I decided that I wanted to implement my solution.

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]


The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

After coding it a bit, I realized that in my answer I had written it more complicated that it needed to be, and after debugging the OP's code I found that the OP's approach in the previous question was better than it looked.

Either way, I ended up with this approach:

1. Create a triangular array initialized to all zeros and initialize rowIndex to the bottom row
2. Add the numbers on this row to the copied array.
3. Iterate through this row, for each consecutive pair of numbers find the smallest one and copy that to the above row.
4. Go up a row and repeat from step two.

So, first two steps:

2          0
3 4        0 0
6 5 7      0 0 0
4 1 8 3    4 1 8 3


Checking the smallest consecutive numbers and setting to the row above:

2          0
3 4        0 0
6 5 7      1 1 3
4 1 8 3    4 1 8 3


Going up one row, adding all numbers on that row:

2          0
3 4        0 0
6 5 7      7 6 10
4 1 8 3    4 1 8 3


Checking the smallest consecutive numbers and setting to the row above:

2          0
3 4        6 6
6 5 7      7 6 10
4 1 8 3    4 1 8 3


Going up one row, adding all numbers on that row:

2          0
3 4        9 10
6 5 7      7 6 10
4 1 8 3    4 1 8 3


And finally, the same for last row:

2          11
3 4        9 10
6 5 7      7 6 10
4 1 8 3    4 1 8 3


Code

I have separated my code into a Triangle and a TriangleResult class. To support retrieving the actual path used (not just the sum) that was found to be the smallest.

Triangle class:

public class Triangle {

private final int[][] triangle;

public Triangle(int[][] triangle) {
this.triangle = copy2DArray(triangle);
}

static int[][] copy2DArray(int[][] input) {
int[][] result = new int[input.length][];
for (int i = 0; i < input.length; i++) {
result[i] = Arrays.copyOf(input[i], input[i].length);
}
return result;
}

public TriangleResult findShortestPath() {
int rowIndex = triangle.length - 1;
int[][] progress = new int[triangle.length][];

for (int y = 0; y < triangle.length; y++) {
progress[y] = new int[triangle[y].length];
}

while (rowIndex >= 0) {
int[] row = triangle[rowIndex];
int[] rowProgress = progress[rowIndex];

for (int x = 0; x < row.length; x++) {
rowProgress[x] += row[x];
}

for (int x = 0; x < row.length - 1; x++) {
int[] upperLevelSum = progress[rowIndex - 1];
int value = rowProgress[x];
int valueToRight = rowProgress[x + 1];
int min = Math.min(value, valueToRight);
upperLevelSum[x] = min;
}
rowIndex--;
}
return new TriangleResult(progress, triangle);
}

public static Triangle generate(int size, Random random, int maxValue) {
int[][] result = new int[size][];
for (int y = 0; y < result.length; y++) {
int[] row = new int[y + 1];
for (int x = 0; x < row.length; x++) {
row[x] = random.nextInt(maxValue);
}
result[y] = row;
}
return new Triangle(result);
}

public void print() {
for (int y = 0; y < triangle.length; y++) {
System.out.println(Arrays.toString(triangle[y]));
}
}

public List<List<Integer>> toList() {
List<List<Integer>> result = new ArrayList<>();
for (int[] row : triangle) {
List<Integer> rowList = Arrays.stream(row).mapToObj(i -> i).collect(Collectors.toList());
}

return result;
}
}


TriangleResult class:

public class TriangleResult {

private final int[][] data;
private final int[][] original;

public TriangleResult(int[][] data, int[][] original) {
this.data = Triangle.copy2DArray(data);
this.original = Triangle.copy2DArray(original);
}

public int getSmallestSum() {
return data[0][0];
}

public int[] getPath() {
int[] result = new int[data.length];
int x = 0;
result[0] = original[0][0];

for (int rowIndex = 1; rowIndex < result.length; rowIndex++) {
int[] row = data[rowIndex];
int[] originalRow = original[rowIndex];

if (x < row.length - 1) {
int left = row[x];
int right = row[x + 1];

if (right < left) {
x++;
}
}

result[rowIndex] = originalRow[x];
}

return result;
}

}


Test

public class RealTest {

@Test
public void triangle() {
Triangle tri = new Triangle(new int[][]{
new int[]{ 2 },
new int[]{ 3, 4 },
new int[]{ 6, 5, 7 },
new int[]{ 4, 1, 8, 3 }
});

TriangleResult solution = tri.findShortestPath();
assertEquals(11, solution.getSmallestSum());
assertArrayEquals(new int[]{ 2, 3, 5, 1 }, solution.getPath());
}

@Test(timeout = 100)
public void bigTriangle() {
Triangle tri = new Triangle(new int[][]{
new int[]{30},
new int[]{13, 48},
new int[]{34, 20, 25},
new int[]{5, 18, 19, 43},
new int[]{32, 2, 26, 42, 26},
new int[]{32, 6, 20, 43, 9, 0},
new int[]{13, 26, 13, 43, 41, 30, 8},
new int[]{37, 46, 30, 6, 30, 35, 17, 27},
new int[]{12, 43, 13, 14, 29, 15, 23, 37, 25},
new int[]{34, 7, 35, 7, 43, 43, 40, 8, 6, 10},
new int[]{10, 13, 9, 11, 3, 47, 19, 2, 1, 44, 44},
new int[]{48, 19, 25, 49, 40, 1, 3, 29, 23, 33, 36, 10},
new int[]{25, 43, 0, 44, 3, 42, 7, 43, 9, 44, 48, 29, 47},
new int[]{46, 23, 45, 9, 23, 29, 26, 26, 28, 20, 40, 32, 29, 33},
new int[]{11, 9, 46, 25, 22, 46, 4, 47, 1, 31, 20, 6, 45, 6, 29},
new int[]{46, 28, 8, 23, 2, 32, 22, 23, 33, 2, 2, 22, 38, 32, 22, 18},
new int[]{25, 42, 27, 33, 23, 27, 21, 23, 4, 3, 28, 43, 47, 41, 30, 35, 21},
new int[]{5, 31, 49, 0, 1, 42, 41, 34, 46, 40, 10, 15, 20, 30, 29, 29, 41, 24},
new int[]{34, 41, 8, 6, 31, 12, 46, 29, 42, 46, 39, 10, 49, 24, 35, 36, 45, 42, 31},
new int[]{48, 43, 16, 28, 16, 29, 39, 43, 43, 24, 9, 18, 28, 38, 19, 27, 22, 41, 4, 30},
new int[]{0, 43, 38, 48, 44, 5, 9, 31, 33, 23, 25, 31, 11, 43, 23, 3, 16, 43, 24, 37, 5},
new int[]{17, 18, 47, 16, 9, 37, 10, 3, 40, 36, 36, 31, 30, 38, 21, 41, 41, 30, 25, 43, 45, 31},
new int[]{25, 3, 45, 9, 9, 15, 31, 8, 9, 10, 16, 14, 47, 15, 7, 49, 6, 44, 40, 38, 31, 10, 9},
new int[]{36, 6, 43, 42, 17, 49, 2, 37, 10, 16, 19, 38, 25, 40, 40, 18, 19, 32, 7, 37, 13, 25, 41, 43},
new int[]{47, 39, 34, 16, 10, 19, 13, 33, 16, 2, 15, 38, 34, 24, 43, 44, 5, 13, 5, 0, 37, 5, 44, 9, 38},
new int[]{18, 29, 31, 36, 2, 48, 43, 41, 37, 36, 46, 7, 3, 21, 36, 9, 44, 7, 6, 11, 38, 42, 13, 9, 18, 24},
new int[]{7, 41, 6, 10, 29, 6, 12, 7, 32, 23, 27, 30, 2, 6, 14, 15, 26, 46, 30, 45, 41, 18, 31, 2, 16, 29, 44},
new int[]{15, 38, 2, 42, 2, 45, 2, 37, 42, 45, 15, 21, 32, 0, 48, 29, 5, 26, 17, 46, 42, 10, 43, 27, 47, 43, 28, 33},
new int[]{18, 41, 10, 42, 20, 31, 37, 38, 8, 44, 8, 17, 13, 0, 49, 48, 43, 45, 24, 25, 47, 38, 34, 3, 4, 19, 11, 8, 36},
new int[]{9, 29, 41, 4, 0, 4, 38, 41, 35, 44, 48, 2, 1, 21, 2, 30, 28, 10, 18, 47, 7, 14, 41, 38, 25, 31, 17, 9, 9, 8},
new int[]{47, 43, 24, 49, 46, 44, 17, 7, 16, 6, 44, 30, 15, 25, 26, 7, 48, 15, 48, 30, 17, 36, 4, 16, 1, 40, 47, 34, 4, 13, 21},
new int[]{24, 24, 16, 3, 23, 26, 41, 23, 0, 20, 28, 45, 4, 24, 19, 33, 24, 34, 21, 7, 35, 21, 38, 25, 18, 34, 25, 1, 31, 30, 17, 48},
new int[]{38, 42, 14, 24, 32, 30, 26, 15, 40, 25, 13, 11, 0, 1, 9, 44, 10, 36, 24, 27, 48, 25, 48, 30, 13, 36, 18, 42, 14, 37, 41, 17, 8},
new int[]{19, 11, 48, 37, 3, 38, 7, 7, 12, 14, 42, 15, 39, 44, 49, 14, 32, 13, 4, 16, 20, 0, 1, 44, 14, 6, 43, 26, 33, 27, 45, 15, 43, 22},
new int[]{24, 12, 43, 32, 39, 46, 9, 43, 33, 5, 35, 35, 28, 48, 32, 6, 29, 3, 29, 23, 21, 23, 18, 23, 25, 49, 28, 22, 12, 17, 7, 3, 40, 41, 37},
new int[]{1, 38, 49, 22, 28, 43, 44, 41, 9, 18, 46, 9, 40, 48, 7, 27, 33, 9, 38, 28, 22, 40, 10, 26, 18, 7, 34, 9, 21, 35, 19, 6, 30, 29, 48, 17},
new int[]{20, 9, 37, 0, 5, 11, 40, 33, 11, 32, 28, 28, 23, 21, 18, 11, 39, 49, 36, 31, 42, 40, 11, 35, 28, 31, 37, 12, 24, 34, 6, 18, 13, 38, 45, 37, 32},
new int[]{17, 49, 38, 31, 20, 6, 6, 9, 18, 49, 25, 7, 4, 21, 0, 11, 31, 45, 35, 42, 9, 45, 18, 8, 46, 30, 44, 4, 5, 21, 18, 40, 38, 32, 13, 28, 38, 37},
new int[]{24, 48, 30, 49, 32, 38, 49, 28, 49, 46, 4, 6, 16, 3, 11, 49, 27, 39, 37, 24, 49, 12, 33, 3, 30, 14, 6, 39, 30, 34, 1, 40, 5, 17, 17, 29, 10, 17, 9},
new int[]{35, 36, 49, 16, 10, 1, 49, 49, 30, 19, 18, 16, 12, 32, 43, 24, 17, 32, 30, 46, 5, 21, 29, 6, 41, 20, 41, 2, 16, 3, 10, 41, 3, 14, 26, 5, 32, 15, 6, 14}
});

TriangleResult solution = tri.findShortestPath();
assertEquals(494, solution.getSmallestSum());
assertArrayEquals(new int[]{ 30, 13, 20, 18, 2, 6, 13, 6, 14, 7,
3, 1, 7, 26, 1, 2, 3, 10, 10, 18,
11, 38, 7, 18, 5, 7, 30, 17, 25, 7,
17, 21, 25, 0, 18, 10, 11, 8, 3, 6 }, solution.getPath());
}

}


Note that one of the tests have a time limit of 100ms, to show that this code is "fast".

Time complexity: $O(n^2)$ (where $n$ is the number of rows in the triangle). $O(n)$ if you consider $n$ to be the number of items. The same goes for space complexity.

Question

I'd rather have comments about the core algorithm (findShortestPath method) and the general approach than about naming and style, but you may (as usual on Code Review) comment about anything.

What I like:

• unit tests, pass for me too
• you have turned the Triangle in to an immutable class
• you have a result class
• you are using primitive int arrays instead of List<List<Integer>> references
• the algorithm is efficient

Where I think there are problems are:

• duplication of data in the Result class. Everything you need is in the Triangle.
• the algorithm you employ goes top-to-bottom, but bottom-to-top has some advantages.
• you should store a 'direction' vector in addition to the sum array (this will be explained in the code I show).
• the result method 'getPath()' should return the actual path, not the values at the path.

All the other style, and readability items are fine, great even.

So, to illustrate my suggestions above, the same problems solved using a simpler data structure:

TriangleResult (note rename to getPathValues())

import java.util.Arrays;

public class TriangleResult {

private final Triangle source;
private final int[] path;

public TriangleResult(Triangle t, int[] path) {
this.source = t;
this.path = Arrays.copyOf(path, path.length);
}

public int getSmallestSum() {
int sum = 0;
for (int v : source.pathValues(path)) {
sum += v;
}
return sum;
}

public int[] getPath() {
return Arrays.copyOf(path, path.length);
}
public int[] getPathValues() {
return source.pathValues(path);
}

}


Triangle

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

public class Triangle {

private final int[][] triangle;

public Triangle(int[][] triangle) {
this.triangle = copy2DArray(triangle);
}

static int[][] copy2DArray(int[][] input) {
int[][] result = new int[input.length][];
for (int i = 0; i < input.length; i++) {
result[i] = Arrays.copyOf(input[i], input[i].length);
}
return result;
}

public TriangleResult findShortestPath() {
int[][] clone = copy2DArray(triangle);
int[][] vectors = new int[clone.length][];
for (int row = clone.length - 2; row >= 0; row--) {
vectors[row] = new int[clone[row].length];
for (int c = clone[row].length - 1; c >= 0; c--) {
int min = Math.min(clone[row + 1][c], clone[row + 1][c + 1]);
// update clone to have the new value.
clone[row][c] += min;
// the value in vectors will be the place/column the value came from.
vectors[row][c] = clone[row + 1][c] == min ? c : c + 1;
}
}
int[] path = new int[vectors.length];
for (int i = 1; i < vectors.length; i++) {
path[i] = vectors[i - 1][path[i - 1]];
}
return new TriangleResult(this, path);
}

public static Triangle generate(int size, Random random, int maxValue) {
int[][] result = new int[size][];
for (int y = 0; y < result.length; y++) {
int[] row = new int[y + 1];
for (int x = 0; x < row.length; x++) {
row[x] = random.nextInt(maxValue);
}
result[y] = row;
}
return new Triangle(result);
}

public void print() {
for (int y = 0; y < triangle.length; y++) {
System.out.println(Arrays.toString(triangle[y]));
}
}

public List<List<Integer>> toList() {
List<List<Integer>> result = new ArrayList<>();
for (int[] row : triangle) {
List<Integer> rowList = Arrays.stream(row).mapToObj(i -> i).collect(Collectors.toList());
}

return result;
}

public int[] pathValues(int[] path) {
int[] vals = new int[path.length];
for (int i = 0; i < path.length; i++) {
vals[i] = triangle[i][path[i]];
}
return vals;
}
}


Some specific 'features' of the solution above are:

• the vectors structure is a common element to a number of algorithms. Knowing where your dynamic data came from is an asset
• reversing the logic, going bottom to top, is a way to optimize things in some algorithms, for example, you could potentially eliminate some paths if they go beyond 'impossible' ranges. Not in this problem, but in other problems where you look for common substrings, etc.
• there's no 'cloned' data that leaves the search method... the 'clone' and 'vectors' arrays are private to that method.
• I return a 'path' in the path, not a an array of values, but I allow the path to be translated in to values easily.

One other small thing... your print method could do an enhanced-for loop instead of the index loop:

public void print() {
for (int y = 0; y < triangle.length; y++) {
System.out.println(Arrays.toString(triangle[y]));
}
}


could be:

public void print() {
for (int[] row : triangle.length) {
System.out.println(Arrays.toString(row));
}
}


It looks like a good dynamic programming solution.

Small Details

• I don't like that you copy the full triangle in TriangleResult. You can just store the relevant path.

• You could define rowIndex right before its use in findShortestPath.

• I don't like raw arrays, but it might OK here for performance reasons.

• There might be many paths with the lowest cost. Your method should probably document that it returns only one such path.

Recursion

I don't know if you noticed, but this is basically a recursive algorithm where you start solving at the bottom of the triangle (even though your code is not recursive). It might not be a good idea to make a recursive algorithm in Java since you might hit a stack overflow (not in other languages such as Scala).

I started to write my recursive solution in Java, but I got frustrated because it was going to require a lot of code. I switched to Scala instead, sorry. I know this does not make much sense, but Java is very frustrating to use once you start coding in Scala.

  type Row = List[Int]
type Triangle =  List[Row]

case class Solution(cost: Int, path: List[Int]) {
}

def solveOneRow(row: Row, belowSolutions: List[Solution]): List[Solution] = {
require(row.size == belowSolutions.size - 1)
val leftRightSolutions = belowSolutions.zip(belowSolutions.tail)
val minBelowSolutions = leftRightSolutions.map { case (left, right) => if (left.cost < right.cost) left else right }
}

def solveTriangle(triangle: Triangle): Solution = {
val reversedTriangle = triangle.reverse
val emptySolutions = List.make(nBottom + 1, Solution(0, List()))
val finalSolution = reversedTriangle.foldLeft(emptySolutions)((belowSolutions, row) => solveOneRow(row, belowSolutions))
}

val triangle = List(List(3), List(5, 8), List(9, 8, 2))
println(solveTriangle(triangle))


EDIT:

It's quite funny. I just read the original post and discovered that recursion was used. The original post makes recursion seem quite complicated, especially the way it computes the path. I would define some new types (as I did in Scala) which would increase the code length in Java, but make things clearer.

• From what I can see of my code, I am definitely not using recursion. Where did you get that from? I am using iteration. Your Scala code is not very useful to me at the moment as I have not yet learned Scala (I would like to though). – Simon Forsberg Oct 19 '14 at 16:23
• Your Scala code might fit better in a new question, and a link to it from here, instead of as an answer to this question. – Simon Forsberg Oct 19 '14 at 16:33
• You are not using recursion. What I meant is that your while-loop is equivalent to calling a recursive function. When I read your code I thought it would be cleaner as a recursive function, but that is very arguable. I did not add the section about recursion to say that I disagree with your answer, but just as a suggestion/discussion. – toto2 Oct 19 '14 at 16:36
• Sorry, from your answer I thought you said my code was recursive. I misunderstood. The fact that it can cause a Stack Overflow in Java is one reason for why I decided to not make it recursive. What are the types that you would add? Just Row and Solution? The Solution might be a good idea. – Simon Forsberg Oct 19 '14 at 16:41
• It is not very useful at the moment to post Scala code on codereview since there are so few Scala programmers (at least on this site). I did get one useful review at some point however. – toto2 Oct 19 '14 at 16:42