Fixed, thanks!
Python
Both of my solutions make use of a Heap and a Disjoint-Set-Union / Union-Find data structure
Part 1: Use a heap to keep 1000 shortest connections, then union them all in DSU and get the 3 largest connected components.
Part 2: Use a heap to keep all connections, then union the shortest ones until all components are connected.
click to view code
import heapq as hq
from itertools import combinations
from collections import Counter
# Disjoint Set Union (or Union-Find) data structure
# with path compression and union by rank
class DSU:
def __init__(self, size: int) -> None:
self.parent = list(range(size)) # ith value is the parent node to node i
self.rank = [1] * size # max depth of subtree rooted here (used for union by rank)
def find(self, x: int) -> int:
# if the node is not its own parent, we need to recurse on parent
if x != self.parent[x]:
# path compression
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def isConnected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
# returns a boolean whether or not union was needed
def union(self, x: int, y: int) -> bool:
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
# no union needed
return False
if self.rank[rootX] > self.rank[rootY]:
# rootX has deeper subtree, therefore set it as parent to rootY (and its subtree)
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
# rootY has deeper subtree, therefore set it as parent to rootX (and its subtree)
self.parent[rootX] = rootY
else:
# both subtrees are of equal depth, therefore choose either one of them as the parent of the other
# here we chose rootX as the parent of rootY, therefore rootX depth increases by 1
self.parent[rootY] = rootX
self.rank[rootX] += 1
# union complete
return True
# parse puzzle input into junction coordinates (x, y, z)
def parse_junctions(data: str):
return [tuple(map(int, line.split(','))) for line in data.splitlines()]
# get distance between two points in 3D space
# skipping the sqrt because we only care about relative distances
def get_dist(p1, p2):
x1, y1, z1 = p1
x2, y2, z2 = p2
return (x2 - x1) ** 2 + (y2 - y1) ** 2 + (z2 - z1) ** 2
def part1(data: str, max_connections: int = 1000):
junctions = parse_junctions(data)
n = len(junctions)
# <max_connections> shortest connections
closest_connections = []
# iterate over all pairs of junctions
# combinations is just some syntactic sugar to avoid a nested for loop (still O(n^2))
for i, j in combinations(range(n), 2):
dist = get_dist(junctions[i], junctions[j])
# keep <max_connections> closest connections
# have to use -dist to simulate max heap
if len(closest_connections) < max_connections:
hq.heappush(closest_connections, (-dist, i, j))
else:
hq.heappushpop(closest_connections, (-dist, i, j))
# union all the closest connections
dsu = DSU(n)
for _, i, j in closest_connections:
dsu.union(i, j)
# count all circuit sizes
circuit_sizes = Counter()
for i in range(n):
circuit_sizes[dsu.find(i)] += 1
# multiply the sizes of the 3 largest circuits
ans = 1
for _, f in circuit_sizes.most_common(3):
ans *= f
return ans
def part2(data: str):
junctions = parse_junctions(data)
n = len(junctions)
# all n^2 junction connections
all_connections = []
# combinations is just some syntactic sugar to avoid a nested for loop (still O(n^2))
for i, j in combinations(range(n), 2):
dist = get_dist(junctions[i], junctions[j])
all_connections.append((dist, i, j))
# create min heap of all connections
# Heapify later to benefit from the heapify algorithm (O(n) instead of O(n log n))
hq.heapify(all_connections)
# connect junctions until all are connected
dsu = DSU(n)
unions = 0
while all_connections:
_, i, j = hq.heappop(all_connections)
unions += dsu.union(i, j)
# if we have n-1 unions, that means all n junctions are connected
if unions == n-1:
return junctions[i][0] * junctions[j][0]
assert False, "It's not possible that all junctions never connect"
sample = """162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689"""
assert part1(sample, max_connections=10) == 40
assert part2(sample) == 25272
Python
Not too difficult, especially since there are no edge cases (particles leaving the grid, adjacent splitters).
My initial solution mutated the input for the simulation which I cleaned up after by creating an array that would record the number of particle paths at every column location + some other optimizations. I chose to implement both parts in the same function because they share the majority of the logic.
click to view code
def solve(data: str):
grid = data.splitlines()
m, n = len(grid), len(grid[0])
# find the first particle
particle_paths = [0] * n # count of particle paths that will reach this column
for j in range(n):
if grid[0][j] == 'S':
particle_paths[j] = 1
break
# count the number of splits for part 1
splits = 0
# simulate the particle moving down the grid
# optimization 1: we can start from the 3rd row (index 2) because that's where the first splitter is
# optimization 2: we can skip alternating rows because every other row is empty
for i in range(2, m, 2):
# particle paths per column after this row is processed
next_particle_paths = [0] * n
for j in range(n):
if particle_paths[j] == 0:
# skip if there are no particle paths coming from above in this column
continue
if grid[i][j] == '.':
# no splitter here, the number of paths in this column remains the same
# make sure to use += to account for neighboring splitters dumping additional paths into this column
next_particle_paths[j] += particle_paths[j]
else:
# splitter activated here, any particle arriving here can end up in the left or right column
# this can be simulated by adding the number of paths to the columns on either side
splits += 1
next_particle_paths[j-1] += particle_paths[j]
next_particle_paths[j+1] += particle_paths[j]
# update vars for next iteration
particle_paths = next_particle_paths
# return both
# the number of splits AND
# the count of timelines a particle would create
return splits, sum(particle_paths)
sample = """.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
..............."""
assert solve(sample) == (21, 40)
Python
For part1, regex is king. Thought about rotating the grid for part2, but going column by column is simple enough.
view code
import re
from operator import add, mul
def part1(data: str):
# split into row, but do not split into cells yet
rows = data.splitlines()
m = len(rows) # number of rows
# initialize the result and operator arrays
# the operators array will store the operator function for each column block
# the result array will store the initial value for each column block
operators = []
res = []
# using regex to skip variable number of spaces
for symbol in re.findall(r'\S', rows[-1]):
if symbol == '+':
operators.append(add)
res.append(0)
elif symbol == '*':
operators.append(mul)
res.append(1)
n = len(res) # number of columns
# iterate through each row, except the last one
for i in range(m-1):
# use regex to find all numbers in the row
for j, num in enumerate(map(int, re.findall(r'\d+', rows[i]))):
# apply the operator to update the result for the appropriate column
res[j] = operators[j](res[j], num)
return sum(res)
def part2(data: str):
# completely split into grid
grid = [list(line) for line in data.splitlines()]
m, n = len(grid), len(grid[0])
res = 0
curr = None # current value of the block
op = None # operator for the block
for j in range(n):
if curr is None:
# we just started a new block
# update the current value and operator based on the symbol
symbol = grid[-1][j]
curr = 0 if symbol == '+' else 1
op = add if symbol == '+' else mul
# read the number from the column
num = 0
for i in range(m-1):
if grid[i][j] != ' ':
num = num * 10 + int(grid[i][j])
# if there is no number, we are at the end of a block
if num == 0:
# add the block value to the result
# and reset the current value and operator
res += curr
curr = None
op = None
continue
# otherwise, update the current value using the operator
curr = op(curr, num)
# finally, don't forget to add the last block value that's being tracked
res += curr
return res
sample = """123 328 51 64
45 64 387 23
6 98 215 314
* + * + """
assert part1(sample) == 4277556
assert part2(sample) == 3263827
Here we see, another innocent victim being drawn into the addictive clutches of Cracktorio. The factory must grow.
Python
Not too bad though part2 could become difficult if you don't realize the simple method to merge overlapping intervals.
see code
# takes a list of (start, end) ranges and merges overlapping ones
def merge_overlapping_ranges(ranges: list[tuple[int, int]]) -> list[tuple[int, int]]:
# sort ranges by start so that overlaps are adjacent
ranges.sort(key=lambda r: r[0])
merged_ranges = []
# keep track of a current range that could be merged into
curr_start, curr_end = ranges[0]
for start, end in ranges:
if curr_start <= start <= curr_end:
# overlap, extend current range
curr_end = max(curr_end, end)
else:
# no overlap, save current range and record the new one
merged_ranges.append((curr_start, curr_end))
curr_start, curr_end = start, end
# finally, don't forget to add the last range that's being tracked
merged_ranges.append((curr_start, curr_end))
return merged_ranges
def part1(data: str):
# split input
freshness_data, ingredients_data = data.split("\n\n")
# parse data
freshness_ranges = [tuple(map(int, f.split('-'))) for f in freshness_data.splitlines()]
freshness_ranges = merge_overlapping_ranges(freshness_ranges) # optimization: merge overlapping ranges
ingredients = [int(i) for i in ingredients_data.splitlines()]
# checks if an ingredient is fresh
# this could've been done with binary search, but linear search is simpler and fast enough
def is_fresh(ingredient: int) -> bool:
for start, end in freshness_ranges:
if start <= ingredient <= end:
# found
return True
if start > ingredient:
# quit early since we are past any range that could've contained the ingredient
return False
return False
# count all fresh ingredients
return sum(is_fresh(i) for i in ingredients)
def part2(data: str):
# split input
freshness_data, _ = data.split("\n\n")
# parse data
freshness_ranges = [tuple(map(int, f.split('-'))) for f in freshness_data.splitlines()]
freshness_ranges = merge_overlapping_ranges(freshness_ranges) # merge overlapping ranges
# return total count of fresh ingredients
# we add +1 because both start and end are inclusive
return sum(end - start + 1 for start, end in freshness_ranges)
sample = """3-5
10-14
16-20
12-18
1
5
8
11
17
32"""
assert part1(sample) == 3
assert part2(sample) == 14
Python
Simple brute-force is enough.
DIRECTIONS = [
(0, 1), (1, 0), (0, -1), (-1, 0), # cardinal
(1, 1), (1, -1), (-1, 1), (-1, -1) # diagonal
]
# yield all valid neighbor coordinates
def yield_neighbors(i, j, m, n):
for di, dj in DIRECTIONS:
ni, nj = i+di, j+dj
if 0 <= ni < m and 0 <= nj < n:
yield ni, nj
# build char grid from input data
def build_grid(data: str):
return [list(row) for row in data.splitlines()]
def part1(data: str):
grid = build_grid(data)
m, n = len(grid), len(grid[0])
# count accessible rolls
accessible = 0
for i in range(m):
for j in range(n):
if grid[i][j] != '@':
continue
neighbor_rolls = sum(grid[ni][nj] == '@' for ni, nj in yield_neighbors(i, j, m, n))
if neighbor_rolls < 4:
accessible += 1
return accessible
def part2(data: str):
grid = build_grid(data)
m, n = len(grid), len(grid[0])
total_accessible = 0 # total accessible rolls over all cycles
accessible = None # rolls accessible this cycle
# repeat until no more rolls can be accessed
while accessible != 0:
accessible = 0
for i in range(m):
for j in range(n):
if grid[i][j] != '@':
continue
neighbor_rolls = sum(grid[ni][nj] == '@' for ni, nj in yield_neighbors(i, j, m, n))
if neighbor_rolls < 4:
accessible += 1
# we can immediately remove this roll, no need to wait for next cycle
grid[i][j] = '.'
# accumulate accessible rolls this cycle
total_accessible += accessible
return total_accessible
sample = """<paste sample here>"""
assert part1(sample) == 13
assert part2(sample) == 43
Python
This was the easier one for me out of the first 3 days. Cleaned up my solution before posting for better readability:
# get joltage of picked batteries
def get_joltage(batteries_picked: list[int]):
bank_joltage = 0
for batt in batteries_picked:
bank_joltage = bank_joltage * 10 + batt
return bank_joltage
# get maximum joltage of a bank
def get_bank_joltage(bank: str, pick_limit = 2) -> int:
# pick first <pick_limit> batteries
batteries_picked = [int(bank[i]) for i in range(pick_limit)]
max_joltage = get_joltage(batteries_picked)
# iterate over remaining batteries
for i in range(pick_limit, len(bank)):
batt = int(bank[i])
# we add batt for selection consideration
batteries_picked.append(batt)
# If all batteries are in descending order and batt is the lowest,
# we will eventually discard batt
to_discard = pick_limit
# However if not, we discard the leftmost MSB battery which has lower joltage than its successor
# and shift all batteries left with batt added at the end.
# This guarantees that we keep the maximum lexicographical order of picked batteries
# regardless of batt's value.
for i in range(pick_limit):
if batteries_picked[i] < batteries_picked[i+1]:
to_discard = i
break
batteries_picked.pop(to_discard)
# update max_joltage, it may have increased
max_joltage = max(max_joltage, get_joltage(batteries_picked))
return max_joltage
# part 1 asserts
assert get_bank_joltage("987654321111111", pick_limit=2) == 98
assert get_bank_joltage("811111111111119", pick_limit=2) == 89
assert get_bank_joltage("234234234234278", pick_limit=2) == 78
assert get_bank_joltage("818181911112111", pick_limit=2) == 92
# part 2 asserts
assert get_bank_joltage("987654321111111", pick_limit=12) == 987654321111
assert get_bank_joltage("811111111111119", pick_limit=12) == 811111111119
assert get_bank_joltage("234234234234278", pick_limit=12) == 434234234278
assert get_bank_joltage("818181911112111", pick_limit=12) == 888911112111
# get total joltage of a set of banks
def solve(data: str, pick_limit = 2):
total_joltage = 0
for bank in data.splitlines():
total_joltage += get_bank_joltage(bank, pick_limit)
return total_joltage
# asserts for sample data
sample = """987654321111111
811111111111119
234234234234278
818181911112111"""
assert solve(sample, pick_limit=2) == 357 # part 1
assert solve(sample, pick_limit=12) == 3121910778619 # part 2
Oh please yes! There have been so many times I've pressed back from a post / post image, only to end up on the communities tab with no way to go back.
You can always add a "Don't ask again" checkbox on the popup for the people who don't need it.
Python
Just putting the solution to part 3 here, because these solutions are pretty long. Took me a while to figure out that an optimal return path from the bottom of the volcano burn can bleed into the left quadrant.
from collections import deque
import heapq as hq
import re
DIRECTIONS_CARDINAL = [(-1, 0), (0, 1), (1, 0), (0, -1)]
DIRECTIONS_ALL = [
*DIRECTIONS_CARDINAL, # cardinal
(-1, -1), (-1, 1), (1, -1), (1, 1) # diagonal
]
# yields all 8 possible neighbors
# lava spreads in all 8 directions
def yield_all_neighbors(i, j, m, n):
for di, dj in DIRECTIONS_ALL:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
yield ni, nj
# yields only the 4 possible cardinal neighbors
# the dragonduck can only move in cardinal directions
def yield_cardinal_neighbors(i, j, m, n):
for di, dj in DIRECTIONS_CARDINAL:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
yield ni, nj
# finds a special character in the grid
def find_char(data: str, ch: str):
i = 0
for row in data.splitlines():
j = row.find(ch)
if j != -1:
return (i, j)
i += 1
assert False, f"Character {ch} not found in grid"
# returns squared distance between two points
def get_dist_sq(a, b):
x1, y1 = a
x2, y2 = b
return (x2 - x1) ** 2 + (y2 - y1) ** 2
# Generator to burn cells permanently one step at a time
def bfs_burn(grid, volcano):
m, n = len(grid), len(grid[0])
queue = deque([volcano])
visited = set()
step = 0
while queue:
nq = len(queue)
for _ in range(nq):
i, j = queue.popleft()
if (i, j) in visited:
continue
# skip cells outside the current step radius
# but do not mark them as visited yet
if get_dist_sq((i, j), volcano) > (step * step):
continue
visited.add((i, j))
# burn cell permanently
grid[i][j] = -1
for ni, nj in yield_all_neighbors(i, j, m, n):
if (ni, nj) in visited:
continue
queue.append((ni, nj))
step += 1
# yield here to allow enclosing the volcano after each step
yield step
def part3(data: str):
# initialize variables
start = find_char(data, 'S')
volcano = find_char(data, '@')
data = re.sub(r'[@S]', '0', data)
grid = [[int(c) for c in row] for row in data.splitlines()]
m, n = len(grid), len(grid[0])
# initialize lava generator
lava_spreader = bfs_burn(grid, volcano)
# Finds shortest path from start to dest within time limit
# Dijkstra's algorithm with constraints
def find_shortest_path(start: tuple[int, int], dest: tuple[int, int], volcano_col: int, time_limit, map_half):
candidates = [(0, start[0], start[1])]
visited = set()
while candidates:
cost, i, j = hq.heappop(candidates)
if (i, j) in visited:
continue
visited.add((i, j))
if (i, j) == dest:
# if we are processing the destination, we have found the shortest path to it
return cost
if cost > time_limit:
# if we have exceeded the time limit, prune this path
continue
# remember: the dragonduck can only move in cardinal directions
for ni, nj in yield_cardinal_neighbors(i, j, m, n):
# skip visited or burned cells
if (ni, nj) in visited or grid[ni][nj] == -1:
continue
# if processing left half, skip paths going to the right of the volcano
if map_half == 'left' and nj > volcano_col:
continue
# if processing right half, skip paths going to the left of the volcano (ONLY for bottom quadrant)
# allow moving into the left half in the top quadrant (!!!)
elif map_half == 'right' and (ni > m // 2 and nj < volcano_col):
continue
# add new candidate path
hq.heappush(candidates, (cost + grid[ni][nj], ni, nj))
# we couldn't reach the destination within time limit
# fail by returning the maximum possible cost
return 9 * m * n
# try increasing lava spreads
while True:
# spread lava one more step
step = next(lava_spreader)
# calculate time limit
time = step * 30
# our paths from the start must connect at the bottom of the lava burn
burn_bottom_boundary = (volcano[0] + step, volcano[1])
time_taken = find_shortest_path(start, burn_bottom_boundary, volcano[1], time, 'left')
if time_taken >= time:
# if we already exceeded time, quit early
continue
time_taken += find_shortest_path(burn_bottom_boundary, start, volcano[1], time - time_taken, 'right')
if time_taken >= time:
# if we exceeded time, try next lava spread
continue
# we successfully enclosed the volcano within time
burn_radius = step - 1
return time_taken * burn_radius
Python
def part1(data: str):
elements = map(int, data.split(','))
total = 0
for ele in elements:
# a spell element will add (90 // number) bricks for 90 columns
total += 90 // ele
return total
assert part1("1,2,3,5,9") == 193
# Gets all spell elements needed to build a wall
# Useful for part 2 and part 3
def get_elements(data: str):
wall = map(int, data.split(','))
elements = [] # spell elements
for col_idx, fragments in enumerate(wall):
# fix for 1-based indexing
col = col_idx + 1
# account bricks for recorded elements
for ele in elements:
if col % ele == 0:
fragments -= 1
# if we still have fragments, we need to add a new element with that column number
if fragments > 0:
elements.append(col)
return elements
def part2(data: str):
# Get all spell elements needed to build the wall
elements = get_elements(data)
# return product of all elements
ans = 1
for ele in elements:
ans *= ele
return ans
assert part2("1,2,2,2,2,3,1,2,3,3,1,3,1,2,3,2,1,4,1,3,2,2,1,3,2,2") == 270
# Part 3: Binary Search for maximum full columns
def part3(data: str):
BRICKS = 202520252025000
elements = get_elements(data)
# Check if we can build 'cols' full columns within BRICKS bricks
def can_build(cols: int) -> bool:
bricks_used = 0
for ele in elements:
bricks_used += cols // ele
if bricks_used > BRICKS:
return False
return True
# binary search: break on first column size we cannot build
lo = 1
hi = BRICKS
while lo < hi:
mid = lo + (hi - lo) // 2
if can_build(mid):
lo = mid + 1
else:
hi = mid
# if lo is the first we cannot build, lo - 1 is the maximum we can build
return lo - 1
assert part3("1,2,2,2,2,3,1,2,3,3,1,3,1,2,3,2,1,4,1,3,2,2,1,3,2,2") == 94439495762954
That and the else (no-break) clause for loops are some of my favorite features.