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