Sean McLemon | Advent of Code

2022-12-17 - Pyroclastic Flow

(original .ipynb)

from copy import deepcopy
from pprint import pprint 

puzzle_input_str = open("./puzzle_input/day17.txt").read()
test_input_str = ">>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>"

def build_shape(shape):
    for r, row in enumerate(shape):
        for c, col in enumerate(row):
            if col == "@":
                yield (r, c)

                
all_shapes = {
    name: (len(shape), list(build_shape(shape))) 
    for name,shape in [
        ("horizontal", [   # horizontal line
            list("..@@@@.")
        ]),
        
        ("cross", [   # cross
            list("...@..."),
            list("..@@@.."),
            list("...@...")
        ]),
        
        ("angle", [   # angle
            list("....@.."),
            list("....@.."),
            list("..@@@..")
        ]),
        ("vertical", [   # vertical line
            list("..@...."),
            list("..@...."),
            list("..@...."),
            list("..@....")
        ]),
        ("square", [   # square
            list("..@@..."),
            list("..@@...")
        ]),
    ]
}


def init_grid():
    return [
        ["."] * 7 for _ in range(3)
    ]


def shapes():
    keys = ["horizontal", "cross", "angle", "vertical", "square"]
    while True:
        for key in keys:
            yield key


def tower_height(grid):
    rows = 0
    for row in grid:
        if "#" in row:
            break
        rows += 1
    return len(grid) - rows


def pad_grid(grid, shape_height):
    rows = 3 + shape_height
    for row in grid:
        if "#" in row:
            break
        rows -= 1
    
    if rows < 0:
        while rows < 0:
            grid.pop(0)
            rows += 1
        #print(f"padding with {rows} rows")
    else:
        while rows > 0:
            grid.insert(0, ["."] * 7)
            rows -= 1


def at_rest(row, shape, grid):
    #print("checking at rest")
    for r,c in shape:
        assert row+r+1 <= len(grid)
        if row+r+1 == len(grid):
            #print("we reached the bottom at row", row+r+1)
            return True        
        
        if grid[row+r+1][c] == "#":
            return True
    
    return False

def parse_input(input_str):
    while True:
        for i, c in enumerate(input_str):
            yield i, c

def apply_jet(jet, row, shape, grid):
    new_shape = []
    if jet == "<":
        for r, c in shape:
            if c == 0 or (grid[row+r][c-1] == "#"):
                #print("Jet of gas pushes rock left, but nothing happens")
                return shape
            new_shape.append((r, c-1))
        #print("Jet of gas pushes rock left")
    elif jet == ">":
        for r, c in shape:
            if c == 6 or (grid[row+r][c+1] == "#"):
                #print("Jet of gas pushes rock right, but nothing happens")
                return shape
            new_shape.append((r, c+1))
        #print("Jet of gas pushes rock right")
    return new_shape


def add_to_grid(row, shape, grid):
    for r,c in shape:
        assert grid[row+r][c] != "#"
        grid[row+r][c] = "#"

    
def dump_grid(grid):
    for row in grid:
        print("".join(row))

        
def prune(grid):
    # find the row below which all are covered
    tester = [False] * len(grid[0])
    
    for r, row in enumerate(grid):
        for c, col in enumerate(row):
            if col == "#":
                tester[c] = True
        
        if all(tester):
            return grid[:r+1], len(grid)-(r+1)
    
    return grid, 0
        

def get_key(grid, shape_name, jet):
    heights = [3] * 7
    for r, row in enumerate(grid):
        for c, col in enumerate(row):
            if col == "#" and heights[c] == 3:
                heights[c] = r
        if all(h != 3 for h in heights):
            break
    
    adjustment = min(heights) - 3
    return "-".join(
        [str(h-adjustment) for h in heights]
        + [shape_name]
        + [jet]
    )


def part_one(input_str, iterations=2022):
    jets = parse_input(input_str)
    grid = init_grid()
    
    shape_getter = shapes()
    
    total_pruned = 0
    iteration = 0
    seen_before = {}
    height_at = {}
    
    while iteration < iterations:
        height_at[iteration] = tower_height(grid) + total_pruned
        iteration += 1
        shape_name = next(shape_getter)
        rows, shape = all_shapes[shape_name]
        pad_grid(grid, rows)
        j, jet = next(jets)
        row = 0
        shape = apply_jet(jet, row, shape, grid)

        while not at_rest(row, shape, grid):
            row += 1
            j, jet = next(jets)
            shape = apply_jet(jet, row, shape, grid)
        
        key = get_key(grid, shape_name, str(j))
        if key in seen_before:
            prev_iteration, prev_height = seen_before[key]
            cycle_length = iteration - prev_iteration
            growth_per_cycle = tower_height(grid) + total_pruned - prev_height
            
            length_of_repeated_section        = (iterations - prev_iteration)
            number_of_cycles                  = length_of_repeated_section // cycle_length
            iterations_after_repeated_section = length_of_repeated_section  % cycle_length

            return sum([
                height_at[prev_iteration],
                number_of_cycles * growth_per_cycle, 
                height_at[prev_iteration + iterations_after_repeated_section] - height_at[prev_iteration]
            ])
        else:
            seen_before[key] = (iteration, tower_height(grid) + total_pruned)
            
        add_to_grid(row, shape, grid)
        grid, pruned = prune(grid)
        total_pruned += pruned
        
    return -1 # should be unreachable. should be ...


assert 3068 == part_one(test_input_str)

print("part one:", part_one(puzzle_input_str))

part one: 3219

def part_two(input_str):
     return part_one(input_str, 1000000000000)


assert 1514285714288 == part_two(test_input_str)

print("part two:", part_two(puzzle_input_str))

part two: 1582758620701