Langton's Ant simulation I created a simple program to simulate the Ant's path.  The Ant moves north, west, east and south. Each time the Anth moves to an "uncharted" location, I build a Square and give it a color. Each time the Ant steps in a square, the square changes color and the Ant rotates 90° and keeps her track. I use a Stack where I push my Squares. The steps list is something I need to keep track of the path of the Ant. I need to find when the Path stabilizes (Roughly after 10000 steps) and the Ant moves in a uniform manner.

It works great until 106 (takes 5 minutes to run). After that it takes more than 14 hours to get to the 107 mark. I don't get why it takes so much more time, shouldn't it just take 10 × time it took to get to 106 iterations assuming my algorithm is o(n)?

I would like to keep the approach single threaded.  What can I optimize?



enum Orientation{
  NORTH, WEST, SOUTH, EAST
}    




public class Square { 
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}




int color = 0;
int x = 0, y = 1;
Stack&lt;Square&gt; squares = new Stack&lt;Square&gt;();
Orientation orientation = Orientation.NORTH;
List&lt;Orientation&gt; steps = new List&lt;Orientation&gt;();
for (int i = 0, counter = 0; i &lt; 10000000; ++i, ++counter)
{

    // First
    if(i == 0)
    {
        squares.Push(new Square() { x = 0, y = 1, color = 1 });
        // Rotate
        orientation = Rotate(orientation, color == 0 ? true : false);
        steps.Add(orientation);
        continue;
    }
    // Move step
    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;

    // Check what the step has
    Square s = squares.Where(square =&gt; square.x == x &amp;&amp; square.y == y).DefaultIfEmpty(null).FirstOrDefault();

    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }

    // 10^6 mark
    if (i == 999999)
    {
            blackSquaresAt100k = squares.Where(sqa =&gt; sqa.color == 1).Count();
            Console.WriteLine(blackSquaresAt100k);
    }

    // 10^7 mark
    if (i == 9999999)
    {
        blackSquaresAt1M = squares.Where(sqa =&gt; sqa.color == 1).Count();
        int totalNrOfBlackSquares = (blackSquaresAt1M - blackSquaresAt100k) * 12 + blackSquaresAt1M;
        Console.WriteLine(totalNrOfBlackSquares);
    }
}
Optimisation


  I use a Stack where I push my Squares.


A stack is the correct data structure when you want last-in-first-out behaviour. Is that the behaviour you need here?


  It works great until 106 (takes 5 minutes to run).


That is a long way from "great". 106 shouldn't take 10 seconds. Use the right data structure for the task, which here is something with amortised constant time insertion and lookup.

Other notes


public class Square { 
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}



Why are all of the fields mutable? Why is there no explicit constructor? Rather than using a 32-bit type to store a single bit and needing to document the legal values, why not use a 1-bit type (i.e. bool isBlack)?




int color = 0;



Does this need such a wide scope?




for (int i = 0, counter = 0; i &lt; 10000000; ++i, ++counter)



What is the purpose of counter? As far as I can tell, it isn't used anywhere.




        squares.Push(new Square() { x = 0, y = 1, color = 1 });



...


        squares.Push(CreateSquare(x, y, 1));



Why the discrepancy?




        orientation = Rotate(orientation, color == 0 ? true : false);



condition ? true : false is an unnecessarily long way of writing condition.




    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;



This is precisely the kind of thing that switch statements were invented to handle.




    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }



Don't repeat yourself. This could be refactored as

    if (s == null)
    {
        s = new Square { x = x, y = y, color = 0 };
        squares.Push(s);
    }

    orientation = Rotate(orientation, s.color == 0);
    steps.Add(orientation);
    s.color = 1 - s.color;





            blackSquaresAt100k = squares.Where(sqa =&gt; sqa.color == 1).Count();



Count has an overload which takes a condition, so enumerable.Where(foo).Count() can be refactored to enumerable.Count(foo).