So, here we have another Conway's Game of Life-esque puzzle. These are a bit of a staple, and that is not a criticism, they are often quite fun.

I suspected the bottleneck in my initial solution here was having to do two passes over the elves for each cycle. This was due to the statement...

So, as we don't know how big the arena will get, and we also don't really care about the empty spaces, I store the elves locations in a HashSet<Point> rather than a 2D array which would have to grow on every round.

My first solution was to do a double-pass over all the elves.

• Go through the hashset building up a list of proposed moves for all elves.
• Then, move any elves that didn't have the same proposed move as any other.

Makes sense, right? You can't move an elf on the first pass in case a later elf proposes the same move.

In my data, there were 2,396 elves. Also my part 2 answer ended up being 954 cycles to the end. So:

• Part 1 passes over the elves 47,920 times (as this is the "trial run", only doing 10 cycles.)
• Part 2 passes over the elves 4,571,568 times.

Halving that number, especially for part 2 should have a decent impact. And it did.

The Problem

Consider the first two steps in the example shown in the puzzle. Hashes replaced with numbers for clarity. I've used the hash here to show the collision point.

.....         ..12.
..12.         .....
..3..   -->   ..3..
..#..         ...5.
..45.         ..4..
.....         .....

The description states:

So, in the initial implementation, your would manipulate your "possible moves" list as follows.

• 1 can move north.
• 2 can move north.
• 3 can move south.
• 4 can move north.
• 3 and 4 have proposed moving to the same cell, remove both of their moves from the list.
• 5 can move north.

Then, you cycle through the elves again and if they have a possible move in the list, you update their position.

The Optimisation

The one-pass solution is quite simple. If you realise two elves proposing the same move will be coming from opposite directions.

In the one and only pass over the elves, you don't maintain a "possible moves" list, you just move each elf as you get to it...

• Try to move 1 north. Done.
• Try to move 2 north. Done.
• Try to move 3 south. Done.
• Try to move 4 north. On no, collision. Bounce them! Don't move 4, but then push 3 back the way 4 was trying to move, i.e. move 3 back north.
• 5 can move north.

This not only halves the number of iterations over the elves, but also removed 3 temporary hashsets from my method, so fewer allocations also which is another win.

Original Method

protected int RunSimulationStep()
{
    // The 3 temporary HashSets I can ditch
    _visited.Clear();

    _blocked.Clear();

    _proposedMoves.Clear();

    // The new positions of the elves after this round
    var elves = new HashSet<Point>(SetMaxSize);

    foreach (var elf in _elves)
    {
        // Get the elf's proposed move
        var proposedMove = GetProposedMove(elf);

        _proposedMoves.Add(elf, proposedMove);

        // Elf happy where he is, add his current position to the new positions set
        if (proposedMove == null)
        {
            elves.Add(elf);

            continue;
        }

        // An elf has already proposed here, so add to the blocked list
        if (_visited.Contains(proposedMove))
        {
            _blocked.Add(proposedMove);

            continue;
        }
        
        // No elf has proposed here, so add as a potential move
        _visited.Add(proposedMove);
    }

    var moved = 0;

    foreach (var elf in _elves)
    {
        // Get the elf's proposed move (again)
        var proposedMove = _proposedMoves[elf];

        // Already added in first pass through
        if (proposedMove == null)
        {
            continue;
        }

        // Move was blocked, add original position to set
        if (_blocked.Contains(proposedMove))
        {
            elves.Add(elf);

            continue;
        }

        // This elf can move, so add new position to set
        elves.Add(proposedMove);

        moved++;
    }

    // Replace the current elf positions with the new ones
    _elves = elves;

    RotateEvaluations();

    return moved;
}

New Method

protected int RunSimulationStep()
{
    // The new positions of the elves after this round
    var elves = new HashSet<Point>(SetMaxSize);

    var moved = 0;

    foreach (var elf in _elves)
    {
        var proposedMove = GetProposedMove(elf);

        // Elf happy where he is, add his current position to the new positions set
        if (proposedMove == null)
        {
            elves.Add(elf);

            continue;
        }

        // Try to move the elf, whoops collision!
        if (elves.Contains(elf + proposedMove))
        {
            // Add his current position to the new positions set as he now can't move
            elves.Add(elf);

            /* Here is the bounce!
            // Remove the elf he collided with from the new positions set
            elves.Remove(elf + proposedMove);

            // Add the elf he collided with back to the new positions set in his original position
            elves.Add(elf + proposedMove + proposedMove);
            */

            moved--;

            continue;
        }

        // Move the elf
        elves.Add(elf + proposedMove);

        moved++;
    }

    // Replace the current elf positions with the new ones
    _elves = elves;

    RotateEvaluations();

    return moved;
}

Pretty cool, I thought.