# Maximum path sum in a triangle with prime number check

I was given this algorithm task:

You will have a triangle input below and you need to find the maximum sum of the numbers according to given rules below;

1. You will start from the top and move downwards to an adjacent number as in below.
2. You are only allowed to walk downwards and diagonally.
3. You can only walk over NON PRIME NUMBERS.

     1
8 4
2  6  9
8  5  9  3


As you can see this has several paths that fits the rule of NOT PRIME NUMBERS; 1>8>6>9, 1>4>6>9, 1>4>9>9 1 + 8 + 6 + 9 = 24. As you see 1, 8, 6, 9 are all NOT PRIME NUMBERS and walking over these yields the maximum sum.

According to above rules what is the maximum sum of below input? It means please take this pyramid as an input (as file or constants directly inside the code) for your implementation and solve by using it.

                                  215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233


Note that, each node has only two children here (except the most bottom ones). As an example, you can walk from 215 to 124 (because 193 is a prime) then from 124 to either 237 or 442. From 124 you cannot go to 117 because it’s not a direct child of 124.

I know there are different approaches of solving this problem which can be

• Brute Force method

• Dynamic Programming method

I used Dynamic Programming method approach due to its efficiency:

   using System;

class Program
{
static void Main(string[] args)
{

//get input
var input = GetInput();

string[] arrayOfRowsByNewlines = input.Split('\n');

var tableHolder = FlattenTheTriangleIntoTable(arrayOfRowsByNewlines);

var result = WalkThroughTheNode(arrayOfRowsByNewlines, tableHolder);

Console.WriteLine($"The Maximum Total Sum Of Non-Prime Numbers From Top To Bottom Is: {result[0,0]}"); Console.ReadKey(); } private static string GetInput() { const string input = @" 215 193 124 117 237 442 218 935 347 235 320 804 522 417 345 229 601 723 835 133 124 248 202 277 433 207 263 257 359 464 504 528 516 716 871 182 461 441 426 656 863 560 380 171 923 381 348 573 533 447 632 387 176 975 449 223 711 445 645 245 543 931 532 937 541 444 330 131 333 928 377 733 017 778 839 168 197 197 131 171 522 137 217 224 291 413 528 520 227 229 928 223 626 034 683 839 053 627 310 713 999 629 817 410 121 924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"; return input; } private static int[,] WalkThroughTheNode(string[] arrayOfRowsByNewlines, int[,] tableHolder) { // walking through the non-prime node for (int i = arrayOfRowsByNewlines.Length - 2; i >= 0; i--) { for (int j = 0; j < arrayOfRowsByNewlines.Length; j++) { //only sum through the non-prime node if ((!IsPrime(tableHolder[i, j]))) { tableHolder[i, j] = Math.Max(tableHolder[i, j] + tableHolder[i + 1, j], tableHolder[i, j] + tableHolder[i + 1, j + 1]); } } } return tableHolder; } private static int[,] FlattenTheTriangleIntoTable(string[] arrayOfRowsByNewlines) { int[,] tableHolder = new int[arrayOfRowsByNewlines.Length, arrayOfRowsByNewlines.Length + 1]; for (int row = 0; row < arrayOfRowsByNewlines.Length; row++) { var eachCharactersInRow = arrayOfRowsByNewlines[row].Trim().Split(' '); for (int column = 0; column < eachCharactersInRow.Length; column++) { int number; int.TryParse(eachCharactersInRow[column], out number); tableHolder[row, column] = number; } } return tableHolder; } public static bool IsPrime(int number) { // Test whether the parameter is a prime number. if ((number & 1) == 0) { if (number == 2) { return true; } return false; } for (int i = 3; (i * i) <= number; i += 2) { if ((number % i) == 0) { return false; } } return number != 1; } }  Can somebody help me go through the code and see if there is a better way of solving it. ## 3 Answers FlattenTheTriangleIntoTable simply assumes the input is properly formatted (No test for "triangularity", and result of TryParse is thrown away). As you control the input, that works but is fragile. You are testing each input in isolation for primality. Consider at least memoizing the primality-test. You don't mark any cell with a prime-input as "cannot be a source". See the following pyramid:  1 1 2  Your result: 3 (1+2) Actual result: 2 (1+1) There's some wonky newlines before the closing brace of your class. Also at the start of Main. The spaces before using are slightly irritating. Also max(a + b, a + c) can be simplified to a + max(b, c), if there is no overflow. You know you can return a boolean expression directly, so why do you put it into an if-statement the once? For variety? • Have you actually tested your input with the code? I ran your input with the code but my result is 3. – vicosoft May 18 '17 at 16:11 • @vicosoft: Sorry, my mental interpreter had a hiccup. Should be fixed now... – Deduplicator May 18 '17 at 16:36 • Good points! What do you think will be the best test condition to ensure will sum through the non-prime nodes only? – vicosoft May 18 '17 at 17:02 • Well, I would go over all cells first and change the primes to some impossible value, 0 seems to work. and then propagate that where needed: both sources 0 or current 0 => 0, otherwise current + max(sources). – Deduplicator May 18 '17 at 17:47 You can greatly improve the readability and testability of the code by better encapsulating each operation into its own method. This will allow you to nicely chain them. Additionally you should unify the two for loops calculating the sums so that they both start at the bottom right corner. With one more helper variable you can save the second loop from going over the zeros in each row. var max = input .Trim() .ParseTriangle() .ToArray2D() .CalcMaxPath();  All methods are extensions that you can easily test and finally compose to get the max value. Here they are (without prime cache). You can parse the data easily with split by NewLine public static IEnumerable<IEnumerable<int>> ParseTriangle(this string input) { return input .Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries) .Select(ParseLine); }  and another helper that uses regex to find the numbers. This does not rely on the spaces between them. private static IEnumerable<int> ParseLine(string line) { return Regex .Matches(line, "[0-9]+") .Cast<Match>() .Select(m => int.Parse(m.Value)); } public static bool IsPrime(this int number) { // no changes here }  The ToArray2D converts the parsed numbers/values into a two-dimensional array. public static T[,] ToArray2D<T>(this IEnumerable<IEnumerable<T>> values) { var arrays = values.Select(v => v.ToArray()).ToArray(); var result = new T[arrays.Length, arrays.Max(a => a.Length)]; for (int row = 0; row < arrays.Length; row++) { for (int col = 0; col < arrays[row].Length; col++) { result[row, col] = arrays[row][col]; } } return result; }  Finally the CalcMaxPath clones the values because it's not a good practice to overwrite the parameter. It performs the calculation on a copy. Here both loops start at the bottom right corner and the colOffset prevents the second loop from unnecessarily going over the zeros. public static int CalcMaxPath(this int[,] values) { var result = values.Clone() as int[,]; var colOffset = 0; for (int row = values.GetLength(0) - 2; row >= 0; row--) { for (int col = values.GetLength(0) - 2 + colOffset; col >= 0; col--) { if (result[row, col].IsPrime()) continue; result[row, col] = Math.Max( result[row, col] + result[row + 1, col], result[row, col] + result[row + 1, col + 1] ); } colOffset--; } return result[0, 0]; }  kudos to @Deduplicator for the insight. I have been able to come up with this solution. It works for me. using System; using System.Collections.Generic; class Program { static void Main(string[] args) { //get input var input = GetInput(); string[] arrayOfRowsByNewlines = input.Split('\n'); var tableHolder = FlattenTheTriangleIntoTable(arrayOfRowsByNewlines); var result = WalkThroughTheNode(arrayOfRowsByNewlines, tableHolder); Console.WriteLine($"The Maximum Total Sum Of Non-Prime Numbers From Top To Bottom Is:  {result[0,0]}");

}

private static string GetInput()
{

const string input =      @" 215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233";
return input;
}

private static int[,] WalkThroughTheNode(string[] arrayOfRowsByNewlines, int[,] tableHolder)
{

// walking through the non-prime node
for (int i = arrayOfRowsByNewlines.Length - 2; i >= 0; i--)
{
for (int j = 0; j < arrayOfRowsByNewlines.Length; j++)
{
var c = resetResult[i, j];
var a = resetResult[i + 1, j];
var b = resetResult[i + 1, j + 1];
//only sum through the non - prime node
if ((!IsPrime(c) && !IsPrime(a)) || (!IsPrime(c) && !IsPrime(b)))
tableHolder[i, j] = c + Math.Max(a, b);

}
}
return tableHolder;
}

private static int[,] ResetAllPrimeNumbers(string[] arrayOfRowsByNewlines, int[,] tableHolder)
{
for (int i = 0; i < arrayOfRowsByNewlines.Length; i++)
{
for (int j = 0; j < arrayOfRowsByNewlines.Length; j++)
{
if (IsPrime(tableHolder[i, j]))
tableHolder[i, j] = 0;
}
}
return tableHolder;
}

public static  Dictionary<int,bool> PrimeCache= new Dictionary<int, bool>();
private static int[,] FlattenTheTriangleIntoTable(string[] arrayOfRowsByNewlines)
{
int[,] tableHolder = new int[arrayOfRowsByNewlines.Length, arrayOfRowsByNewlines.Length + 1];

for (int row = 0; row < arrayOfRowsByNewlines.Length; row++)
{
var eachCharactersInRow = arrayOfRowsByNewlines[row].Trim().Split(' ');

for (int column = 0; column < eachCharactersInRow.Length; column++)
{
int number;
int.TryParse(eachCharactersInRow[column], out number);
tableHolder[row, column] = number;
}
}
return tableHolder;
}

public static bool IsPrime(int number)
{
// Test whether the parameter is a prime number.
if (PrimeCache.ContainsKey(number))
{
bool value;
PrimeCache.TryGetValue(number, out value);
return value;
}
if ((number & 1) == 0)
{
if (number == 2)
{
return true;
}
return false;
}

for (int i = 3; (i * i) <= number; i += 2)
{
if ((number % i) == 0)
{