Sean McLemon | Advent of Code

2016-12-13 - A Maze of Twisty Little Cubicles

(original .ipynb)

import math
from advent import neighbours4
from heapq import heappush, heappop

puzzle_input = 1358
test_input = 10


def tile_type(x, y, favourite_number):
    res = (x*x + 3*x + 2*x*y + y + y*y) + favourite_number
    return "." if sum(1 for c in bin(res) if c == '1') % 2 == 0 else "#"


def build_grid(target_r, target_c, favourite_number):
    grid = []
    r = 0
    
    while r <= target_r:
        c = 0
        row = []
        while c <= target_c:
            row.append(tile_type(c, r, favourite_number))
            c += 1
            
        grid.append(row)
        r += 1
    return grid


def part_one(dest_c, dest_r, favourite_number):
    buffer = 5
    grid = build_grid(dest_r + buffer, dest_c + buffer, favourite_number)
    
    distances = [
        [ math.inf for c in range(dest_c + buffer + 1)]
        for r in range(dest_r + buffer + 1)
    ]
    
    queue = []
    heappush(queue, (0, (1, 1)))
    
    while len(queue) > 0:
        steps, (r, c) = heappop(queue)
        
        if grid[r][c] == "#" or steps > distances[r][c]:
            continue
        
        if (r == dest_r) and (c == dest_c):
            return steps
            
        distances[r][c] = steps        
        for (nr, nc) in neighbours4(grid, r, c):
            heappush(queue, (steps+1, (nr, nc)))
    
    return -1

assert 11 == part_one(7, 4, test_input)

print("part one:", part_one(31, 39, puzzle_input))

part one: 96

def part_two(favourite_number):
    grid = build_grid(50, 50, favourite_number)
    
    distances = [
        [ math.inf for c in range(51)]
        for r in range(51)
    ]
    
    queue = []
    heappush(queue, (0, (1, 1)))
    
    while len(queue) > 0:
        steps, (r, c) = heappop(queue)
        
        if grid[r][c] == "#" or steps > 50 or steps > distances[r][c]:
            continue
            
        distances[r][c] = steps        
        for (nr, nc) in neighbours4(grid, r, c):
            heappush(queue, (steps+1, (nr, nc)))
    
    reachable_in_50 = 0
    for row in distances:
        for col in row:
            if col <= 50:
                reachable_in_50 += 1
    
    return reachable_in_50

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

part two: 141