lawl~

Project Euler problem 83~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The minimal path sum, in matrix.txt: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_Dijkstra_s_algorithm_with_priority_queue);
  9:             
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// based on the pseudocode on wiki page(http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
 16:         /// </summary>
 17:         static int using_Dijkstra_s_algorithm_with_priority_queue()
 18:         {
 19:             var len = 80;
 20:             var node_map = new Node[len, len];
 21:             var queue = new PriorityQueue(len * len);
 22:             Node source = null;
 23:             Node goal = null;
 24:             var row = 0;
 25:             var col = 0;
 26:             foreach (var line in File.ReadAllLines("matrix.txt"))
 27:             {
 28:                 col = 0;
 29:                 foreach (var num in line.Split(new char[] { ',' }))
 30:                 {
 31:                     var node = new Node(Convert.ToInt32(num)) { row = row, col = col };
 32:                     if (row == 0 && col == 0) source = node;
 33:                     if (row == len - 1 && col == len - 1) goal = node;
 34:                     // node map is mainly used to get neighbors
 35:                     node_map[row, col] = node;
 36:                     queue.Enqueue(node);
 37:                     col++;
 38:                 }
 39:                 row++;
 40:             }
 41:             // set the source's distance to zero to kick start the process
 42:             queue.Update(source, 0);
 43:             // code for getting neighbor, using closure with the neighbor_list to make life a little easier
 44:             var neighbor_list = new Node[4]; // 0:left 1:up 2:right 3:down
 45:             Action<Node> prepare_neighbor_list = n =>
 46:                 {
 47:                     neighbor_list[0] = n.col - 1 < 0 ? null : node_map[n.row, n.col - 1];
 48:                     neighbor_list[1] = n.row - 1 < 0 ? null : node_map[n.row - 1, n.col];
 49:                     neighbor_list[2] = n.col + 1 >= len ? null : node_map[n.row, n.col + 1];
 50:                     neighbor_list[3] = n.row + 1 >= len ? null : node_map[n.row + 1, n.col];
 51:                 };
 52:             var total = 0;
 53:             while (queue.IsEmpty() == false)
 54:             {
 55:                 var u = queue.DequeueMin();
 56:                 if (u.distance == int.MaxValue)
 57:                     break; // all remaining vertices are inaccessible from source
 58:                 if (u == goal)
 59:                 {
 60:                     while (u != null)
 61:                     {
 62:                         total += u.cost;
 63:                         u = u.previous;
 64:                     }
 65:                     break;
 66:                 }
 67:                 // call this method before using neighbor_list array
 68:                 prepare_neighbor_list(u);
 69:                 foreach (var v in neighbor_list)
 70:                 {
 71:                     if (v == null)
 72:                         continue; // like when u is edge cell in the matrix
 73: 
 74:                     var alt = u.distance + u.cost + v.cost;
 75:                     if (alt < v.distance)
 76:                     {
 77:                         v.previous = u;
 78:                         queue.Update(v, alt);
 79:                     }
 80:                 }
 81:             }
 82:             return total;
 83:         }
 84:         
 85:         [DebuggerDisplay("d:{distance} c:{cost} i:{index}")]
 86:         class Node
 87:         {
 88:             public int cost;
 89:             public int distance = int.MaxValue; // so its like infinity 
 90:             public int row;
 91:             public int col;
 92:             public int index; // so with index, searching the node in the array when update can be O(1)
 93:             public Node previous = null;
 94:             public Node(int cost) { this.cost = cost; }
 95:         }
 96:         /// <summary>
 97:         /// a much better implementation of PriorityQueue this time :P.
 98:         /// </summary>
 99:         class PriorityQueue
100:         {
101:             Node[] array;
102:             int count;
103:             Func<int, int> Left = i => 2 * i;
104:             Func<int, int> Right = i => 2 * i + 1;
105: 
106:             public PriorityQueue(int size)
107:             {
108:                 array = new Node[size + 1];
109:                 count = 1; // rebase index to start with 1
110:             }
111: 
112:             public void Enqueue(Node new_node)
113:             {
114:                 var i = count;
115:                 array[i] = new_node;
116:                 array[i].index = i;
117:                 count++;
118:                 while (i > 1 && array[i].distance < array[i / 2].distance)
119:                 {
120:                     Swap(i / 2, i); // swap new_node's and its parent's position since new_node has smaller dist
121:                     i /= 2;
122:                 }
123:             }
124:             public Node DequeueMin()
125:             {
126:                 // save the minimum node to be returned later
127:                 var node = array[1];
128:                 node.index = -1;
129:                 // swap the last node to root(array[1]) position, also updates count
130:                 array[1] = array[--count];
131:                 array[1].index = 1;
132:                 array[count] = null;
133:                 var i = 1;
134:                 var min = 0;
135:                 // bubble down the last_node til correct position
136:                 while (i < count)
137:                 {
138:                     min = i;
139:                     if (Left(i) < count && array[Left(i)].distance < array[min].distance)
140:                         min = Left(i);
141:                     if (Right(i) < count && array[Right(i)].distance < array[min].distance)
142:                         min = Right(i);
143: 
144:                     if (min != i)
145:                     {
146:                         Swap(i, min); // swap the node with smaller one of its children
147:                         i = min;
148:                     }
149:                     else
150:                         break;
151:                 }
152:                 return node;
153:             }
154:             public void Update(Node toUpdate, int newDist) // only works if node's distnace becomes smaller
155:             {
156:                 toUpdate.distance = newDist;
157:                 var i = toUpdate.index;
158:                 while (i > 1 && array[i].distance < array[i / 2].distance)
159:                 {
160:                     Swap(i / 2, i); // swap toUpdate node's and its parent's position since toUpdate node has smaller dist
161:                     i /= 2;
162:                 }
163:             }
164:             void Swap(int index1, int index2)
165:             {
166:                 var tmp = array[index1];
167:                 array[index1] = array[index2];
168:                 array[index1].index = index1;
169:                 array[index2] = tmp;
170:                 array[index2].index = index2;
171:             }
172:             public bool IsEmpty() { return count == 1; }
173:         }
174: 
175:         static Stopwatch stopwatch = new Stopwatch();
176:         static void TestBenchSetup()
177:         {
178:             // Uses the second Core or Processor for the Test
179:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
180:             // Prevents "Normal" processes from interrupting Threads
181:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
182:             // Prevents "Normal" Threads from interrupting this thread
183:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
184:         }
185:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
186:         static void TestBenchLoader(Func<int> test_method)
187:         {
188:             stopwatch.Reset();
189:             stopwatch.Start();
190:             long result = 0;
191:             long avg_tick = 0;
192:             long avg_ms = 0;
193:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
194:             // stabilizes the CPU cache and pipeline.
195:             {
196:                 result = test_method(); // Warmup
197:             }
198:             stopwatch.Stop();
199:             for (int repeat = 0; repeat < 20; ++repeat)
200:             {
201:                 stopwatch.Reset();
202:                 stopwatch.Start();
203:                 result = test_method();
204:                 stopwatch.Stop();
205:                 avg_tick += stopwatch.ElapsedTicks;
206:                 avg_ms += stopwatch.ElapsedMilliseconds;
207:             }
208:             avg_tick = avg_tick / 20;
209:             avg_ms = avg_ms / 20;
210:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
211:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
212:         }
213:     }

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