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());
    }
  }
}