Pass Triangle challenge

Question

In order to solve this challenge:

Challenge Description

By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.

   5

  9 6

 4 6 8

0 7 1 5

5 + 9 + 6 + 7 = 27

Input sample

Your program should accept as its first argument a path to a filename. Input example is the following:

5
9 6
4 6 8
0 7 1 5

You make also check full input file which will be used for your code evaluation.

Output sample

The correct output is the maximum sum for the triangle. So for the given example the correct answer would be

27

I came up with the following code:

static int GetMaxSum(int[][] numbers)
{
    int firstCandidate = 0;
    int secondCandidate = 0;
    int max = 0;

    for(int i = 1; i < numbers.Length; i++)
    {
        for(int j = 0; j < numbers[i].Length; j++)
        {
            firstCandidate = 0;
            secondCandidate = 0;

            if (j - 1 >= 0)
            {
                firstCandidate = numbers[i][j] + numbers[i - 1][j - 1];
            }

            if (j < numbers[i - 1].Length)
            {
                secondCandidate = numbers[i][j] + numbers[i - 1][j];
            }

            numbers[i][j] = firstCandidate > secondCandidate ? firstCandidate : secondCandidate;
        }
    }

    int lastIndex = numbers.Length - 1;
    var lastLine = numbers[lastIndex];
    for(int i = 0; i < lastLine.Length; i++)
    {
        if(lastLine[i] > max)
        {
            max = lastLine[i];
        }
    }

    return max;
}

static int[] ParseLine(string line)
{
    string[] numbers = line.Trim().Split(' ');
    int numbersLength = numbers.Length;
    var result = new int[numbersLength];

    for(int i = 0; i < numbersLength; i++)
    {
        result[i] = int.Parse(numbers[i]);
    }

    return result;
}

static void Main(string[] args)
{
    var list = new List<int[]>();
    int max = 0;

    using (StreamReader reader = File.OpenText(args[0]))
    {
        while (!reader.EndOfStream)
        {
            string line = reader.ReadLine();

            if (null == line)
            {
                continue;
            }

            list.Add(ParseLine(line));
        }
    }

    max = GetMaxSum(list.ToArray());

    Console.WriteLine(max);
}

and wanted some feedback on it.

The basic idea is:

• Read all the file
• Transform the content in a Lower Triangle Matrix structure
• Calculate max sums directly in the matrix (being that it's used only internally and it can be thrown once it's been processed)

This was the most efficient - with regard to space and time - algorithm I could think of.

Everything you can find - readability problems, efficiency problems, design problems, etc... - is fine.

Answer 1

The GetMaxSum() function would be clearer if it were not so monolithic. The general outline of the program is: update the numbers for each input row based on the previous intermediate results, and fetch the maximum at the end. The program structure should reflect that. Furthermore, you can avoid storing the entire triangle in memory by working as you encounter each row.

The firstCandidate / secondCandidate comparison would be better written using Math.Max().

Your ParseLine() can be simplified using Array.ConvertAll(). Since it's a one-liner, perhaps you don't need to write it as its own method at all.

The epilogue can be simplified using LINQ.

using System;
using System.IO;
using System.Linq;

public class Triangle
{
    private int[] Row = new int[0];

    public void AppendRow(string numbers)
    {
        int[] oldRow = Row;

        // http://stackoverflow.com/a/1297250
        Row = Array.ConvertAll(numbers.Trim().Split(' '), int.Parse);

        for (int j = 0; j < Row.Length; j++)
        {
            Row[j] += Math.Max
            (
                (j > 0)             ? oldRow[j - 1] : 0,
                (j < oldRow.Length) ? oldRow[j]     : 0
            );
        }
    }

    public int GetMaxSum()
    {
        return Row.Max();
    }

    public static void Main(string[] args)
    {
        Triangle triangle = new Triangle();
        using (StreamReader reader = File.OpenText(args[0]))
        {
            while (!reader.EndOfStream)
            {
                triangle.AppendRow(reader.ReadLine());
            }
        }
        Console.WriteLine(triangle.GetMaxSum());
    }
}

Answer 2

int firstCandidate = 0;
int secondCandidate = 0;
int max = 0;

None of these need as wide a scope as they have. In particular, firstCandidate and secondCandidate are only used inside the nested loop, and are initialised every time they're used. They should be pushed in (if not eliminated...)

---

        firstCandidate = 0;
        secondCandidate = 0;

        if (j - 1 >= 0)
        {
            firstCandidate = numbers[i][j] + numbers[i - 1][j - 1];
        }

        if (j < numbers[i - 1].Length)
        {
            secondCandidate = numbers[i][j] + numbers[i - 1][j];
        }

        numbers[i][j] = firstCandidate > secondCandidate ? firstCandidate : secondCandidate;

This can be simplified slightly with a simple algebraic rearrangement to factor out the numbers[i][j] from the two candidates, since we know that at least one candidate must exist. (Note that by using int.MinValue we also fix something which could be argued to be a bug, unless the spec clearly states that the triangle will never contain negative numbers).

