Pass Triangle challenge

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 = 0)
            {
                firstCandidate = numbers[i][j] + numbers[i - 1][j - 1];
            }

            if (j  secondCandidate ? firstCandidate : secondCandidate;
        }
    }

    int lastIndex = numbers.Length - 1;
    var lastLine = numbers[lastIndex];
    for(int i = 0; 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 ();
    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

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

StackExchange Code Review Q#118866, answer score: 3