c#/xna/VS2010/and more…

Project Euler problem 79~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The shortest possible secret passcode: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_topological_sorting);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// first did it by hand with a chart which list of all predecessors for each number
 16:         /// and found out this problem can be solved with topological_sorting.
 17:         /// </summary>
 18:         static int using_topological_sorting()
 19:         {
 20:             int number, n1, n2, n3;
 21:             var map = new Dictionary<int, Node>();
 22:             // create a directed graph using use class and dictionary to prevent duplicate
 23:             foreach (var num in File.ReadAllLines("keylog.txt").Select(n => Convert.ToInt32(n)))
 24:             {
 25:                 number = num;
 26:                 number = Math.DivRem(number, 10, out n3);
 27:                 number = Math.DivRem(number, 10, out n2);
 28:                 number = Math.DivRem(number, 10, out n1);
 29: 
 30:                 if (map.ContainsKey(n1) == false)
 31:                     map.Add(n1, new Node(n1));
 32: 
 33:                 if (map.ContainsKey(n2) == false)
 34:                     map.Add(n2, new Node(n2));
 35: 
 36:                 if (map.ContainsKey(n3) == false)
 37:                     map.Add(n3, new Node(n3));
 38: 
 39:                 map[n1].outgoing[n2] = map[n2];
 40:                 map[n1].outgoing[n3] = map[n3];
 41:                 map[n2].incoming[n1] = map[n1];
 42:                 map[n2].outgoing[n3] = map[n3];
 43:                 map[n3].incoming[n1] = map[n1];
 44:                 map[n3].incoming[n2] = map[n2];
 45:             }
 46:             // using Topological sorting(http://en.wikipedia.org/wiki/Topological_sort)
 47:             var s = map.Where(n => n.Value.incoming.Count == 0).Select(n => n.Value).ToList();
 48:             var l = new List<Node>();
 49:             while (s.Count != 0)
 50:             {
 51:                 var n = s[0];
 52:                 s.RemoveAt(0);
 53:                 l.Add(n);
 54:                 foreach (var m in n.outgoing.Values)
 55:                 {
 56:                     m.incoming.Remove(n.value);
 57:                     if (m.incoming.Count == 0)
 58:                         s.Add(m);
 59:                 }
 60:             }
 61:             // transform now sorted list "l" to result as a number
 62:             var result = l[0].value;
 63:             for (int i = 1; i < l.Count; i++)
 64:             {
 65:                 result *= 10;
 66:                 result += l[i].value;
 67:             }
 68:             return result;
 69:         }
 70: 
 71:         class Node
 72:         {
 73:             public int value;
 74:             public Dictionary<int, Node> incoming;
 75:             public Dictionary<int, Node> outgoing;
 76:             public Node(int num)
 77:             {
 78:                 value = num;
 79:                 incoming = new Dictionary<int, Node>();
 80:                 outgoing = new Dictionary<int, Node>();
 81:             }
 82:         }
 83: 
 84:         static Stopwatch stopwatch = new Stopwatch();
 85:         static void TestBenchSetup()
 86:         {
 87:             // Uses the second Core or Processor for the Test
 88:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 89:             // Prevents "Normal" processes from interrupting Threads
 90:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 91:             // Prevents "Normal" Threads from interrupting this thread
 92:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 93:         }
 94:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 95:         static void TestBenchLoader(Func<int> test_method)
 96:         {
 97:             stopwatch.Reset();
 98:             stopwatch.Start();
 99:             var result = 0;
100:             long avg_tick = 0;
101:             long avg_ms = 0;
102:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
103:             // stabilizes the CPU cache and pipeline.
104:             {
105:                 result = test_method(); // Warmup
106:             }
107:             stopwatch.Stop();
108:             for (int repeat = 0; repeat < 20; ++repeat)
109:             {
110:                 stopwatch.Reset();
111:                 stopwatch.Start();
112:                 result = test_method();
113:                 stopwatch.Stop();
114:                 avg_tick += stopwatch.ElapsedTicks;
115:                 avg_ms += stopwatch.ElapsedMilliseconds;
116:             }
117:             avg_tick = avg_tick / 20;
118:             avg_ms = avg_ms / 20;
119:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
120:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
121:         }
122:     }


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