Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Text;
- namespace RobotSolver
- {
- class Program
- {
- static void Main(string[] args)
- {
- new Solver().Go();
- }
- }
- /// <summary>
- /// Solves the light-bot game
- /// </summary>
- class Solver
- {
- // The commands the robot can do
- enum Cmd { Nothing, Call1, Call2, Jump, Left, Right, Light, Forwards };
- // ****** Level 11 \/ \/ \/
- string[] grid =
- {
- // 01234567 <- x
- "33333333", // y=0
- "22222222", // 1
- "11111111", // 2
- " ", // 3
- "11111111", // 4
- " ", // 5
- "11111111", // 6
- " " // 7
- };
- int[] lx = {1,2,3,4,5,6,7,
- 1,2,3,4,5,6,7,8,
- 1,2,3,4,5,6,7,8,
- 1,2,3,4,5,6,7,8,
- 1,2,3,4,5,6,7,8,
- 1,2,3,4,5,6,7,8,
- }; // light x locations
- int[] ly = {7,7,7,7,7,7,7,
- 6,6,6,6,6,6,6,6,
- 5,5,5,5,5,5,5,5,
- 4,4,4,4,4,4,4,4,
- 3,3,3,3,3,3,3,3,
- 2,2,2,2,2,2,2,2,
- }; // light y locations
- int startrx = 0, startry = 6, startra = 1; // facing E on the grid
- // ****** Level 10 /\ /\ /\
- bool[] l = new bool[47]; // light lit status
- int rx, ry, ra; // current robot x,y,angle
- Int64 tries = 0; // tries counter
- int best = 0; // number of lights turned on by the best
- // solution seen so far
- int newBest = 0;
- string Directions(Cmd[] list)
- {
- string s = "";
- for (int i = 0; i < 28; i++)
- s += list[i].ToString() + (i==11 || i==19 || i==27 ? "\n" : ",");
- return s;
- }
- void Reset()
- {
- for (int i = 0; i < l.Length; i++) {
- l[i] = false;
- }
- rx = startrx;
- ry = startry;
- ra = startra;
- }
- int Height()
- {
- if (' ' == grid[ry][rx]) return 0;
- return grid[ry][rx] - '0';
- }
- void Clip()
- {
- if (rx < 0) rx = 0;
- if (rx > 7) rx = 7;
- if (ry < 0) ry = 0;
- if (ry > 7) ry = 7;
- }
- void Move()
- {
- if (ra == 0) ry--; // N
- if (ra == 1) rx++; // E
- if (ra == 2) ry++; // S
- if (ra == 3) rx--; // W
- }
- void Exec(Cmd c)
- {
- int oldx = rx;
- int oldy = ry;
- int oldht = Height();
- if (c == Cmd.Forwards)
- {
- Move();
- Clip();
- // can't climb/fall
- if (oldht != Height())
- {
- rx = oldx;
- ry = oldy;
- }
- }
- if (c == Cmd.Jump)
- {
- Move();
- Clip();
- // must climb one level or fall any levels
- int newht = Height();
- if (!(newht == oldht + 1 || newht < oldht))
- {
- rx = oldx;
- ry = oldy;
- }
- }
- if (c == Cmd.Left)
- {
- ra--;
- if (ra < 0) ra = 3;
- }
- if (c == Cmd.Right)
- {
- ra++;
- if (ra > 3) ra = 0;
- }
- if (c == Cmd.Light)
- {
- for (int i = 0; i < l.Length; i++) {
- if (rx == lx[i] && ry == ly[i]) {
- l[i] = !l[i];
- }
- }
- }
- }
- void TryPath(Cmd[] f)
- {
- tries++;
- Reset();
- int index = 0;
- List<int> stacki = new List<int>();
- bool done = false;
- do
- {
- Cmd c = f[index];
- // call other functions
- if (c == Cmd.Call1)
- {
- stacki.Add(index);
- index = 12;
- }
- if (c == Cmd.Call2)
- {
- stacki.Add(index);
- index = 20;
- }
- if (c != Cmd.Call1 && c != Cmd.Call2)
- {
- // run it
- Exec(c);
- // move next
- index++;
- while (index == 20 || index == 28) // finished f1 or f2
- {
- // pop
- index = stacki[stacki.Count - 1] + 1;
- stacki.RemoveAt(stacki.Count - 1);
- }
- if (index == 12) done = true; // did it just end?
- }
- } while (!done && stacki.Count < 10);
- if (stacki.Count >= 10) Reset(); // if it looped then
- }
- public int CountTrue(bool[] l) {
- int count = 0;
- for (int i = 0; i < l.Length; i++) {
- if (l[i]) {
- count += 1;
- }
- }
- return count;
- }
- public void Go()
- {
- Console.WriteLine("Begin: " + DateTime.Now.ToString());
- Random r = new Random();
- int update_counter = 0;
- bool done = false;
- int i, j, morphs, successrate, morphcount, freshrate, morphrate, spreadrate;
- Cmd[] morphgood = new Cmd[28];
- Cmd[][] f;
- f = new Cmd[1000][]; // 1000 members of this generation
- for (j = 0; j < 1000; j++) f[j] = new Cmd[28];
- // Start with a random generation
- for (j = 0; j < 1000; j++)
- {
- for (i = 0; i < 27; i++)
- {
- f[j][i] = (Cmd)r.Next(8);
- }
- }
- bool[] goodones = new bool[1000]; // which ones in that generation were any good
- do
- { // Loop through a single generation
- best = newBest;
- // Go through all members of this generation
- successrate = 0;
- for (j = 0; j < 1000; j++)
- {
- // try it
- TryPath(f[j]);
- int count = CountTrue(l);
- //Console.WriteLine(count);
- goodones[j] = (count > best); // is this one any good?
- if (count > best && count > newBest) {
- newBest = count;
- }
- if (goodones[j]) // It's a half winner
- {
- successrate++;
- }
- if (count == l.Length) // Found a winner!
- {
- done = true;
- Console.WriteLine("\nWINNER:\n{0}", Directions(f[j]));
- }
- }
- // Randomise the generation
- morphcount = 0;
- freshrate = 0;
- morphrate = 0;
- spreadrate = 0;
- for (j = 0; j < 1000; j++)
- {
- if (goodones[j])
- { // If it's half good, then morph it
- // before i morph it, copy it for later morphing
- Array.Copy(f[j], morphgood, 28);
- morphs = r.Next(4); // how many fields to morph
- for (i = 0; i < morphs; i++) // morph X entries
- {
- f[j][r.Next(28)] = (Cmd)r.Next(8);
- }
- morphrate++;
- morphcount = 10; // morph this one over the next 10 crap ones
- }
- else // If its crap, then overwrite it
- {
- // Shall i spread and morph a previous half-good one into this slot?
- if (morphcount > 0)
- {
- Array.Copy(morphgood, f[j], 28); // copy it into this slot
- morphs = r.Next(4); // how many fields to morph
- for (i = 0; i < morphs; i++) // morph X entries
- {
- f[j][r.Next(28)] = (Cmd)r.Next(8);
- }
- morphcount--;
- spreadrate++;
- }
- else
- { // just totally regenerate it
- for (i = 0; i < 27; i++)
- {
- f[j][i] = (Cmd)r.Next(8);
- }
- freshrate++;
- }
- }
- }
- // Update the user
- update_counter++;
- if (update_counter >= 100)
- {
- update_counter = 0;
- Console.Write("\rTries: {0:#,0} Halfway: {1} Fresh: {2} Morphed: {3} Spread: {4} Best: {5}", tries, successrate, freshrate, morphrate, spreadrate, best);
- }
- } while (!done);
- Console.WriteLine("End: " + DateTime.Now.ToString());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement