# 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 '19 at 22:19
• @vnp Let me know if you need anything more – Greggz Jan 15 '19 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 '19 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 '19 at 23:23
• Thank you guys for the suggestion I shall try it – Greggz Jan 15 '19 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);

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