MEF/ODATA/SketchFlow/XP-programming/and more…

Project Euler problem 31~

method takes forever to benchmark, so here is the screenshot(also, the 1st problem that i get to use and learn about dynamic programming, which i learned in college algorithm class but never able to understand(well i didn’t try very hard to study, too. Damn you, WOW)

 

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The different ways can £2 be made using any number of coins:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_loop_all_possibilities);
  9:             TestBenchLoader(controlled_brute_force_loop_eliminated_dead_ends);
 10:             TestBenchLoader(the_1337_dynamic_programming);
 11: 
 12:             Console.WriteLine("Press any key to exit");
 13:             Console.ReadKey();
 14:         }
 15: 
 16:         /// <summary>
 17:         /// iterate every possibilities, lawl
 18:         /// </summary>
 19:         /// <returns></returns>
 20:         static int brute_force_loop_all_possibilities()
 21:         {
 22:             var counter = 0;
 23:             for (int a = 0; a <= 1; a++)
 24:             {
 25:                 for (int b = 0; b <= 2; b++)
 26:                 {
 27:                     for (int c = 0; c <= 4; c++)
 28:                     {
 29:                         for (int d = 0; d <= 10; d++)
 30:                         {
 31:                             for (int e = 0; e <= 20; e++)
 32:                             {
 33:                                 for (int f = 0; f <= 40; f++)
 34:                                 {
 35:                                     for (int g = 0; g <= 100; g++)
 36:                                     {
 37:                                         for (int h = 0; h <= 200; h++)
 38:                                         {
 39:                                             if (a * 200 + b * 100 + c * 50 + d * 20 + e * 10 + f * 5 + g * 2 + h == 200)
 40:                                                 counter++;
 41:                                         }
 42:                                     }
 43:                                 }
 44:                             }
 45:                         }
 46:                     }
 47:                 }
 48:             }
 49:             return counter;
 50:         }
 51: 
 52:         /// <summary>
 53:         /// by filtering out the impossible value(like when 1 200p coin is used, there is no point keep going)
 54:         /// a alot of unnecessary loop is eliminated
 55:         /// </summary>
 56:         /// <returns></returns>
 57:         static int controlled_brute_force_loop_eliminated_dead_ends()
 58:         {
 59:             var counter = 0;
 60:             int a, b, c, d, e, f, g;
 61:             for (a = 200; a >= 0; a -= 200)
 62:             {
 63:                 for (b = a; b >= 0; b -= 100)
 64:                 {
 65:                     for (c = b; c >= 0; c -= 50)
 66:                     {
 67:                         for (d = c; d >= 0; d -= 20)
 68:                         {
 69:                             for (e = d; e >= 0; e -= 10)
 70:                             {
 71:                                 for (f = e; f >= 0; f -= 5)
 72:                                 {
 73:                                     for (g = f; g >= 0; g -= 2)
 74:                                     {
 75:                                         counter++;
 76:                                     }
 77:                                 }
 78:                             }
 79:                         }
 80:                     }
 81:                 }
 82:             }
 83:             return counter;
 84:         }
 85: 
 86:         /// <summary>
 87:         /// the dynamic programming way, lawl
 88:         /// (still considered to be voodoo magic to me, but getting better)
 89:         /// so lets say an array with map[0...201] where the index is the dollar value
 90:         /// and map[index] = all the ways made using any number of coins
 91:         /// if we construct this map from the beginning and starts with 1 coin
 92:         /// we can gradually transform the map with new ways added when more and more coins are added
 93:         /// which means that for n-th coins, we can use the result of (n-1)th coin and begin from there
 94:         /// so this make it a dynamic programming friendly problem, by solving all the subset problems
 95:         /// 1,2,,,n-th problem we would get the final answer, and all the subset result help creating the 
 96:         /// answer for final result, so we dont do any unnecessary/redundant calculations
 97:         /// start with 1st coin(1p), there is only 1 way for each value(since there is only 1 type of coin)
 98:         /// so after 1st coin(p1), the map is filled with 1.
 99:         /// now moves to next coin(2p), when value is 1(map[1]), 2p coin cant be used, so the way remain unchanged
100:         /// when value is 2, which is same as the coin, we know now there are 2 ways(one p2, or 2 p1)
101:         /// when value is 3, we can definitely use 1 p2, so the remaining value becomes 3-2=1, since the value(map[1]) 
102:         /// contains 1 way, we know the following:
103:         ///     1. by using the current latest coin(p2), the remaining value's way is stored in map[current value-p2's value]
104:         ///     2. if the current value is equal to current latest coin's value, then now we have one additional way
105:         ///     3. the current value contain all the ways of all previous walked-through coins(so far only p1)
106:         ///     4. so we can sum up 1,2 and 3 now we have all the way for the current value with all the current coins(p1, and p2)
107:         ///     5. put the result from (4.) in map[current value]
108:         /// repeat the process by going through all the value (1 to 200) as coins are added, evetually the map[200] would contain
109:         /// all the values.
110:         /// </summary>
111:         /// <returns></returns>
112:         static int the_1337_dynamic_programming()
113:         {
114:             var map = new int[201];
115:             var coins = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };
116:             var v = 0;
117:             var c = 0;
118:             var ways = 0;
119:             for (c = 0; c < 8; c++)
120:             {
121:                 for (v = 1; v < 201; v++)
122:                 {
123:                     if (v == coins[c])
124:                         map[v]++;
125: 
126:                     ways = v - coins[c];
127:                     if (ways >= 0)
128:                         map[v] = map[v] + map[ways];
129:                 }
130:             }
131:             return map[200];
132:         }
133: 
134:         static Stopwatch stopwatch = new Stopwatch();
135:         static void TestBenchSetup()
136:         {
137:             // Uses the second Core or Processor for the Test
138:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
139:             // Prevents "Normal" processes from interrupting Threads
140:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
141:             // Prevents "Normal" Threads from interrupting this thread
142:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
143:         }
144:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
145:         static void TestBenchLoader(Func<int> test_method)
146:         {
147:             stopwatch.Reset();
148:             stopwatch.Start();
149:             var result = 0;
150:             long avg_tick = 0;
151:             long avg_ms = 0;
152:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
153:             // stabilizes the CPU cache and pipeline.
154:             {
155:                 result = test_method(); // Warmup
156:             }
157:             stopwatch.Stop();
158:             for (int repeat = 0; repeat < 20; ++repeat)
159:             {
160:                 stopwatch.Reset();
161:                 stopwatch.Start();
162:                 result = test_method();
163:                 stopwatch.Stop();
164:                 avg_tick += stopwatch.ElapsedTicks;
165:                 avg_ms += stopwatch.ElapsedMilliseconds;
166:             }
167:             avg_tick = avg_tick / 20;
168:             avg_ms = avg_ms / 20;
169:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
170:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
171:         }
172:     }

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