- Ten Reasons to use the Managed Extensibility Framework (Jeremy Likness)
- Creating Awesome Applications when you’re Clueless (Pete Brown)
- OData Visualizer Extension (Gil Fink)
- Great SketchFlow Book Available (Jared Bienz)
- Step by Step Tutorial : Installing Multi-Touch Simulator for Silverlight Phone 7 (Michael Sync)
- Never Underestimate A Well Written Regular Expression, Jodan Terrell
- Extreme Programming (XP) at a Glance – J.D. Meier gives an overview of the Extreme Programming Practices, along with a number of related links to resources about XP
- First round playing with Memcached – Shaun Xu takes a look at the setup and getting started with coding against the Memcached distributed cache running on Windows.
- XNA/C# – A garbage-free StringBuilder Format() method

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