I agree with TarkaDaal that Math.Max is slightly more readable. And I would also find it more readable with ternary operators. Bearing in mind the scope change mentioned above, I get:

        int firstCandidate = j > 0 ? numbers[i - 1][j - 1] : int.MinValue;
        int secondCandidate = j < numbers[i - 1].Length ? numbers[i - 1][j] : int.MinValue;
        numbers[i][j] += Math.Max(firstCandidate, secondCandidate);

---

To find the maximum of an array, Linq is more readable and you won't notice any speed difference.

---

Summarising, I would rewrite the d.p. method as

static int GetMaxSum(int[][] numbers)
{
    for(int i = 1; i < numbers.Length; i++)
    {
        for(int j = 0; j < numbers[i].Length; j++)
        {
            int firstCandidate = j > 0 ? numbers[i - 1][j - 1] : int.MinValue;
            int secondCandidate = j < numbers[i - 1].Length ? numbers[i - 1][j] : int.MinValue;
            numbers[i][j] += Math.Max(firstCandidate, secondCandidate);
        }
    }

    return numbers[numbers.Length - 1].Max();
}

Answer 3

Let's begin with 3 observations

• Consider going the bottom-up approach. If you start at the bottom, then numbers[0][0] will contain the maximum. This will save you twice going through the last row.
• You need to read the whole file before you can process it. This fact make your reading + parsing code much shorter.
• List<int[]> feels a bit so-so. Why not use a jagged array ? we know the length in advance, which is required for arrays

First reduce the amount of code for reading and parsing the file. You can read the whole file in 1 run with System.IO.File.ReadAllLines(string path) , this returns all lines in a string-array.

Next to that you could use Array.Convert method, which can parse all numbers to an array in 1 statement; it would replace your method ParseLine(string line). As it has lambda-function, but could also be a method-call. Array.ConvertAll(array, a => Int32.Parse(a)) can be shortened to Array.ConvertAll(array, Int32.Parse) and even to Array.ConvertAll(array, int.Parse); all 3 statements do the exact same.

Example for reading AND parsing the input file

static void Main(string[] args){
    var lines = File.ReadAllLines(args[0]);
    var numbers = new int[lines.Length][];
    for(int i = 0; i < lines.Length; i++){
        // Splitting strings and instantly convert them to integer-array
        // and adding them to the number array (jagged array)
        numbers[i] = Array.ConvertAll(lines[i].Trim().Split(' '), int.Parse);
    }
    int max = GetMaxSum(numbers);
    Console.WriteLine(max);
}

Now that we have reduced the amount of code for input-parsing. Lets see about GetMaxSum(int[][] numbers). As you specifically ask for

Calculate max sums directly in the matrix (being that it's used only internally and it can be thrown once it's been processed)

Indeed you can actually do it in-place. Especially when you go bottom-up, you leave the last row intact and bubble your way to the top. Lets visualize it with your example

5          5              20
9 6    =>  15 14      =>  15 14
4 6 8      4  6  8        4  6  8

An in-place GetMaxSum would still need to 2 for-loops and no code to determine the maximum, as numbers[0][0] contains the maximum sum.

static int GetMaxSum(int[][] numbers)
{
    for (int i = numbers.Length - 2; i >= 0; i--)
    {    // start at the bottom, but ignore the last row
        for (int j = 0; j < numbers[i].Length; j++)
        {    
            int left = numbers[i + 1][j];       // left child of current number
            int right = numbers[i + 1][j + 1];  // right child of current number
            // add the maximum to the current number
            numbers[i][j] = left >= right ? numbers[i][j] + left : numbers[i][j] + right;
        }
    }
    return numbers[0][0];
}

You could improve it more with the suggestions of TarkaDaal and Peter Taylor. They have covered Math.Max and Math.Min enough :)

Answer 4

Just my options, naturally, but here's what I think:

• You don't need the list.ToArray in your main method, as you can index List<> directly in C#.
• It took me quite a while to work out what your algorithm was in GetMaxSum. Comments, better variable names, or well named methods would help.
• This problem could be solved more elegantly using a tree, rather than a 2D array.
• To me, it seems counter-intuitive to overwrite your input data during your calculations .
• There's a mix of implicit and explicit typing (e.g., in the main method, where one variable is declared as var, and the other int). I prefer var, but either way, pick one and stick with it.

• Instead of

  numbers[i][j] = firstCandidate > secondCandidate ? firstCandidate : secondCandidate;

  ...consider:

  numbers[i][j] = Math.Max(firstCandidate, secondCandidate);

Answer 5

In the teams I have worked there has always been debate whether Linq makes code easier or harder to read, but I often like it. Just as a reference of what your GetMaxSum method could look like if you use functional programming to the limits:

static int GetMaxSum(int[][] numbers)
{
    return numbers
        .Reverse()
        .Aggregate(Enumerable.Repeat(0, numbers.Length + 1),
            (state, row) => {
                return state
                    .Zip(state.Skip(1), (x, y) => x > y ? x : y)
                    .Zip(row, (x, y) => x + y);
            })
        .Single();
}

The trick is that you work through the pyramid from base to tip. For every row, you need to add each element to the maximum of the maximum sums from the elements below it. In the aggregation, the first zip computes that maximum and the second zip adds the value of the current row.