Skip to content

Instantly share code, notes, and snippets.

@patrickfuller
Last active December 27, 2022 04:04
Show Gist options
  • Save patrickfuller/55571f2a2d5e22f7fe906e00726769b1 to your computer and use it in GitHub Desktop.
Save patrickfuller/55571f2a2d5e22f7fe906e00726769b1 to your computer and use it in GitHub Desktop.
Advent of Code 2022
# pylint: disable=unspecified-encoding
"""Solutions for 2022 Advent of Code puzzles.
https://adventofcode.com/2022
"""
import argparse
import functools
import itertools
import json
from queue import LifoQueue
import re
def day_1_part_1():
"""Solve Day 1 Part 1 calories puzzle."""
with open('day_1.txt') as in_file:
elves = in_file.read().split('\n\n')
elves = (elf.strip().split('\n') for elf in elves)
rations = (sum(int(food) for food in elf) for elf in elves)
return max(rations)
def day_1_part_2():
"""Solve Day 1 Part 2 calories puzzle."""
with open('day_1.txt') as in_file:
elves = in_file.read().split('\n\n')
elves = (elf.strip().split('\n') for elf in elves)
rations = [sum(int(food) for food in elf) for elf in elves]
rations.sort()
return sum(rations[-3:])
def day_2_part_1():
"""Solve Day 2 Part 1 rock-paper-scissors puzzle."""
rock, paper, scissors = 1, 2, 3
loss, draw, win = 0, 3, 6
scores = {
'A X': rock + draw,
'A Y': paper + win,
'A Z': scissors + loss,
'B X': rock + loss,
'B Y': paper + draw,
'B Z': scissors + win,
'C X': rock + win,
'C Y': paper + loss,
'C Z': scissors + draw,
}
with open('day_2.txt') as in_file:
total = sum(scores[move.strip()] for move in in_file)
return total
def day_2_part_2():
"""Solve Day 2 Part 2 rock-paper-scissors puzzle."""
rock, paper, scissors = 1, 2, 3
loss, draw, win = 0, 3, 6
scores = {
'A X': loss + scissors,
'A Y': draw + rock,
'A Z': win + paper,
'B X': loss + rock,
'B Y': draw + paper,
'B Z': win + scissors,
'C X': loss + paper,
'C Y': draw + scissors,
'C Z': win + rock,
}
with open('day_2.txt') as in_file:
total = sum(scores[move.strip()] for move in in_file)
return total
def day_3_part_1():
"""Solve Day 3 Part 1 rucksack puzzle."""
with open('day_3.txt') as in_file:
rucksacks = in_file.read().splitlines()
total = 0
for rucksack in rucksacks:
middle = len(rucksack) // 2
item = (set(rucksack[:middle]) & set(rucksack[middle:])).pop()
total += ord(item) - (96 if ord(item) > 96 else 38)
return total
def day_3_part_2():
"""Solve Day 3 Part 2 rucksack puzzle."""
with open('day_3.txt') as in_file:
rucksacks = in_file.read().splitlines()
total = 0
groups = (rucksacks[i:i+3] for i in range(0, len(rucksacks), 3))
for group in groups:
item = (set(group[0]) & set(group[1]) & set(group[2])).pop()
total += ord(item) - (96 if ord(item) > 96 else 38)
return total
def day_4_part_1():
"""Solve Day 4 Part 1 section overlap puzzle."""
with open('day_4.txt') as in_file:
assignments = in_file.read().splitlines()
overlaps = 0
for pair in assignments:
sections = (
[int(i) for i in section.split('-')]
for section in pair.split(',')
)
outer, inner = sorted(sections, key=lambda x: x[0])
if outer[0] == inner[0] or outer[1] >= inner[1]:
overlaps += 1
return overlaps
def day_4_part_2():
"""Solve Day 4 Part 2 section overlap puzzle."""
with open('day_4.txt') as in_file:
assignments = in_file.read().splitlines()
overlaps = 0
for pair in assignments:
sections = (
[int(i) for i in section.split('-')]
for section in pair.split(',')
)
lower, higher = sorted(sections, key=lambda x: x[0])
if higher[0] <= lower[1]:
overlaps += 1
return overlaps
def day_5_part_1():
"""Solve Day 5 Part 1 crane stacking puzzle."""
with open('day_5.txt') as in_file:
initial_stack, steps = in_file.read().split('\n\n')
# Parse header (containing initial stack list)
stacks = {}
header, *initial_stack = initial_stack.splitlines()[::-1]
for i, char in enumerate(header):
if char.isdigit():
stacks[char] = LifoQueue()
for row in initial_stack:
if len(row) >= i and row[i] != ' ':
stacks[char].put(row[i])
# Parse steps and apply onto header
pattern = re.compile(r'move (\d+) from (\d+) to (\d+)')
for step in steps.splitlines():
count, src, dst = pattern.match(step).groups()
for _ in range(int(count)):
crate = stacks[src].get()
stacks[dst].put(crate)
return ''.join(stack.get() for stack in stacks.values())
def day_5_part_2():
"""Solve Day 5 Part 2 crane stacking puzzle."""
with open('day_5.txt') as in_file:
initial_stack, steps = in_file.read().split('\n\n')
# Parse header (containing initial stack list)
stacks = {}
header, *initial_stack = initial_stack.splitlines()[::-1]
for i, char in enumerate(header):
if char.isdigit():
stacks[char] = LifoQueue()
for row in initial_stack:
if len(row) >= i and row[i] != ' ':
stacks[char].put(row[i])
# Parse steps and apply onto header
pattern = re.compile(r'move (\d+) from (\d+) to (\d+)')
for step in steps.splitlines():
count, src, dst = pattern.match(step).groups()
crates = [stacks[src].get() for _ in range(int(count))]
for crate in crates[::-1]:
stacks[dst].put(crate)
return ''.join(stack.get() for stack in stacks.values())
def day_6_part_1():
"""Solve Day 6 Part 1 datastream packet puzzle."""
with open('day_6.txt') as in_file:
datastream = in_file.read()
for i, _ in enumerate(datastream, start=4):
if len(set(datastream[i-4:i])) == 4:
return i
raise ValueError("No start-of-packet marker found.")
def day_6_part_2():
"""Solve Day 6 Part 2 datastream packet puzzle."""
with open('day_6.txt') as in_file:
datastream = in_file.read()
for i, _ in enumerate(datastream, start=14):
if len(set(datastream[i-14:i])) == 14:
return i
raise ValueError("No start-of-message marker found.")
def day_7_part_1():
"""Solve Day 7 Part 1 directory map puzzle."""
dirs, files = {}, {}
cwd = ''
reading_files = False
with open('day_7.txt') as in_file:
for line in in_file:
line = line.strip()
# cd
if match := re.match(r'\$ cd (.+)', line):
reading_files = False
command = match[1]
if command == '/':
cwd = ''
elif command == '..':
cwd = cwd.rsplit('/', 1)[0]
else:
cwd = '/'.join([cwd, command])
dirs[cwd] = 0
# ls
elif line == '$ ls':
reading_files = True
elif reading_files:
size, name = line.split()
path = '/'.join([cwd, name])
if size == 'dir':
dirs[path] = 0
else:
files[path] = int(size)
total = 0
for directory in dirs:
dir_size = sum(size for path, size in files.items()
if path.startswith(directory))
if dir_size < 100000:
total += dir_size
return total
def day_7_part_2():
"""Solve Day 7 Part 2 directory map puzzle."""
dirs, files = {}, {}
cwd = ''
reading_files = False
with open('day_7.txt') as in_file:
for line in in_file:
line = line.strip()
# cd
if match := re.match(r'\$ cd (.+)', line):
reading_files = False
command = match[1]
if command == '/':
cwd = ''
elif command == '..':
cwd = cwd.rsplit('/', 1)[0]
else:
cwd = '/'.join([cwd, command])
dirs[cwd] = 0
# ls
elif line == '$ ls':
reading_files = True
elif reading_files:
size, name = line.split()
path = '/'.join([cwd, name])
if size == 'dir':
dirs[path] = 0
else:
files[path] = int(size)
size_needed = sum(size for size in files.values()) - 40_000_000
size_to_free = 70_000_000
for directory in dirs:
dir_size = sum(size for path, size in files.items()
if path.startswith(directory))
if size_needed < dir_size < size_to_free:
size_to_free = dir_size
return size_to_free
def day_8_part_1():
"""Solve Day 8 Part 1 tree visibility puzzle."""
with open('day_8.txt') as in_file:
trees = [[int(tree) for tree in row] for row in in_file.read().splitlines()]
size = len(trees)
visible = [[False] * size for _ in range(size)]
def traverse_tree_line(tree_line):
"""Update `visible` traversal table with visible trees."""
height = -1
for row, column, tree in tree_line:
if tree > height:
height = tree
visible[row][column] = True
for row, tree_line in enumerate(trees):
# Left to right
traverse_tree_line((row, column, tree) for column, tree
in enumerate(tree_line))
# Right to left
traverse_tree_line((row, column, tree) for column, tree
in list(enumerate(tree_line))[::-1])
for column, tree_line in enumerate(zip(*trees)):
# Top to bottom
traverse_tree_line((row, column, tree) for row, tree
in enumerate(tree_line))
# Bottom to top
traverse_tree_line((row, column, tree) for row, tree
in list(enumerate(tree_line))[::-1])
return sum(sum(row) for row in visible)
def day_8_part_2():
"""Solve Day 8 Part 2 tree visibility puzzle."""
with open('day_8.txt') as in_file:
trees = [[int(tree) for tree in row] for row in in_file.read().splitlines()]
size = len(trees)
max_score = 0
for row, tree_line in enumerate(trees):
for column, tree in enumerate(tree_line):
i = row - 1
while i > 0 and trees[i][column] < tree:
i -= 1
score = -(i - row)
i = row + 1
while i < size - 1 and trees[i][column] < tree:
i += 1
score *= i - row
j = column - 1
while j > 0 and tree_line[j] < tree:
j -= 1
score *= -(j - column)
j = column + 1
while j < size - 1 and tree_line[j] < tree:
j += 1
score *= j - column
max_score = max(max_score, score)
return max_score
def day_9_part_1():
"""Solve Day 9 Part 1 rope bridge puzzle."""
head, tail = (0, 0), (0, 0)
history = {tail}
head_moves = {
'U': (0, 1),
'D': (0, -1),
'R': (1, 0),
'L': (-1, 0),
}
tail_moves = {
(2, 0): (1, 0),
(-2, 0): (-1, 0),
(0, 2): (0, 1),
(0, -2): (0, -1),
(2, 1): (1, 1),
(1, 2): (1, 1),
(2, -1): (1, -1),
(1, -2): (1, -1),
(-2, 1): (-1, 1),
(-1, 2): (-1, 1),
(-2, -1): (-1, -1),
(-1, -2): (-1, -1),
}
with open('day_9.txt') as in_file:
for command in in_file:
direction, steps = command.strip().split()
for _ in range(int(steps)):
head = tuple(h + m for h, m in zip(head, head_moves[direction]))
diff = tuple(h - t for h, t in zip(head, tail))
move = tail_moves.get(diff, (0, 0))
tail = tuple(t + m for t, m in zip(tail, move))
history.add(tail)
return len(history)
def day_9_part_2():
"""Solve Day 9 Part 2 rope bridge puzzle."""
head, tails = (0, 0), [(0, 0) for _ in range(9)]
history = {tails[-1]}
head_moves = {
'U': (0, 1),
'D': (0, -1),
'R': (1, 0),
'L': (-1, 0),
}
tail_moves = {
(2, 0): (1, 0),
(-2, 0): (-1, 0),
(0, 2): (0, 1),
(0, -2): (0, -1),
(2, 1): (1, 1),
(1, 2): (1, 1),
(2, -1): (1, -1),
(1, -2): (1, -1),
(-2, 1): (-1, 1),
(-1, 2): (-1, 1),
(-2, -1): (-1, -1),
(-1, -2): (-1, -1),
(2, 2): (1, 1),
(-2, 2): (-1, 1),
(2, -2): (1, -1),
(-2, -2): (-1, -1),
}
with open('day_9.txt') as in_file:
for command in in_file:
direction, steps = command.strip().split()
for _ in range(int(steps)):
head = tuple(h + m for h, m in zip(head, head_moves[direction]))
for i, tail in enumerate(tails):
prev = head if i == 0 else tails[i - 1]
diff = tuple(p - t for p, t in zip(prev, tail))
move = tail_moves.get(diff, (0, 0))
tails[i] = tuple(t + m for t, m in zip(tail, move))
history.add(tails[-1])
return len(history)
def day_10_part_1():
"""Solve Day 10 Part 1 clock cycles puzzle."""
register_x, cycle, signal, strength = 1, 0, 20, 0
with open('day_10.txt') as in_file:
for line in in_file:
cycle += 1
if cycle >= signal - 1:
strength += signal * register_x
signal += 40
if line.startswith('addx'):
cycle += 1
register_x += int(line.split(' ')[-1])
return strength
def day_10_part_2():
"""Solve Day 10 Part 2 clock cycles puzzle."""
register_x, cycle = 1, 0
draw = list('.' * 240)
with open('day_10.txt') as in_file:
for line in in_file:
if abs(register_x - (cycle % 40)) <= 1:
draw[cycle] = '#'
cycle += 1
if line.startswith('addx'):
if abs(register_x - (cycle % 40)) <= 1:
draw[cycle] = '#'
cycle += 1
register_x += int(line.split(' ')[-1])
lines = [''.join(draw[i:i + 40]) for i in range(0, 240, 40)]
return '\n'.join(lines)
def day_11_part_1():
"""Solve Day 11 Part 1 monkey throwing puzzle."""
rounds = 20
pattern = re.compile(
r'Monkey (\d+):\s+'
r'Starting items: ([\d, ]+)\s+'
r'Operation: new = old ([*+]) (\S+)\s+'
r'Test: divisible by (\d+)\s+'
r'If true: throw to monkey (\d+)\s+'
r'If false: throw to monkey (\d+)'
)
monkeys = []
with open('day_11.txt') as in_file:
for monkey in in_file.read().split('\n\n'):
match = pattern.match(monkey).groups()
monkeys.append({
'id': int(match[0]),
'items': [int(item) for item in match[1].split(', ')],
'increase': {
'operator': match[2],
'value': 'old' if match[3] == 'old' else int(match[3]),
},
'test': {
'divisor': int(match[4]),
True: int(match[5]),
False: int(match[6])
},
'inspections': 0,
})
for _ in range(rounds):
for monkey in monkeys:
while monkey['items']:
# Pull item for inspection
item = monkey['items'].pop(0)
monkey['inspections'] += 1
# Increase worry
mi = monkey['increase']
worry = item if mi['value'] == 'old' else mi['value']
if mi['operator'] == '+':
item += worry
elif mi['operator'] == '*':
item *= worry
else:
raise ValueError(f"Operator {mi['operator']} not supported.")
# Decrease worry
item //= 3
# Check and throw to next monkey
mt = monkey['test']
test = (item % mt['divisor'] == 0)
monkeys[mt[test]]['items'].append(item)
inspections = sorted([monkey['inspections'] for monkey in monkeys])
return inspections[-1] * inspections[-2]
def day_11_part_2():
"""Solve Day 11 Part 2 monkey throwing puzzle."""
rounds = 10000
pattern = re.compile(
r'Monkey (\d+):\s+'
r'Starting items: ([\d, ]+)\s+'
r'Operation: new = old ([*+]) (\S+)\s+'
r'Test: divisible by (\d+)\s+'
r'If true: throw to monkey (\d+)\s+'
r'If false: throw to monkey (\d+)'
)
monkeys = []
gcd = 1
with open('day_11.txt') as in_file:
for monkey in in_file.read().split('\n\n'):
match = pattern.match(monkey).groups()
monkeys.append({
'id': int(match[0]),
'items': [int(item) for item in match[1].split(', ')],
'increase': {
'operator': match[2],
'value': 'old' if match[3] == 'old' else int(match[3]),
},
'test': {
'divisor': int(match[4]),
True: int(match[5]),
False: int(match[6])
},
'inspections': 0,
})
gcd *= int(match[4])
for _ in range(rounds):
for monkey in monkeys:
while monkey['items']:
# Pull item for inspection
item = monkey['items'].pop(0)
monkey['inspections'] += 1
# Increase worry
mi = monkey['increase']
worry = item if mi['value'] == 'old' else mi['value']
if mi['operator'] == '+':
item += worry
elif mi['operator'] == '*':
item *= worry
else:
raise ValueError(f"Operator {mi['operator']} not supported.")
# Modulo worry (to avoid big int overflow)
item %= gcd
# Check and throw to next monkey
mt = monkey['test']
test = (item % mt['divisor'] == 0)
monkeys[mt[test]]['items'].append(item)
inspections = sorted([monkey['inspections'] for monkey in monkeys])
return inspections[-1] * inspections[-2]
def day_12_part_1():
"""Solve Day 12 Part 1 hill climbing puzzle.
This was made to be an A* algorithm, and my literal graduate thesis is a
waste if I can't write one of these. EDIT: This is short enough for BFS.
"""
with open('day_12.txt') as in_file:
grid = [list(row) for row in in_file.read().splitlines()]
# Build indexed adjacency list to convert to a graph
start, end = None, None
nodes = {}
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == 'S':
start = (i, j)
cell = 'a'
elif cell == 'E':
end = (i, j)
cell = 'z'
nodes[(i, j)] = {
'value': ord(cell) - ord('a'),
'neighbors': [],
'steps': 1000000,
}
for (i, j), node in nodes.items():
for neighbor in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if neighbor in nodes and nodes[neighbor]['value'] <= node['value'] + 1:
node['neighbors'].append(neighbor)
# Breadth-first search the graph to calculate steps to get to each node
nodes[start]['steps'] = 0
queue = [start]
while queue:
node = nodes[queue.pop(0)]
for neighbor_location in node['neighbors']:
neighbor = nodes[neighbor_location]
steps = node['steps'] + 1
if steps < neighbor['steps']:
neighbor['steps'] = steps
queue.append(neighbor_location)
if neighbor_location == end:
break
return nodes[end]['steps']
def day_12_part_2():
"""Solve Day 12 Part 2 hill climbing puzzle."""
with open('day_12.txt') as in_file:
grid = [list(row) for row in in_file.read().splitlines()]
# Build indexed adjacency list to convert to a graph
start = None
nodes = {}
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == 'S':
cell = 'a'
elif cell == 'E':
start = (i, j)
cell = 'z'
nodes[(i, j)] = {
'value': ord('z') - ord(cell),
'neighbors': [],
'steps': 1000000,
}
for (i, j), node in nodes.items():
for neighbor in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if neighbor in nodes and nodes[neighbor]['value'] <= node['value'] + 1:
node['neighbors'].append(neighbor)
# Breadth-first search the graph to calculate steps to get to each node
nodes[start]['steps'] = 0
queue = [start]
while queue:
node = nodes[queue.pop(0)]
for neighbor_location in node['neighbors']:
neighbor = nodes[neighbor_location]
steps = node['steps'] + 1
if steps < neighbor['steps']:
neighbor['steps'] = steps
queue.append(neighbor_location)
return min(node['steps'] for node in nodes.values() if node['value'] == 25)
def day_13_part_1():
"""Solve Day 13 Part 1 pair matching puzzle."""
LOWER, SAME, HIGHER = -1, 0, 1
with open('day_13.txt') as in_file:
pairs = [
[json.loads(row) for row in pair.strip().split('\n')]
for pair in in_file.read().split('\n\n')
]
def compare(left, right):
"""Recursively compare left and right pairs."""
if left is None:
return LOWER
if right is None:
return HIGHER
if isinstance(left, int) and isinstance(right, int):
if left < right:
return LOWER
if left > right:
return HIGHER
return SAME
if isinstance(left, list) and isinstance(right, list):
for l, r in itertools.zip_longest(left, right):
result = compare(l, r)
if result != SAME:
return result
return SAME
return compare(
[left] if isinstance(left, int) else left,
[right] if isinstance(right, int) else right
)
return sum(i for i, pair in enumerate(pairs, 1) if compare(*pair) == LOWER)
def day_13_part_2():
"""Solve Day 13 Part 2 pair matching puzzle."""
LOWER, SAME, HIGHER = -1, 0, 1
dividers = [[2]], [[6]]
with open('day_13.txt') as in_file:
packets = [
json.loads(row) for row in in_file.read().split('\n')
if row.strip()
]
packets += dividers
def compare(left, right):
"""Recursively compare left and right pairs."""
if left is None:
return LOWER
if right is None:
return HIGHER
if isinstance(left, int) and isinstance(right, int):
if left < right:
return LOWER
if left > right:
return HIGHER
return SAME
if isinstance(left, list) and isinstance(right, list):
for l, r in itertools.zip_longest(left, right):
result = compare(l, r)
if result != SAME:
return result
return SAME
return compare(
[left] if isinstance(left, int) else left,
[right] if isinstance(right, int) else right
)
packets.sort(key=functools.cmp_to_key(compare))
first, second = [packets.index(divider) for divider in dividers]
return (first + 1) * (second + 1)
def day_14_part_1():
"""Solve Day 14 Part 1 sand filling puzzle."""
AIR, SAND, ROCK, SOURCE = '.', 'o', '#', '+'
with open('day_14.txt') as in_file:
rock_paths = [json.loads(f"[[{row.replace('->', '],[')}]]")
for row in in_file]
# Normalize the data to simplify visualization
min_x, max_x, max_y = 1000, 0, 0
for rock_path in rock_paths:
for x, y in rock_path:
min_x, max_x, max_y = min(min_x, x), max(max_x, x), max(max_y, y)
for i, rock_path in enumerate(rock_paths):
rock_paths[i] = [(x - min_x, y) for x, y in rock_path]
max_x -= min_x
grid = [[AIR] * (max_y + 1) for _ in range(max_x + 1)]
source = (500 - min_x, 0)
grid[source[0]][source[1]] = SOURCE
# Load grid with rocks
for rock_path in rock_paths:
for (x1, y1), (x2, y2) in zip(rock_path[:-1], rock_path[1:]):
if y1 == y2:
start, end = min(x1, x2), max(x1, x2) + 1
points = ((x, y1) for x in range(start, end))
elif x1 == x2:
start, end = min(y1, y2), max(y1, y2) + 1
points = ((x1, y) for y in range(start, end))
for x, y in points:
grid[x][y] = ROCK
# Fill structure with sand until full
done = False
number_of_grains = 0
while not done:
x, y = source
while True:
if y == max_y:
done = True
break
elif x in [-1, max_x] or grid[x][y + 1] == AIR:
y += 1
elif x == 0 or grid[x - 1][y + 1] == AIR:
x, y = x - 1, y + 1
elif x == max_x or grid[x + 1][y + 1] == AIR:
x, y = x + 1, y + 1
else:
break
if not done:
number_of_grains += 1
grid[x][y] = SAND
# print('\n'.join([''.join(row) for row in zip(*grid)]))
return number_of_grains
def day_14_part_2():
"""Solve Day 14 Part 2 sand filling puzzle."""
AIR, SAND, ROCK, SOURCE = '.', 'o', '#', '+'
with open('day_14.txt') as in_file:
rock_paths = [json.loads(f"[[{row.replace('->', '],[')}]]")
for row in in_file]
# Normalize the data to simplify visualization
min_x, max_x, max_y = 1000, 0, 0
for rock_path in rock_paths:
for x, y in rock_path:
min_x, max_x, max_y = min(min_x, x), max(max_x, x), max(max_y, y)
# Add very large ("infinite") floor
min_x, max_x, max_y = min_x - 500, max_x + 500, max_y + 2
rock_paths.append([[min_x, max_y], [max_x, max_y]])
for i, rock_path in enumerate(rock_paths):
rock_paths[i] = [(x - min_x, y) for x, y in rock_path]
max_x -= min_x
grid = [[AIR] * (max_y + 1) for _ in range(max_x + 1)]
source = (500 - min_x, 0)
grid[source[0]][source[1]] = SOURCE
# Load grid with rocks
for rock_path in rock_paths:
for (x1, y1), (x2, y2) in zip(rock_path[:-1], rock_path[1:]):
if y1 == y2:
start, end = min(x1, x2), max(x1, x2) + 1
points = ((x, y1) for x in range(start, end))
elif x1 == x2:
start, end = min(y1, y2), max(y1, y2) + 1
points = ((x1, y) for y in range(start, end))
for x, y in points:
grid[x][y] = ROCK
# Fill structure with sand until full
number_of_grains = 0
while True:
x, y = source
while True:
if grid[x][y + 1] == AIR:
y += 1
elif grid[x - 1][y + 1] == AIR:
x, y = x - 1, y + 1
elif grid[x + 1][y + 1] == AIR:
x, y = x + 1, y + 1
else:
break
number_of_grains += 1
grid[x][y] = SAND
if (x, y) == source:
break
return number_of_grains
def day_15_part_1():
"""Solve Day 15 Part 1 sensor-beacon puzzle."""
pattern = re.compile(r'Sensor at x=(\d+), y=(\d+): '
r'closest beacon is at x=(-?\d+), y=(-?\d+)\n')
with open('day_15.txt') as in_file:
sensors = [[int(x) for x in pattern.match(row).groups()]
for row in in_file]
# Keep a set of all x coords where a beacon cannot be located
y_target = 2_000_000
no_beacon = set()
for x_sensor, y_sensor, x_beacon, y_beacon in sensors:
radius = abs(x_beacon - x_sensor) + abs(y_beacon - y_sensor)
if y_sensor - radius <= y_target <= y_sensor + radius:
dy = abs(y_target - y_sensor)
dx = radius - dy
no_beacon.update({*range(x_sensor - dx, x_sensor + dx + 1)})
# Remove beacons that may exist in the target row
for _, _, x_beacon, y_beacon in sensors:
if y_beacon == y_target and x_beacon in no_beacon:
no_beacon.remove(x_beacon)
return len(no_beacon)
def day_15_part_2():
"""Solve Day 15 Part 2 sensor-beacon puzzle."""
pattern = re.compile(r'Sensor at x=(\d+), y=(\d+): '
r'closest beacon is at x=(-?\d+), y=(-?\d+)\n')
with open('day_15.txt') as in_file:
sensors = [[int(x) for x in pattern.match(row).groups()]
for row in in_file]
# Keep a set of all x coord ranges where a beacon cannot be located
max_coordinate = 4_000_000
y_targets = range(max_coordinate + 1)
for y_target in y_targets:
no_beacon = []
for x_sensor, y_sensor, x_beacon, y_beacon in sensors:
radius = abs(x_beacon - x_sensor) + abs(y_beacon - y_sensor)
if y_sensor - radius <= y_target <= y_sensor + radius:
dy = abs(y_target - y_sensor)
dx = radius - dy
left = min(max(x_sensor - dx, 0), max_coordinate)
right = min(max(x_sensor + dx, 0), max_coordinate)
no_beacon.append((left, right))
no_beacon.sort()
i = 1
while i < len(no_beacon):
x1_min, x1_max = no_beacon[0]
x2_min, x2_max = no_beacon[i]
if x2_min - 1 <= x1_max < x2_max:
no_beacon[0] = (x1_min, x2_max)
i += 1
x = no_beacon[0][1]
if x != max_coordinate:
break
return (x + 1) * 4_000_000 + y_target
def day_16_part_1():
"""Solve Day 16 Part 1 valve opening puzzle."""
pattern = re.compile(r'Valve (\w+) has flow rate=(\d+); '
r'tunnels? leads? to valves? (.+)\n')
valves = {}
with open('day_16.txt') as in_file:
for row in in_file:
valve, rate, neighbors = pattern.match(row).groups()
valves[valve] = {
'rate': int(rate),
'neighbors': neighbors.split(', '),
}
# Important! Convert the valves into a weighted graph containing only
# nodes with usable valves (rate > 0). This greatly simplifies the search
# space and smooths over corner cases.
indices = {v: i for i, v in enumerate(valves)}
distances = [[1000] * len(indices) for _ in indices]
for name, valve in valves.items():
valve_index = indices[name]
for neighbor in valve['neighbors']:
neighbor_index = indices[neighbor]
distances[valve_index][neighbor_index] = 1
# Floyd–Warshall DP algorithm for calculating edge weights
for k, i, j in itertools.product(indices.values(), indices.values(), indices.values()):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
root = 'AA'
nodes = [
{'name': name, 'rate': valve['rate']}
for name, valve in valves.items()
if valve['rate'] > 0 or name == root
]
for i, node in enumerate(nodes):
node['neighbors'] = {
j: distances[indices[node['name']]][indices[neighbor['name']]]
for j, neighbor in enumerate(nodes)
if i != j
}
root_index = next(i for i, node in enumerate(nodes) if node['name'] == root)
depth = 30
max_score = 0
queue = [{
'node': root_index,
'steps': 0,
'traversed': [False] * len(nodes),
'score': 0,
}]
while queue:
entry = queue.pop()
if entry['steps'] == depth:
max_score = max(entry['score'], max_score)
else:
moved = False
i = entry['node']
for j, distance in nodes[i]['neighbors'].items():
new_step = entry['steps'] + distance + 1
if new_step + distance < depth + 1 and not entry['traversed'][j]:
moved = True
new_traversed = entry['traversed'].copy()
new_traversed[i] = True
new_traversed[j] = True
new_score = entry['score'] + nodes[j]['rate'] * (depth - new_step)
queue.append({
'node': j,
'steps': new_step,
'traversed': new_traversed,
'score': new_score,
})
if not moved:
queue.append({
'node': entry['node'],
'steps': depth,
'traversed': entry['traversed'],
'score': entry['score'],
})
return max_score
def day_16_part_2():
"""Solve Day 16 Part 2 valve opening puzzle.
This took me a *long* time. The breakthrough came from simplifying the
valves into a weighted graph.
"""
pattern = re.compile(r'Valve (\w+) has flow rate=(\d+); '
r'tunnels? leads? to valves? (.+)\n')
valves = {}
with open('day_16.txt') as in_file:
for row in in_file:
valve, rate, neighbors = pattern.match(row).groups()
valves[valve] = {
'rate': int(rate),
'neighbors': neighbors.split(', '),
}
# Important! Convert the valves into a weighted graph containing only
# nodes with usable valves (rate > 0). This greatly simplifies the search
# space and smooths over corner cases.
indices = {v: i for i, v in enumerate(valves)}
distances = [[1000] * len(indices) for _ in indices]
for name, valve in valves.items():
valve_index = indices[name]
for neighbor in valve['neighbors']:
neighbor_index = indices[neighbor]
distances[valve_index][neighbor_index] = 1
# Floyd–Warshall DP algorithm for calculating edge weights
for k, i, j in itertools.product(indices.values(), indices.values(), indices.values()):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
root = 'AA'
nodes = [
{'name': name, 'rate': valve['rate']}
for name, valve in valves.items()
if valve['rate'] > 0 or name == root
]
for i, node in enumerate(nodes):
node['neighbors'] = {
j: distances[indices[node['name']]][indices[neighbor['name']]]
for j, neighbor in enumerate(nodes)
if i != j
}
root_index = next(i for i, node in enumerate(nodes) if node['name'] == root)
depth = 26
max_score = 0
queue = [{
'nodes': [root_index, root_index],
'steps': [0, 0],
'traversed': [False] * len(nodes),
'score': 0,
}]
while queue:
entry = queue.pop()
if all(step == depth for step in entry['steps']):
max_score = max(entry['score'], max_score)
else:
options = [[] for _ in entry['nodes']]
for i, option, step in zip(entry['nodes'], options, entry['steps']):
for j, distance in nodes[i]['neighbors'].items():
if step + distance < depth and not entry['traversed'][j]:
option.append([j, step + distance + 1])
if not option:
option.append([i, depth])
for (i, step_1), (j, step_2) in itertools.product(*options):
# Cannot flip same valve
if i == j:
continue
new_score = entry['score'] + (
nodes[i]['rate'] * (depth - step_1) +
nodes[j]['rate'] * (depth - step_2)
)
# A manual heuristic to chop paths that are not scoring well
if new_score + 100 * (depth - min(step_1, step_2)) > max_score:
new_traversed = entry['traversed'].copy()
new_traversed[i] = True
new_traversed[j] = True
queue.append({
'nodes': [i, j],
'steps': [step_1, step_2],
'traversed': new_traversed,
'score': new_score,
})
return max_score
parser = argparse.ArgumentParser(description="Run 2022 Advent of Code solutions.")
parser.add_argument('day', type=int, choices=range(1, 26), metavar='[1, 25]',
help='Advent code day to run.')
args = parser.parse_args()
part_1, part_2 = locals()[f'day_{args.day}_part_1'], locals()[f'day_{args.day}_part_2']
print(f"Part 1:\n{part_1()}\n")
print(f"Part 2:\n{part_2()}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment