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<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);
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);
}else if(s.color == 1)
{
s.color = 0;
orientation = Rotate(orientation, false);
}else
{
s.color = 1;
orientation = Rotate(orientation, true);
}

// 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);
}
}
• The question is on the verge of being closed for Lack of concrete context reason. At least, what is squares? Please add all necessary details. – vnp Jan 15 at 22:19
• @vnp Let me know if you need anything more – Greggz Jan 15 at 22:26
• Well now we see that since squares is a Stack, and Stack.Where takes linear time, the entire thing cannot be $O(n)$. Use Set. – vnp Jan 15 at 23:06
• Your code is still incomplete; for example, the Orientation enum is never defined, and the color variable referenced in the if(i==0) block isn't declared. But as @vnp pointed out, your main performance problem is almost certainly the .Where, which may iterate the entire collection. Switching to a Dictionary<Tuple<int, int>, Square>, and using TryGetValue will help you a lot. You may still have issues related to memory allocation as the collections grow very large, however. – benj2240 Jan 15 at 23:23
• Thank you guys for the suggestion I shall try it – Greggz Jan 15 at 23:29

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 < 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);
}else if(s.color == 1)
{
s.color = 0;
orientation = Rotate(orientation, false);
}else
{
s.color = 1;
orientation = Rotate(orientation, true);
}

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