• Sign Up
• Login
• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
42%
SHARE
TWEET

# Chris Connett

a guest Oct 20th, 2008 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. using System;
2. using System.Collections.Generic;
3. using System.Text;
4.
5. namespace RobotSolver
6. {
7.   class Program
8.   {
9.     static void Main(string[] args)
10.     {
11.       new Solver().Go();
12.     }
13.   }
14.
15.   /// <summary>
16.   /// Solves the light-bot game
17.   /// </summary>
18.   class Solver
19.   {
20.     // The commands the robot can do
21.     enum Cmd { Nothing, Call1, Call2, Jump, Left, Right, Light, Forwards };
22.
23.     // ****** Level 11 \/ \/ \/
24.     string[] grid =
25.     {
26.     // 01234567   <- x
27.       "33333333", // y=0
28.       "22222222", //   1
29.       "11111111", //   2
30.       "        ", //   3
31.       "11111111", //   4
32.       "        ", //   5
33.       "11111111", //   6
34.       "        "  //   7
35.     };
36.     int[] lx = {1,2,3,4,5,6,7,
37.                 1,2,3,4,5,6,7,8,
38.                 1,2,3,4,5,6,7,8,
39.                 1,2,3,4,5,6,7,8,
40.                 1,2,3,4,5,6,7,8,
41.                 1,2,3,4,5,6,7,8,
42.     }; // light x locations
43.     int[] ly = {7,7,7,7,7,7,7,
44.                 6,6,6,6,6,6,6,6,
45.                 5,5,5,5,5,5,5,5,
46.                 4,4,4,4,4,4,4,4,
47.                 3,3,3,3,3,3,3,3,
48.                 2,2,2,2,2,2,2,2,
49.     }; // light y locations
50.     int startrx = 0, startry = 6, startra = 1;  // facing E on the grid
51.     // ****** Level 10 /\ /\ /\
52.
53.     bool[] l = new bool[47]; // light lit status
54.     int rx, ry, ra; // current robot x,y,angle
55.     Int64 tries = 0; // tries counter
56.
57.     int best = 0; // number of lights turned on by the best
58.                           // solution seen so far
59.     int newBest = 0;
60.
61.     string Directions(Cmd[] list)
62.     {
63.       string s = "";
64.       for (int i = 0; i < 28; i++)
65.         s += list[i].ToString() + (i==11 || i==19 || i==27 ? "\n" : ",");
66.       return s;
67.     }
68.
69.     void Reset()
70.     {
71.       for (int i = 0; i < l.Length; i++) {
72.         l[i] = false;
73.       }
74.       rx = startrx;
75.       ry = startry;
76.       ra = startra;
77.     }
78.
79.     int Height()
80.     {
81.       if (' ' == grid[ry][rx]) return 0;
82.       return grid[ry][rx] - '0';
83.     }
84.
85.     void Clip()
86.     {
87.       if (rx < 0) rx = 0;
88.       if (rx > 7) rx = 7;
89.       if (ry < 0) ry = 0;
90.       if (ry > 7) ry = 7;
91.     }
92.
93.     void Move()
94.     {
95.       if (ra == 0) ry--; // N
96.       if (ra == 1) rx++; // E
97.       if (ra == 2) ry++; // S
98.       if (ra == 3) rx--; // W
99.     }
100.
101.     void Exec(Cmd c)
102.     {
103.       int oldx = rx;
104.       int oldy = ry;
105.       int oldht = Height();
106.       if (c == Cmd.Forwards)
107.       {
108.         Move();
109.         Clip();
110.         // can't climb/fall
111.         if (oldht != Height())
112.         {
113.           rx = oldx;
114.           ry = oldy;
115.         }
116.       }
117.       if (c == Cmd.Jump)
118.       {
119.         Move();
120.         Clip();
121.         // must climb one level or fall any levels
122.         int newht = Height();
123.         if (!(newht == oldht + 1 || newht < oldht))
124.         {
125.           rx = oldx;
126.           ry = oldy;
127.         }
128.       }
129.       if (c == Cmd.Left)
130.       {
131.         ra--;
132.         if (ra < 0) ra = 3;
133.       }
134.       if (c == Cmd.Right)
135.       {
136.         ra++;
137.         if (ra > 3) ra = 0;
138.       }
139.       if (c == Cmd.Light)
140.       {
141.         for (int i = 0; i < l.Length; i++) {
142.           if (rx == lx[i] && ry == ly[i]) {
143.             l[i] = !l[i];
144.           }
145.         }
146.       }
147.     }
148.
149.     void TryPath(Cmd[] f)
150.     {
151.       tries++;
152.       Reset();
153.
154.       int index = 0;
155.       List<int> stacki = new List<int>();
156.       bool done = false;
157.       do
158.       {
159.         Cmd c = f[index];
160.
161.         // call other functions
162.         if (c == Cmd.Call1)
163.         {
164.           stacki.Add(index);
165.           index = 12;
166.         }
167.         if (c == Cmd.Call2)
168.         {
169.           stacki.Add(index);
170.           index = 20;
171.         }
172.         if (c != Cmd.Call1 && c != Cmd.Call2)
173.         {
174.           // run it
175.           Exec(c);
176.
177.           // move next
178.           index++;
179.
180.           while (index == 20 || index == 28) // finished f1 or f2
181.           {
182.             // pop
183.             index = stacki[stacki.Count - 1] + 1;
184.             stacki.RemoveAt(stacki.Count - 1);
185.           }
186.           if (index == 12) done = true; // did it just end?
187.         }
188.       } while (!done && stacki.Count < 10);
189.
190.       if (stacki.Count >= 10) Reset(); // if it looped then
191.     }
192.
193.     public int CountTrue(bool[] l) {
194.       int count = 0;
195.       for (int i = 0; i < l.Length; i++) {
196.         if (l[i]) {
197.           count += 1;
198.         }
199.       }
200.       return count;
201.     }
202.
203.     public void Go()
204.     {
205.       Console.WriteLine("Begin: " + DateTime.Now.ToString());
206.
207.       Random r = new Random();
208.       int update_counter = 0;
209.       bool done = false;
210.       int i, j, morphs, successrate, morphcount, freshrate, morphrate, spreadrate;
211.       Cmd[] morphgood = new Cmd[28];
212.
213.       Cmd[][] f;
214.       f = new Cmd[1000][]; // 1000 members of this generation
215.       for (j = 0; j < 1000; j++) f[j] = new Cmd[28];
216.
217.       // Start with a random generation
218.       for (j = 0; j < 1000; j++)
219.       {
220.         for (i = 0; i < 27; i++)
221.         {
222.           f[j][i] = (Cmd)r.Next(8);
223.         }
224.       }
225.
226.       bool[] goodones = new bool[1000]; // which ones in that generation were any good
227.
228.       do
229.       { // Loop through a single generation
230.         best = newBest;
231.
232.         // Go through all members of this generation
233.         successrate = 0;
234.         for (j = 0; j < 1000; j++)
235.         {
236.           // try it
237.           TryPath(f[j]);
238.
239.           int count = CountTrue(l);
240.           //Console.WriteLine(count);
241.
242.           goodones[j] = (count > best); // is this one any good?
243.           if (count > best && count > newBest) {
244.             newBest = count;
245.           }
246.           if (goodones[j]) // It's a half winner
247.           {
248.             successrate++;
249.           }
250.
251.           if (count == l.Length) // Found a winner!
252.           {
253.             done = true;
254.             Console.WriteLine("\nWINNER:\n{0}", Directions(f[j]));
255.           }
256.         }
257.
258.         // Randomise the generation
259.         morphcount = 0;
260.         freshrate = 0;
261.         morphrate = 0;
262.         spreadrate = 0;
263.         for (j = 0; j < 1000; j++)
264.         {
265.           if (goodones[j])
266.           { // If it's half good, then morph it
267.             // before i morph it, copy it for later morphing
268.             Array.Copy(f[j], morphgood, 28);
269.
270.             morphs = r.Next(4); // how many fields to morph
271.             for (i = 0; i < morphs; i++) // morph X entries
272.             {
273.               f[j][r.Next(28)] = (Cmd)r.Next(8);
274.             }
275.             morphrate++;
276.             morphcount = 10; // morph this one over the next 10 crap ones
277.           }
278.           else // If its crap, then overwrite it
279.           {
280.             // Shall i spread and morph a previous half-good one into this slot?
281.             if (morphcount > 0)
282.             {
283.               Array.Copy(morphgood, f[j], 28); // copy it into this slot
284.               morphs = r.Next(4); // how many fields to morph
285.               for (i = 0; i < morphs; i++) // morph X entries
286.               {
287.                 f[j][r.Next(28)] = (Cmd)r.Next(8);
288.               }
289.               morphcount--;
290.               spreadrate++;
291.             }
292.             else
293.             { // just totally regenerate it
294.               for (i = 0; i < 27; i++)
295.               {
296.                 f[j][i] = (Cmd)r.Next(8);
297.               }
298.               freshrate++;
299.             }
300.           }
301.         }
302.
303.         // Update the user
304.         update_counter++;
305.         if (update_counter >= 100)
306.         {
307.           update_counter = 0;
308.           Console.Write("\rTries: {0:#,0} Halfway: {1} Fresh: {2} Morphed: {3} Spread: {4} Best: {5}", tries, successrate, freshrate, morphrate, spreadrate, best);
309.         }
310.
311.       } while (!done);
312.
313.       Console.WriteLine("End: " + DateTime.Now.ToString());
314.     }
315.   }
316. }
RAW Paste Data
Top