WP7/WPF/C#/MEF/Algorithm/and more…

Project Euler problem 61~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of the only ordered set of six cyclic 4-digit numbers: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(recursive_brute_force_to_find_and_construct_chain);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically generate all the number for each type thats within range(1k to 9999) and save them in map
 16:         /// (the Node class is used to make life easier)
 17:         /// then the recursive way is used to find the answer
 18:         /// </summary>
 19:         /// <returns></returns>
 20:         static int recursive_brute_force_to_find_and_construct_chain()
 21:         {
 22:             var map = new List<Node>[]
 23:                 {
 24:                     generate_numbers(triangle, 3),
 25:                     generate_numbers(square, 4),
 26:                     generate_numbers(pentagonal, 5),
 27:                     generate_numbers(hexagonal, 6),
 28:                     generate_numbers(heptagonal, 7),
 29:                     generate_numbers(octagonal, 8)
 30:                 };
 31:             // closure ftw!
 32:             var map_index = map.Length - 1;
 33:             var result = 0;
 34:             var init = 0;
 35:             var set = new HashSet<List<Node>>(); //since there can be only one number from each type
 36:             var found = false; // stops the search, since there is only 1 such set stated by the problem
 37:             Action<Node, int> probe = null;
 38:             probe = (n, i) =>
 39:             {
 40:                 foreach (var nodes in map)
 41:                 {
 42:                     if (set.Contains(nodes))
 43:                         continue;
 44:                     set.Add(nodes);
 45:                     foreach (var node in nodes)
 46:                     {
 47:                         if (n.n1n2 == node.n3n4)
 48:                         {
 49:                             node.uplink = n;
 50:                             if (i == 0 && node.n1n2 == init)
 51:                             {
 52:                                 var walker = node; //johnnie
 53:                                 while (walker != null)
 54:                                 {
 55:                                     result += walker.number;
 56:                                     walker = walker.uplink;
 57:                                 }
 58:                                 found = true;
 59:                             }
 60:                             if (found == false)
 61:                                 probe(node, i - 1);
 62:                         }
 63:                     }
 64:                     set.Remove(nodes);
 65:                 }
 66:             };
 67:             foreach (var nodes in map)
 68:             {
 69:                 set.Add(nodes);
 70:                 foreach (var node in nodes)
 71:                 {
 72:                     init = node.n3n4;
 73:                     if (found == false)
 74:                         probe(node, map_index - 1);
 75:                 }
 76:                 set.Remove(nodes);
 77:             }
 78:             return result;
 79:         }
 80: 
 81:         static List<Node> generate_numbers(Func<int, int> formula, int s)
 82:         {
 83:             var nodes = new List<Node>();
 84:             var num = 0;
 85:             var n = 0;
 86:             int s1, s2;
 87:             while ((num = formula(++n)) <= 9999)
 88:             {
 89:                 if (num >= 1000)
 90:                 {
 91:                     s1 = Math.DivRem(num, 100, out s2);
 92:                     nodes.Add(new Node() { type = s, number = num, nth = n, n1n2 = s1, n3n4 = s2, uplink = null });
 93:                 }
 94:             }
 95:             return nodes;
 96:         }
 97: 
 98:         [DebuggerDisplay("side={type} num={number} n-th={nth}")]
 99:         class Node
100:         {
101:             public int type;
102:             public int number;
103:             public int nth;
104:             public int n1n2;
105:             public int n3n4;
106:             public Node uplink;
107:         }
108: 
109:         static Func<int, int> triangle = (n) => n * (n + 1) / 2;
110:         static Func<int, int> square = (n) => n * n;
111:         static Func<int, int> pentagonal = (n) => n * (3 * n - 1) / 2;
112:         static Func<int, int> hexagonal = (n) => n * (2 * n - 1);
113:         static Func<int, int> heptagonal = (n) => n * (5 * n - 3) / 2;
114:         static Func<int, int> octagonal = (n) => n * (3 * n - 2);
115: 
116:         static Stopwatch stopwatch = new Stopwatch();
117:         static void TestBenchSetup()
118:         {
119:             // Uses the second Core or Processor for the Test
120:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
121:             // Prevents "Normal" processes from interrupting Threads
122:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
123:             // Prevents "Normal" Threads from interrupting this thread
124:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
125:         }
126:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
127:         static void TestBenchLoader(Func<int> test_method)
128:         {
129:             stopwatch.Reset();
130:             stopwatch.Start();
131:             var result = 0;
132:             long avg_tick = 0;
133:             long avg_ms = 0;
134:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
135:             // stabilizes the CPU cache and pipeline.
136:             {
137:                 result = test_method(); // Warmup
138:             }
139:             stopwatch.Stop();
140:             for (int repeat = 0; repeat < 20; ++repeat)
141:             {
142:                 stopwatch.Reset();
143:                 stopwatch.Start();
144:                 result = test_method();
145:                 stopwatch.Stop();
146:                 avg_tick += stopwatch.ElapsedTicks;
147:                 avg_ms += stopwatch.ElapsedMilliseconds;
148:             }
149:             avg_tick = avg_tick / 20;
150:             avg_ms = avg_ms / 20;
151:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
152:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
153:         }
154:     }

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