Mix10/XAML/WPF/ParallelProgramming/and more…

Project Euler problem 18~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The maximum total from top to bottom of the triangle below:");
  8:             sw.Start();
  9:             var sum1 = test();
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("cascading addition arithmetic way(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("Press any key to exit");
 16:             Console.ReadKey();
 17:         }
 18: 
 19:         // i ❤ alt select + copy/paste
 20:         static int[][] map = new int[][]
 21:         {
 22:             new int[] {75},
 23:             new int[] {95, 64},
 24:             new int[] {17, 47, 82},
 25:             new int[] {18, 35, 87, 10},
 26:             new int[] {20, 04, 82, 47, 65},
 27:             new int[] {19, 01, 23, 75, 03, 34},
 28:             new int[] {88, 02, 77, 73, 07, 63, 67},
 29:             new int[] {99, 65, 04, 28, 06, 16, 70, 92},
 30:             new int[] {41, 41, 26, 56, 83, 40, 80, 70, 33},
 31:             new int[] {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
 32:             new int[] {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
 33:             new int[] {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
 34:             new int[] {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
 35:             new int[] {63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
 36:             new int[] {04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23},
 37:         };
 38: 
 39:         //static int[][] map = new int[][]
 40:         //{
 41:         //    new int[] {3},          new int[] {3},           new int[] {3},         *new int[] {23},
 42:         //    new int[] {7,4},    ->  new int[] {7,4},     -> *new int[] {20,19},   -> new int[] {20,19},    
 43:         //    new int[] {2,4,6},     *new int[] {10,13,15},    new int[] {10,13,15},   new int[] {10,13,15},
 44:         //   *new int[] {8,5,9,3},    new int[] {8,5,9,3},     new int[] {8,5,9,3},    new int[] {8,5,9,3},
 45:         //};
 46: 
 47:         /// <summary>
 48:         /// replace each cell in each row with higher sum of cell + right or left children, so the follow
 49:         ///  2             (2+8)             10
 50:         /// 8  5 becomes  8     5 becomes   8   5
 51:         /// eventually the 1st cell of the whole thing would contain the highest sum (see above)
 52:         /// </summary>
 53:         /// <returns></returns>
 54:         static int test()
 55:         {
 56:             var left = 0;
 57:             var right = 0;
 58:             for (int row = map.Length - 2; row >= 0; row--)
 59:             {
 60:                 for (int col = 0; col < map[row].Length; col++)
 61:                 {
 62:                     left = map[row + 1][col];
 63:                     right = map[row + 1][col + 1];
 64:                     map[row][col] = map[row][col] + (left > right ? left : right);
 65:                 }
 66:             }
 67:             return map[0][0];
 68:         }
 69:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s