title: Maximum path sum In a triangle with prime number check
body: <p>I was given this algorithm task:  </p>
  
  <p>You will have a triangle input below and you need to find the maximum sum of the numbers according to given rules below; </p>
  
  <ol>
  <li>You will start from the top and move downwards to an adjacent number as in below. </li>
  <li>You are only allowed to walk downwards and diagonally. </li>
  <li><p>You can only walk over NON PRIME NUMBERS. </p>
  
  <pre><code>     1
      8 4
    2  6  9
   8  5  9  3
  </code></pre></li>
  </ol>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <pre><code>                                  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
  </code></pre>
  
  <p>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.</p>
  
  <p>I know there are different approaches of solving this problem which can be </p>
  
  <ul>
  <li><p>Brute Force method</p></li>
  <li><p>Dynamic Programming method</p></li>
  </ul>
  
  <p>I used Dynamic Programming method approach due to its efficiency:</p>
  
  <pre><code>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 &gt;= 0; i--)
          {
              for (int j = 0; j &lt; 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 &lt; arrayOfRowsByNewlines.Length; row++)
          {
              var eachCharactersInRow = arrayOfRowsByNewlines[row].Trim().Split(' ');
  
              for (int column = 0; column &lt; 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 &amp; 1) == 0)
          {
              if (number == 2)
              {
                  return true;
              }
              return false;
          }
  
          for (int i = 3; (i * i) &lt;= number; i += 2)
          {
              if ((number % i) == 0)
              {
                  return false;
              }
          }
          return number != 1;
      }
  
  
  
  
  }
  </code></pre>
  
  <p>Can somebody help me go through the code and see if there is a better way of solving it. </p>