Now, this puzzle has a couple of interesting optimisations.

It is essentially Tetris without the rotation element. And slightly different "ominoes".

I started by trying to model the playing field and the "pyronimoes" in a 2D array. This should have been fine, but I found it a bit clumsy for some reason. No performance concerns at this point, just trying to make my life easier.

So, bit twiddling it is.

The playing field is small, so each row can easily be stored in a byte. I use integers just as I'm not sure there's an advantage to using bytes on a 64-bit computer.

Each filled cell can now be represented by a 1.

Representing the pyronimoes can now be done as follows in memory...

private readonly int[][] _rocks =
{
    /*
     ....
     ....
     ....
     ####
     */
    new[]
    {
        0b0011110
    },
    /*
     ....
     .#..
     ###.
     .#..
     */
    new[]
    {
        0b0001000,
        0b0011100,
        0b0001000
    },
    /*
     ....
     ..#.
     ..#.
     ###.
     */
    new[]
    {
        0b0000100,
        0b0000100,
        0b0011100
    },
    /*
     #...
     #...
     #...
     #...
     */
    new[]
    {
        0b0010000,
        0b0010000,
        0b0010000,
        0b0010000
    },
    /*
     ....
     ....
     ##..
     ##..
     */
    new[]
    {
        0b0011000,
        0b0011000
    }
};

The arena can simply be stored in an int[], where each entry is a row in the playing field.

Storing the pyronimoes in this fashion also means that moving them left or right is simply a case of bit rotation. Moving a row of a pyronimo right is simply:

rock[y] >> 1

Detecting a collision when a pyronimo falls, one simply compares the rows of the pyronimo with the relevant row in the playing field.

if ((rock[rY] & _map[y]) != 0)
{
    // Collision
}

Pretty simple and neat I thought, worked quickly and produced the correct answer. Awesome!

Then part 2 hit...

Arse.

Given the enormity of that number, I knew that brute-forcing the problem was not an option.

The Optimisation

private const long MassiveNumber = 1_000_000_000_000;

First, add that constant to the class so I don't have to type that number again.

I presumed that there must be a repeating pattern so that one doesn't have to cycle through all the iterations, otherwise, this problem is a no-go. How to detect the pattern and calculate the final result though?

There will be people better trained or more well educated in computer science than me who probably have a better solution, but this is what I came up with.

Whenever a new block lands, I take a "snapshot" of the top 50 rows of the playing field and store it along with the 𝑦 coordinate of the current top of the map and the current cycle number. These are stored as a hash of each of the 50 rows combined. This keeps the data small, and allows fast lookups. 50 rows is just arbitrary, but it seems to work.

private readonly Dictionary<int, (int Y, int Cycle)> _hashes = new();

To illustrate, I'll use a smaller window of 5 lines.

y = 9,987  |..#....|  16
           |.###...|  56
           |..#....|  16
           |.####..|  60
           |....##.|  6
           |....##.|
           |....#..|
           |..#.#..|
           |..#.#..|
           |#####..|
           |..###..|
           |...#...|
           |..####.|
           +-------+

The reason 𝑦 is 9,987 is because I chose a map size of 10,000 rows arbitrarily to store in memory and treat _map[9_999] as the bottom row of the field.

Since each row is stored with bits representing the occupied cells, it is just an integer which is incredibly easy to hash.

Now, to see whether the pattern in the playing field is repeating, on each turn we:

• Create a hash of the top 50 rows of the field.
• Compare it with our list of historical hashes.
• If found, we have discovered a pattern.
• If not found, add the hash to the historical list.

For the above example we would add the hash as follows with _highPoint = 9_987, WindowSize = 5 and cycle = 7 as 7 blocks have fallen.

var hash = new HashCode();

for (var y = _highPoint; y < _highPoint + WindowSize; y++)
{
    hash.Add(_map[y]);
}

var hashCode = hash.ToHashCode();

if (_hashes.ContainsKey(hashCode))
{
    // Pattern found!
}
else
{
    // Pattern not found, add to history.
    _hashes.Add(hash.ToHashCode(), (_highPoint, cycle));
}

Once a pattern has been found, we can calculate what we need for the final answer.

var cycleLength = cycle - _previousCycle;

var heightBoost = (MassiveNumber / cycleLength - 2) * _previousPeriod;

var remainingCycles = (int) ((MassiveNumber - cycle) % cycleLength));

With cycleLength being how many cycles have passed since the pattern we have matched with, heightBoost how much the top of the playing field has moved in that time and remainingCycles how many cycles are required to finish the game after the height boost has been added.

At this point, we can add the height boost to the current height and run the game for the remaining cycles.

Voilà, a run-time that would probably go beyond the heat death of the universe is reduced to 2 milliseconds.