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:

• Create a triangular array initialized to all zeros and initialize rowIndex to the bottom row

• Add the numbers on this row to the copied array.

• Iterate through this row, for each consecutive pair of numbers find the smallest one and copy that to the above row.

• 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.

`Triangl

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> 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 = 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 > toList() {
        List> result = new ArrayList<>();
        for (int[] row : triangle) {
            List rowList = Arrays.stream(row).mapToObj(i -> i).collect(Collectors.toList());
            result.add(rowList);
        }

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

StackExchange Code Review Q#67152, answer score: 6