SL/Game/Cassandra/XNA/Algorithm/and more…

Project Euler problem 67~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The maximum total from top to bottom in triangle.txt: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_linq_and_algorithm_from_problem_18);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically using linq to read all lines of number in reverse order, parse each line into int[], and then
 16:         /// use the same algorithm from problem 18(o(n), DP-style).
 17:         /// the current vector store the row with updated number(max sum from children)
 18:         /// the last holds the current's content because current will be wiped to hold new updated number.
 19:         /// for the alogorithm: see following:
 20:         /// 
 21:         /// static int[][] map = new int[][]
 22:         /// {
 23:         ///     new int[] {3},          new int[] {3},           new int[] {3},         *new int[] {23},
 24:         ///     new int[] {7,4},    ->  new int[] {7,4},     -> *new int[] {20,19},   -> new int[] {20,19},   
 25:         ///     new int[] {2,4,6},     *new int[] {10,13,15},    new int[] {10,13,15},   new int[] {10,13,15},
 26:         ///    *new int[] {8,5,9,3},    new int[] {8,5,9,3},     new int[] {8,5,9,3},    new int[] {8,5,9,3},
 27:         /// };
 28:         /// 
 29:         /// Replace each cell in each row with higher sum of cell + right or left children, so the follow:
 30:         /// 
 31:         ///  2             (2+8)             10
 32:         /// 8  5 becomes  8     5 becomes   8   5
 33:         /// 
 34:         /// eventually the 1st cell of the whole thing would contain the highest sum (see above)
 35:         /// Since the the file is read in reverse, so "foreach" code can start from 1st row and work the way down, using
 36:         /// current and last respectively. eventually current would contain 1st cell which is the max possible sum.
 37:         /// </summary>
 38:         static int using_linq_and_algorithm_from_problem_18()
 39:         {
 40:             var index = 0;
 41:             var last = new List<int>();
 42:             var current = new List<int>();
 43: 
 44:             File.ReadAllLines("triangle.txt")
 45:                 .Reverse()
 46:                 .Select(row => row.Split(' ').Select(ch => Convert.ToInt32(ch)).ToArray())
 47:                 .ToList()
 48:                 .ForEach(row =>
 49:                     {
 50:                         if (index > 0)
 51:                         {
 52:                             var left = 0;
 53:                             var right = 0;
 54:                             current.Clear();
 55:                             for (int col = 0; col < row.Length; col++)
 56:                             {
 57:                                 left = last[col];
 58:                                 right = last[col + 1];
 59:                                 current.Add(row[col] + (left > right ? left : right));
 60:                             }
 61:                             last.Clear();
 62:                             for (int col = 0; col < current.Count; col++)
 63:                                 last.Add(current[col]);
 64:                         }
 65:                         else
 66:                         {
 67:                             last.Clear();
 68:                             for (int col = 0; col < row.Length; col++)
 69:                                 last.Add(row[col]);
 70:                         }
 71:                         index++;
 72:                     });
 73: 
 74:             return current.First();
 75:         }
 76: 
 77:         static Stopwatch stopwatch = new Stopwatch();
 78:         static void TestBenchSetup()
 79:         {
 80:             // Uses the second Core or Processor for the Test
 81:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 82:             // Prevents "Normal" processes from interrupting Threads
 83:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 84:             // Prevents "Normal" Threads from interrupting this thread
 85:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 86:         }
 87:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 88:         static void TestBenchLoader(Func<int> test_method)
 89:         {
 90:             stopwatch.Reset();
 91:             stopwatch.Start();
 92:             var result = 0;
 93:             long avg_tick = 0;
 94:             long avg_ms = 0;
 95:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 96:             // stabilizes the CPU cache and pipeline.
 97:             {
 98:                 result = test_method(); // Warmup
 99:             }
100:             stopwatch.Stop();
101:             for (int repeat = 0; repeat < 20; ++repeat)
102:             {
103:                 stopwatch.Reset();
104:                 stopwatch.Start();
105:                 result = test_method();
106:                 stopwatch.Stop();
107:                 avg_tick += stopwatch.ElapsedTicks;
108:                 avg_ms += stopwatch.ElapsedMilliseconds;
109:             }
110:             avg_tick = avg_tick / 20;
111:             avg_ms = avg_ms / 20;
112:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
113:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
114:         }
115:     }

c++

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

int using_linq_and_algorithm_from_problem_18();
int main()  
{
  cout << "The maximum total from top to bottom in triangle.txt: \n";
  int answer = using_linq_and_algorithm_from_problem_18();
  cout << "using_linq_and_algorithm_from_problem_18 way: " << answer;

  cout << "\nPress any key to exit";
  string input = "";
  getline(cin, input);
  return 0; 
}

int using_linq_and_algorithm_from_problem_18()
{
  short triangle[100][100];
  std::ifstream src;
  src.open("triangle.txt");
  if (src.is_open() == false)
  {
    cout << "\nFile(triangle.txt) is not found!";
    return 0;
  }
  for (int row = 0; row < 100; row++)
  {
    for (int col = 0; col <= row; col++)
    {
      src >> triangle[row][col];
    }
  }
  src.close();
  for (int row = 98; row >= 0; row--)
  {
    for (int col = 0; col <= row; col++)
    {
      triangle[row][col] += max(triangle[row + 1][col], triangle[row + 1][col + 1]);
    }
  }
  return triangle[0][0];
}

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