back from vacation

Project Euler problem 92~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The numbers of starting numbers below ten million arrived at 89: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_with_memoization);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically use memoization to store prevous calculated result
 16:         /// and the long nested loop speeds up the process by not breaking down the number and generate first pass
 17:         /// number iteratively.
 18:         /// </summary>
 19:         static int brute_force_with_memoization()
 20:         {
 21:             var map = new Dictionary<int, bool>();
 22:             var squares = Enumerable.Range(0, 10).Select(l => l * l).ToArray();
 23:             Func<int, bool> expand_chain = null;
 24:             expand_chain = num =>
 25:             {
 26:                 if (num == 89)
 27:                     return true;
 28:                 else if (num <= 1)
 29:                     return false;
 30:                 else
 31:                     return map.ContainsKey(num) == true ? map[num] : (map[num] = expand_chain(form_new_number(num)));
 32:             };
 33:             var count = 0; // since the question asks for 10mil, which means 7 nested loops
 34:             for (int a = 0; a < 10; a++)
 35:             {
 36:                 var a0 = squares[a];
 37:                 for (int b = 0; b < 10; b++)
 38:                 {
 39:                     var b0 = a0 + squares[b];
 40:                     for (int c = 0; c < 10; c++)
 41:                     {
 42:                         var c0 = b0 + squares[c];
 43:                         for (int d = 0; d < 10; d++)
 44:                         {
 45:                             var d0 = c0 + squares[d];
 46:                             for (int e = 0; e < 10; e++)
 47:                             {
 48:                                 var e0 = d0 + squares[e];
 49:                                 for (int f = 0; f < 10; f++)
 50:                                 {
 51:                                     var f0 = e0 + squares[f];
 52:                                     for (int g = 0; g < 10; g++)
 53:                                     {
 54:                                         if (expand_chain(f0 + squares[g]) == true)
 55:                                             count++;
 56:                                     }
 57:                                 }
 58:                             }
 59:                         }
 60:                     }
 61:                 }
 62:             }
 63:             return count;
 64:         }
 65: 
 66:         static int form_new_number(int num)
 67:         {
 68:             var result = 0;
 69:             do
 70:             {
 71:                 var d = num % 10;
 72:                 result += d * d;
 73:             } while ((num /= 10) > 0);
 74:             return result;
 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++

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