Sean McLemon | Advent of Code

Home | Czech | Blog | GitHub | Advent Of Code | Notes


2018-12-18 - Settlers of The North Pole

(original .ipynb)
from itertools import combinations

test_input_str = """.#.#...|#.
.....#|##|
.|..|...#.
..|#.....#
#.#|||#|#|
...#.||...
.|....|...
||...#|.#|
|.||||..|.
...#.|..|."""

from pprint import pprint

# open ground (.), trees (|), or a lumberyard (#). 

open_ground = "."
trees = "|"
lumberyard = "#"

def parse_input(input_str):
    return [
        [ col for col in row ] for row in input_str.split("\n") 
    ]

def is_open_ground(acre):
    return acre == open_ground

def is_trees(acre):
    return acre == trees

def is_lumberyard(acre):
    return acre == lumberyard

def get_neighbours(grid, r, c):
    indices = []
    rs = range(r-1, r+2)
    cs = range(c-1, c+2)
    
    max_r = len(grid)
    max_c = len(grid[0])

    for maybe_r in rs:
        for maybe_c in cs:
            if maybe_r == r and maybe_c == c:
                continue
                
            if maybe_r >= max_r or maybe_r < 0:
                continue
                
            if maybe_c >= max_c or maybe_c < 0:
                continue
                
            yield grid[maybe_r][maybe_c]


            
def next_acre_state(current_acre, neighbours):
    # An open acre will become filled with trees if three or more adjacent acres contained trees. 
    #    Otherwise, nothing happens.    
    if is_open_ground(current_acre):
        neighbouring_trees = [n for n in neighbours if is_trees(n)]
        if len(neighbouring_trees) >= 3:
            return trees
        
    # An acre filled with trees will become a lumberyard if three or more adjacent acres were lumberyards. 
    #    Otherwise, nothing happens.
    elif is_trees(current_acre):
        neighbouring_lumberyards = [n for n in neighbours if is_lumberyard(n)]
        if len(neighbouring_lumberyards) >= 3:
            return lumberyard
        
    # An acre containing a lumberyard will remain a lumberyard if it was adjacent to at least one other lumberyard 
    #     and at least one acre containing trees. Otherwise, it becomes open.
    elif is_lumberyard(current_acre):
        if not (lumberyard in neighbours and trees in neighbours):
            return open_ground
        
    return current_acre
            
def step(state):
    new_state = []
    for r, row in enumerate(state):
        new_row = []
        for c, acre in enumerate(row):
            ns = [n for n in get_neighbours(state, r, c)]
            next_acre = next_acre_state(acre, ns)
            new_row.append(next_acre)
            
        new_state.append(new_row)
            
    return new_state
    
def print_state(state):
    for row in state:
        print("".join(row))
    
def serialize_state(state):
    return "".join(
        [ "".join(row) for row in state ]
    )
    
def run(state, iterations):   
    last_seen = {}
    loop_found = False
    while iterations > 0:       
        state = step(state)
        state_str = serialize_state(state)
        
        # fucked around with this after seeing part #2
        if (state_str in last_seen) and not(loop_found):
            loop_found = True
            iterations = iterations % (last_seen[state_str] - iterations) - 1
        else:
            last_seen[state_str] = iterations
            iterations -= 1
        
    return state
    
def solve(input_str, iterations):
    state = parse_input(input_str)
    final_state = run(state, iterations)
    
    count_open_ground = 0
    count_lumberyards = 0
    count_trees = 0
    
    for row in final_state:
        for acre in row:
            if is_open_ground(acre):
                count_open_ground += 1
            elif is_lumberyard(acre):
                count_lumberyards += 1
            elif is_trees(acre):
                count_trees += 1                
    
    return count_lumberyards * count_trees

assert 1147 == solve(test_input_str, 10)
puzzle_input_str = """..##|#.##..|#...|.#|....#|.#......|#......#|....|.
..#|.#.#|..#.|...|.|.|....|..|||||..#|..#.#..|##.|
.||.....#..#.....|||#|.....#|###|||.|..#...#..|##.
#|...|#|.......##.|......####.|..||#....##||.#...#
..|.##|#.|.#||#....#||...|#.||.|....|.|#|.#...#.#.
#..|......#..#....|||.||..#..#..#.|.|.|#.||.....#.
|.|...#|..|#|.|....#...#.|.#||.....#........||..|.
.#|##.|...|......|.#||#|#..|.|....|....|||...#####
.|.......#....##|.#.#...|.||.....#|.|#.......|##|.
.#....#|##|..##|..#.|...##.|#.##..#.......||.|.|##
###..#||........#...#..#..|......||.......#.|#|#..
.||.#.....|.#...|......#.||##||......|...||.||....
..#|.|....#.#.|||#...#.....#.#.#.|....#.|...|#....
#...|..#.|.|...#|..#.|#...|.......#.|.......|.###.
.|#|.#.|..#|....|..|..#..#|......#..#..|.#...|.|#.
.#...#......#|||..|.|.....#....|#.||.....#||##..|.
|.|...#||..|........#.....|#....|...||..##.#.#.|..
.....|......######|...|.....##.........|#|.#|.....
|..|.......|#|.##.|..|....#....##..||..|...|..|...
.||||#....|..|.|#|..|...#.|#.|.....|.||.||#...|...
.#|#..###.#|....#..||...|##..#.#|..#..|||........#
..|.#.....#|..|.#..|...#||......##.|....|.|#.|.|||
..#.......|#||..|...|.....##..#.#.####..|......#|#
.|##......|#....|..|.||...##|#....##||#.#|#.#..#.|
#..#..|..#....|..|....##..|..#....##.#|#|##|#|....
|####..#....|..|..|....|#.|....|.....##.##.#|....|
..||...##..|...#|##..|.##......#...##.|....#.|...#
.#...|#.|#|.....|#|....##.|.........|.......|.#...
||...###...|#..###|..|.#.|#||...#...#|.....|##|..|
#.#.#|....#|#..|..........|#..#|.|#||...|##.##.|#.
....|.##..#...#..##|..|....|..||#.|..|..#..#......
.|.#..|.#...||..#..|.|...#....|.||#.|#.....||.|...
..#|||.#..|#|...||#.|....|.#...#||||#...#...|...|#
..#..#....#|.............##...|..#..#..||##|..#.||
#....#|...#..##....###..||..#||...|.#..|.....|....
....|..#...#...||..||....|#|#|.|..|.#.|..|.##..|#.
..#.....|....||.##..#..#|..|.|#.....|...|..|..#..#
.##.||.#||..#|.#....||.|.....#|.....#....||..#.##|
..|.#|.|...|........#......|.##.|#.#..|......##...
.##||.|.##....|...##.#.....#.##.##..#...|||#|#.|.|
....|||..|....#..#.#..|.|.|....#.|#.#.##|.|#.#|.#.
..|...#|#....##.#|##.#.||##...#.|#..##.....#...#..
.|#..#.....|...|.#..##......|..#.|.......#.....#..
.#..|.#..|#...#....|..||.|..#..#...##........#....
.|.##.#|.#.#.|..||##|..||||.##|||..#..##...|..#|#.
#.......#...|#.|#||..|.##...#...|....|...##....#.|
.###..|......||#...|..||||#....|.||...#....|.#...|
.|.#...|#..|.....#......|.......|.........|.#.#...
|.|...#...|#|||...|||....|#..|#...#.#..#...|....#|
|#...#..#.|#|.#..#.#.....|.|.##...#.|#..|.#|..#..."""


print(solve(puzzle_input_str, 10))
638400
print(solve(puzzle_input_str, 1000000000))
195952