Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Chris Connett

By: a guest on Oct 20th, 2008  |  syntax: C#  |  size: 7.72 KB  |  views: 56  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }