Langton's Ant simulation

Question

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 10⁶ (takes 5 minutes to run). After that it takes more than 14 hours to get to the 10⁷ mark. I don't get why it takes so much more time, shouldn't it just take 10 × time it took to get to 10⁶ 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<Square> squares = new Stack<Square>();
Orientation orientation = Orientation.NORTH;
List<Orientation> steps = new List<Orientation>();
for (int i = 0, counter = 0; i < 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 => square.x == x && 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 => sqa.color == 1).Count();
            Console.WriteLine(blackSquaresAt100k);
    }

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

Answer 1

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 10⁶ (takes 5 minutes to run).

That is a long way from "great". 10⁶ 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 < 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 => sqa.color == 1).Count();

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