XNA/3D/C#/Programmer/And more…

Project Euler problem 81~
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(half_ass_a_star_and_Dijkstra_tarball);
  9:             TestBenchLoader(using_DP_with_memoization);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         static int using_DP_with_memoization()
 16:         {
 17:             var len = 80;
 18:             var map = new int[len, len];
 19:             var cache = new int[len, len];
 20:             var row = 0;
 21:             foreach (var line in File.ReadAllLines("matrix.txt"))
 22:             {
 23:                 var col = 0;
 24:                 foreach (var num in line.Split(new char[] { ',' }))
 25:                 {
 26:                     cache[row, col] = -1;
 27:                     map[row, col] = Convert.ToInt32(num);
 28:                     col++;
 29:                 }
 30:                 row++;
 31:             }
 32:             Func<int, int, int> min_path = null;
 33:             min_path = (r, c) =>
 34:                 {
 35:                     if (cache[r, c] != -1)
 36:                         return cache[r, c];
 37:                     else if (r == len - 1 && c == len - 1)
 38:                         return (cache[r, c] = map[r, c]);
 39:                     else if (r == len - 1)
 40:                         return (cache[r, c] = map[r, c] + min_path(r, c + 1));
 41:                     else if (c == len - 1)
 42:                         return (cache[r, c] = map[r, c] + min_path(r + 1, c));
 43:                     else
 44:                         return (cache[r, c] = map[r, c] + Math.Min(min_path(r, c + 1), min_path(r + 1, c)));
 45:                 };
 46:             return min_path(0, 0);
 47:         }
 48: 
 49:         /// <summary>
 50:         /// was trying to implement A* search algorithm(http://en.wikipedia.org/wiki/A*_search_algorithm)
 51:         /// but i cant think of a meaningful h(x) (heuristic_estimate_of_distance), so i guess its more of 
 52:         /// Dijkstra's algorithm, but yet the code structure followed the pseudo code of A* search on wiki page.
 53:         /// some crucial mechanism are not implemented (namely the tentative_g_score smaller than g_score[y])
 54:         /// </summary>
 55:         static int half_ass_a_star_and_Dijkstra_tarball()
 56:         {
 57:             var len = 80;
 58:             var map = new int[len, len];
 59:             var row = 0;
 60:             foreach (var line in File.ReadAllLines("matrix.txt"))
 61:             {
 62:                 var col = 0;
 63:                 line.Split(new char[] { ',' }).Select(c => Convert.ToInt32(c)).ToList().ForEach(n => map[row, col++] = n);
 64:                 row++;
 65:             }
 66:             var start = new Node(0, 0, map[0, 0]);
 67:             var goal = new Node(len - 1, len - 1, map[len - 1, len - 1]);
 68:             var openset = new PriorityQueue();
 69: 
 70:             start.g_score = 0;
 71:             start.h_score = heuristic_estimate_of_distance(start, goal, map);
 72:             start.f_score = start.h_score;
 73:             openset.Push(start);
 74: 
 75:             while (openset.IsEmpty() == false)
 76:             {
 77:                 var x = openset.PopMinimum();
 78:                 if (x.m_row == goal.m_row && x.m_col == goal.m_col)
 79:                 {
 80:                     var cost = 0;
 81:                     while (x != null)
 82:                     {
 83:                         cost += x.m_value;
 84:                         x = x.came_from;
 85:                     }
 86:                     return cost;
 87:                 }
 88: 
 89:                 foreach (var y in get_neighbors(x, map, len))
 90:                 {
 91:                     if (openset.Exists(y) == false)
 92:                     {
 93:                         y.came_from = x;
 94:                         y.g_score = x.g_score + x.m_value + y.m_value;
 95:                         y.h_score = heuristic_estimate_of_distance(y, goal, map);
 96:                         y.f_score = y.g_score + y.h_score;
 97:                         openset.Push(y);
 98:                     }
 99:                 }
100:             }
101:             return 0;
102:         }
103: 
104:         /// <summary>
105:         /// it has to be admissible heuristic(http://en.wikipedia.org/wiki/A*_search_algorithm)
106:         /// great! if i already know such way, wouldnt it be faster if i just use that instead. o.O
107:         /// </summary>
108:         static int heuristic_estimate_of_distance(Node x, Node y, int[,] map)
109:         {
110:             return x.m_value + y.m_value; // jetpack version, x can just jump to y
111:         }
112: 
113:         static List<Node> get_neighbors(Node node, int[,] map, int len)
114:         {
115:             var neighbors = new List<Node>();
116:             var row = node.m_row;
117:             var col = node.m_col;
118: 
119:             if (col + 1 < len)
120:                 neighbors.Add(new Node(row, col + 1, map[row, col + 1]));
121:             if (row + 1 < len)
122:                 neighbors.Add(new Node(row + 1, col, map[row + 1, col]));
123: 
124:             return neighbors;
125:         }
126: 
127:         [DebuggerDisplay("{m_value} ({m_row},{m_col}) f:{f_score}")]
128:         class Node : IComparable<Node>
129:         {
130:             public int m_value;
131:             public int m_row;
132:             public int m_col;
133:             public int g_score;
134:             public int h_score;
135:             public int f_score;
136:             public Node came_from;
137:             public Node() { g_score = 0; h_score = 0; f_score = 0; came_from = null; }
138:             public Node(int row, int col, int value) : this() { m_row = row; m_col = col; m_value = value; }
139:             public int CompareTo(Node node) { return f_score > node.f_score ? 1 : f_score < node.f_score ? -1 : 0; }
140:         }
141: 
142:         /// <summary>
143:         /// it is like a very ghetto priority queue implementation using minimum-at-top binary heap, which is used
144:         /// by the A* Search way
145:         /// </summary>
146:         class PriorityQueue
147:         {
148:             List<Node> m_store;
149:             int[,] m_nodeMap; //this is used for faster Exists look up
150:             public PriorityQueue()
151:             {
152:                 m_store = new List<Node>() { null }; // filler, 1st element is not used
153:                 m_nodeMap = new int[80, 80];
154:             }
155:             public void Push(Node item)
156:             {
157:                 m_store.Add(item);
158:                 m_nodeMap[item.m_row, item.m_col] = 1;
159:                 var index = m_store.Count - 1;
160:                 var parent_index = 0;
161:                 while (index != 1)
162:                 {
163:                     parent_index = index / 2;
164:                     var parent = m_store[parent_index];
165:                     if (item.CompareTo(parent) < 0)
166:                     {
167:                         m_store[parent_index] = item;
168:                         m_store[index] = parent;
169:                         index = parent_index;
170:                     }
171:                     else
172:                         break;
173:                 }
174:             }
175:             public Node PopMinimum()
176:             {
177:                 var removed = m_store[1];
178:                 var len = m_store.Count - 1;
179:                 var current = 1;
180:                 var left = 1;
181:                 var right = 1;
182:                 var min = 1;
183:                 m_store[1] = m_store[len];
184:                 do
185:                 {
186:                     left = 2 * current;
187:                     right = 2 * current + 1;
188:                     min = left <= len && m_store[left].CompareTo(m_store[current]) < 0 ? left : min;
189:                     min = right <= len && m_store[right].CompareTo(m_store[min]) < 0 ? right : min;
190: 
191:                     if (min != current)
192:                     {
193:                         var tmp = m_store[current];
194:                         m_store[current] = m_store[min];
195:                         m_store[min] = tmp;
196:                         current = min;
197:                     }
198:                     else
199:                         break;
200:                 } while (true);
201:                 m_nodeMap[removed.m_row, removed.m_col] = -1;
202:                 m_store.RemoveAt(len);
203:                 return removed;
204:             }
205:             public bool IsEmpty() { return m_store.Count == 1; }
206:             public bool Exists(Node node) { return m_nodeMap[node.m_row, node.m_col] == 1; }
207:         }
208: 
209:         static Stopwatch stopwatch = new Stopwatch();
210:         static void TestBenchSetup()
211:         {
212:             // Uses the second Core or Processor for the Test
213:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
214:             // Prevents "Normal" processes from interrupting Threads
215:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
216:             // Prevents "Normal" Threads from interrupting this thread
217:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
218:         }
219:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
220:         static void TestBenchLoader(Func<int> test_method)
221:         {
222:             stopwatch.Reset();
223:             stopwatch.Start();
224:             long result = 0;
225:             long avg_tick = 0;
226:             long avg_ms = 0;
227:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
228:             // stabilizes the CPU cache and pipeline.
229:             {
230:                 result = test_method(); // Warmup
231:             }
232:             stopwatch.Stop();
233:             for (int repeat = 0; repeat < 20; ++repeat)
234:             {
235:                 stopwatch.Reset();
236:                 stopwatch.Start();
237:                 result = test_method();
238:                 stopwatch.Stop();
239:                 avg_tick += stopwatch.ElapsedTicks;
240:                 avg_ms += stopwatch.ElapsedMilliseconds;
241:             }
242:             avg_tick = avg_tick / 20;
243:             avg_ms = avg_ms / 20;
244:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
245:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
246:         }
247:     }

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