Advent of Code Day 17 — Pyroclastic Flow

If ever there was a day to write a game for, this one would be it. Because it is Tetris.

The setup here is you are trying to escape with the elephants from the imminently erupting volcano, and the elephants don’t believe you can predict where the rocks falling, one at a time, from an opening far above, so they refuse to run to safety.

Part 1 is to drop 2,022 Tetris piece-shaped rocks and see where they land. Part 2 is to drop a trillion blocks. Not a typo.

Until I saw what Part 2 was, I was just going to solve this in PICO-8 and get a game out of it for free. But Part 2 said that this was not a puzzle about playing Tetris. It was a puzzle about finding a sequence.

The rules of this challenge always drop the same five blocks in the same order, starting in the same position relative to the already placed pieces. Pieces are moved left and right as they drop according to the puzzle input.

At some point, the sequence of dropped blocks will repeat. The trick (there is always a trick) is to find the start and length of this sequence, and then use that plus the bits at the start and end that don’t rate a full sequence to find the total height of the column (which for my puzzle was 1,536,231,884,054 units.) If a unit was a meter, the column of rocks would stretch from the Earth to Saturn. So these elephants are a little unreasonable.

There are a bunch of cool algorithms to find sequences in data, but my understanding of them is poor, so I just used brute force to find it. And I think, maybe, I found a bug?

Almost everyone solved Part 1 by programming the Tetris game and just seeing how things landed. I did, too, and got the correct answer, and moved on.

Part 2 required this other thing, and I did that, got the correct answer… but didn’t move on. Instead, I tried to solve Part 1 with this, since the sequence would be the same (even if it wasn’t long enough to contain a full sequence, it would just consist of the beginning part and the end part with no sequence).

And it almost worked — it was off by one.

I just don’t get it. I’m not surprised, as it measures to the bottom of the last dropped rock. When I ran the game for Part 1, I added the height of that last rock in for the correct answer. The new solution doesn’t do that.

So I really expected Part 2 to be off by one, not Part 1. It does not make any sense at all.

Anyway, maybe I’ll come back and write the PICO-8 version of this.

Python 3.11

This is not clean, nor elegant. Just gonna leave it here without comment.

from itertools import cycle

def read_hot_jets():
    with open(r"2022\puzzle17.txt") as f:
        jet_jet_jet = f.read()
        return len(jet_jet_jet), cycle(jet_jet_jet)

def get_pieces():
    pieces = []
    pieces.append([(0,0), (1,0), (2,0), (3,0)])
    pieces.append([(1,0), (0,1), (1,1), (2,1), (1,2)])
    pieces.append([(0,0), (1,0), (2,0), (2,1), (2,2)])
    pieces.append([(0,0), (0,1), (0,2), (0,3)])
    pieces.append([(0,0), (1,0), (0,1), (1,1)])
    return len(pieces), cycle(pieces)

def check_collision(playing_board, piece, piece_pos, delta):
    for x,y in piece:
        nx, ny = piece_pos[0]+x+delta[0], piece_pos[1]+y+delta[1]
        if (nx, ny) in playing_board:
            return True
        if nx < 0 or nx >= 7 or ny < 0:
            return True
    return False

def get_rock_height(playing_board):
    return max([y+1 for _,y in playing_board]) if playing_board else 0

def drop_a_rock(playing_board: set, pieces, jets, rest_at: list):
    piece = next(pieces)
    piece_pos = (2, get_rock_height(playing_board)+3)
    
    while True:
        jet = next(jets)
        #print(piece_pos, jet)
        dx = -1 if jet == '<' else 1
        if not check_collision(playing_board, piece, piece_pos, (dx, 0)):
            piece_pos = (piece_pos[0]+dx, piece_pos[1])
        if check_collision(playing_board, piece, piece_pos, (0, -1)):
            # add all piece points to the playing board
            for x,y in piece:
                playing_board.add((piece_pos[0]+x, piece_pos[1]+y))
            rest_at.append((*piece_pos, piece))
            #print ("dropped")
            break
        piece_pos = (piece_pos[0], piece_pos[1]-1)

def run_simulation(part1_drops):
    pieces_length, pieces = get_pieces()
    _, jets = read_hot_jets()
    playing_board = set()
    rest_at = list()

    for _ in range(part1_drops):
        drop_a_rock(playing_board, pieces, jets, rest_at)
    
    return rest_at, pieces_length

def get_pattern(rest_at, pieces_length, total_drops):
    confirmation_size = 4
    max_pattern_size = total_drops // confirmation_size // pieces_length
    print (max_pattern_size)

    pattern_found = False
    for i in range(max_pattern_size):
        pattern_length = (i+1)*pieces_length
        for test_start in range(0, total_drops - confirmation_size*pattern_length):
            pattern_found = True
            for j in range(test_start, test_start+pattern_length):
                if rest_at[j][0] != rest_at[j+pattern_length][0] or \
                    rest_at[j][0] != rest_at[j+2*pattern_length][0] or \
                    rest_at[j][0] != rest_at[j+3*pattern_length][0]:
                    pattern_found = False
                    break
            if pattern_found:
                return test_start, pattern_length
        if pattern_found:
            break

def calc_height_at(total_drops, rest_at, test_start, pattern_length, height_of_pattern):
    starting_height = rest_at[test_start][1]
    print ("--- Starting height", starting_height)
    num_pattern_repeats = (total_drops - test_start) // pattern_length
    print ("--- Num pattern repeats", num_pattern_repeats)
    leftover = (total_drops - test_start) % pattern_length
    print ("--- Leftover", leftover)
    leftover_height = rest_at[test_start+leftover][1] - rest_at[test_start][1]
    print ("--- Leftover height", leftover_height)
    return starting_height + num_pattern_repeats*height_of_pattern + leftover_height

ballpark_figure = 10000
rest_at, pieces_length = run_simulation(ballpark_figure)
test_start, pattern_length = get_pattern(rest_at, pieces_length, ballpark_figure)

print ("Pattern found at", test_start, "with length", pattern_length)
height_of_pattern = rest_at[test_start+pattern_length][1] - rest_at[test_start][1]
print ("Height of pattern", height_of_pattern)

print ("Part 1:", calc_height_at(2022, rest_at, test_start, pattern_length, height_of_pattern))
print ("Part 2:", calc_height_at(1000000000000, rest_at, test_start, pattern_length, height_of_pattern))