Jesper Dramsch , , read in 5 minutes

Ok this one was fun!

I actually got started with Python on a Tetris clone, back in the day for a Hackathon.

Building this from scratch was refreshing!

What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

Find my solutions here: github.com/JesperDramsch/advent-of-code

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

The example input

Is this Tetris?!

####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##

oh that's not the example input. This is!

>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>

It is tetris-adjacent!

The implementation

When we think "game" we need to think "state", so it's best to start with a class.

That class can keep the board state, pieces, instructions, and it's perfect for an object like this.

Part 1 is very straight forward. Parse the inputs. Build the logic.

I parse the inputs as dictionaries with 2D coordinates as complex numbers to make the math easy, after all we need to shift down, left, and right. This also meant I did not have to do weird "row logic", I could simply check where a piece is in space and if its boundaries collide with other pieces or the walls.

def turn(self):
    piece = self.next_piece()
    while True:
        direction = self.next_direction()
        if direction == "<":
            new_piece = self._left(piece)
        elif direction == ">":
            new_piece = self._right(piece)
        if new_piece is not None:
            piece = new_piece
        new_piece = self._down(piece)
        if new_piece is not None:
            piece = new_piece
        else:
            self.board |= piece
            self.height = int(max([self.height] + [p.real for p in piece.keys()]))
            break

The idea here is the each move is checked and if it's a valid move, the new position is returned, otherwise we just get None.

So. That was pretty fun!

Is part 2 adding rotations? Is it finding tetrises?

Part Due

A yes, a trillion executions.

We will run into two problems here. Space and time.

The space constraint is how large our board might become. However, we only need the height, so we don't actually have to keep the entire board.

Every time there is a "tetris", we can delete the board below, because no checks have to be made against it.

def check_tetris(self, piece):
    min_height = int(min([p.real - 1 for p in self.board.keys()]))
    for i in range(self.height, min_height, -1):
        if all([i + ii * 1j in self.board for ii in range(self.width)]):
            self.board = {k: v for k, v in self.board.items() if k.real > i}
            self.floor = i
            break

So a bit different to the actual Tetris, but still useful!

But the real problem is time!

Running this code for a trillion iterations, will take a bit of time, but if you've been around AOC for a while, you know this is a "find the circular pattern"-problem.

The board is empty. The directions are circular, the pieces are circular. There positively HAS to be a point a pattern repeats.

So i implemented a cache of the game:

def check_circular(self):
    if self.height < 55:
        return
    signature = tuple(
        k - (self.height + 55)
        for k, v in self.board.items()
        if k.real >= self.height - 55
    )
    piece = tuple(self.pieces)
    directions = tuple(self.directions)
    if (signature, piece, directions) in self.seen:
        self.circular = self.seen[(signature, piece, directions)], (
            self.turn_counter,
            self.height,
        )
    self.seen[(signature, piece, directions)] = (self.turn_counter, self.height)

55 lines are hopefully enough to check. And they were!

Now we just add this to the game logic:

def game(self, turns):
    self.turn_counter = 0
    height_offset = 0
    while self.turn_counter < turns:
        self.turn()

        if self.circular:
            (i_start, h_start), (i_end, h_end) = self.circular
            cycles = (turns - i_start) // (i_end - i_start)
            height_offset = h_start + cycles * (h_end - h_start) - h_end
            self.turn_counter = i_start + cycles * (i_end - i_start)
            self.circular, self.seen = (), {}
        self.turn_counter += 1
    else:
        self.height += height_offset

If a circular pattern is detected, fast forward the counter and the height.

Clear the cache.

Play the last few turns.

And submit the final height!

Error Log

Just the usual. Messing up names and forgetting I started one thing then working on the next.

  • new_pieces.append(i+ii*1j) NameError: name 'new_pieces' is not defined. Did you mean: 'new_piece'? oops. Yes I did. The new Python errors are really good actually.
  • IndentationError: expected an indented block after function definition on line 52 started working on a different part and forgot the pass
  • return "\n".join("".join(row) for row in self.board) TypeError: can only join an iterable argh. Yeah makes sense. I don't actually have rows.
  • for i, v in self.pieces.items(): AttributeError: 'list' object has no attribute 'items' wrong variable
  • def _right(self): SyntaxError: invalid syntax closing brackets. Weird autocomplete quirks...
  • if i + direction in self.board or i + direction < 0 or i + direction > self.width: TypeError: '<' not supported between instances of 'complex' and 'int' argh, yeah makes sense.
  • for i in range(self.height): TypeError: 'float' object cannot be interpreted as an integer oops, yeah the max() function returned a float
  • self.check_tetris(piece) TypeError: Tetris.check_tetris() takes 1 positional argument but 2 were given forgot to provide the piece to the function
  • signature = tuple(k-(self.height+23) for k, v in self.board.items() if k >= self.height - 23)TypeError: '>=' not supported between instances of 'complex' and 'int' I will never not fall for this.
  • self.height += height_offset - h_end UnboundLocalError: cannot access local variable 'height_offset' where it is not associated with a value didn't initialize...