Advent of Code Prep: Advanced Techniques
· by Michael Doornbos · 2197 words
This is part 3 of a three-part series on preparing for Advent of Code. See the main overview for the complete roadmap, Part 1: Foundation for parsing and data structures, or Part 2: Core Skills for grids and basic traversal.
You’ve got the foundation. You can navigate grids and traverse graphs with BFS and DFS. Now for the techniques that unlock the harder puzzles—the ones where brute force fails and you need a smarter approach.
Dijkstra’s Algorithm: Weighted Shortest Paths
BFS finds the shortest path when every step costs the same. But what if some steps cost more than others? A maze where moving through mud takes 3 steps while moving on road takes 1? That’s where Dijkstra’s algorithm shines.
The core idea
Always process the node with the lowest total cost first. This guarantees that when you reach a node, you’ve found the cheapest way to get there.
import heapq
def dijkstra(graph, start, end):
"""
Find shortest path in weighted graph.
graph[node] = [(neighbor, cost), ...]
"""
# Priority queue: (total_cost, node)
pq = [(0, start)]
visited = set()
while pq:
cost, node = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
if node == end:
return cost
for neighbor, edge_cost in graph[node]:
if neighbor not in visited:
heapq.heappush(pq, (cost + edge_cost, neighbor))
return -1 # No path exists
How the heap works
heapq is Python’s priority queue. It always pops the smallest element:
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappop(heap) # 2
heapq.heappop(heap) # 5
heapq.heappop(heap) # 8
For tuples, it compares by first element, then second. So (cost, node) sorts by cost first.
Grid example with terrain costs
import heapq
def dijkstra_grid(grid, start, end):
"""
Find lowest-cost path through grid.
Cell values are movement costs (1-9).
"""
rows, cols = len(grid), len(grid[0])
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
pq = [(0, start)]
costs = {start: 0}
while pq:
cost, (r, c) = heapq.heappop(pq)
if (r, c) == end:
return cost
if cost > costs.get((r, c), float('inf')):
continue
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
# Cost to enter the new cell
new_cost = cost + int(grid[nr][nc])
if new_cost < costs.get((nr, nc), float('inf')):
costs[(nr, nc)] = new_cost
heapq.heappush(pq, (new_cost, (nr, nc)))
return -1
Note: We use a costs dictionary instead of a visited set. This handles the case where we might reach the same node via different paths with different costs.
AoC twist: State includes more than position
Sometimes the “node” isn’t just a position—it’s position plus some state. Maybe you’re carrying keys. Maybe you can only turn, not move. The cost function might depend on direction.
def dijkstra_with_direction(grid, start, end):
"""
Movement costs 1, turning costs 1000.
State is (row, col, direction).
"""
rows, cols = len(grid), len(grid[0])
DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)] # N, E, S, W
# Start facing East (index 1)
pq = [(0, (start[0], start[1], 1))]
visited = set()
while pq:
cost, (r, c, d) = heapq.heappop(pq)
if (r, c) == end:
return cost
if (r, c, d) in visited:
continue
visited.add((r, c, d))
# Move forward
dr, dc = DIRS[d]
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
heapq.heappush(pq, (cost + 1, (nr, nc, d)))
# Turn left or right (costs 1000)
heapq.heappush(pq, (cost + 1000, (r, c, (d + 1) % 4)))
heapq.heappush(pq, (cost + 1000, (r, c, (d - 1) % 4)))
return -1
The state is (row, col, direction). Turning is expensive, so the algorithm finds paths that minimize turning.
Reconstructing the path
To get the actual path, track where you came from:
def dijkstra_with_path(graph, start, end):
pq = [(0, start, [start])]
visited = set()
while pq:
cost, node, path = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
if node == end:
return cost, path
for neighbor, edge_cost in graph[node]:
if neighbor not in visited:
heapq.heappush(pq, (cost + edge_cost, neighbor, path + [neighbor]))
return -1, []
Backtracking: Try Everything Systematically
Some problems can’t be solved greedily—you need to explore possibilities and undo choices that don’t work out. Backtracking is systematic trial and error.
The pattern
def backtrack(state):
if is_solution(state):
return state # or record it
for choice in get_choices(state):
make_choice(state, choice)
result = backtrack(state)
if result is not None:
return result
undo_choice(state, choice) # Backtrack
return None # No solution found
The key is the undo step. After exploring a branch, you restore the state before trying the next option.
Example: N-Queens
Place N queens on an N×N board so none attack each other.
def solve_n_queens(n):
"""Find one valid placement of n queens."""
board = [['.'] * n for _ in range(n)]
def is_safe(row, col):
# Check column
for r in range(row):
if board[r][col] == 'Q':
return False
# Check diagonals
for r, c in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[r][c] == 'Q':
return False
for r, c in zip(range(row-1, -1, -1), range(col+1, n)):
if board[r][c] == 'Q':
return False
return True
def backtrack(row):
if row == n:
return True # All queens placed
for col in range(n):
if is_safe(row, col):
board[row][col] = 'Q' # Make choice
if backtrack(row + 1):
return True
board[row][col] = '.' # Undo choice
return False
backtrack(0)
return board
Example: Subset sum
Find a subset of numbers that adds to a target:
def subset_sum(numbers, target):
"""Find subset that sums to target, or None."""
def backtrack(index, current_sum, chosen):
if current_sum == target:
return chosen.copy()
if index >= len(numbers) or current_sum > target:
return None
# Choice 1: Include this number
chosen.append(numbers[index])
result = backtrack(index + 1, current_sum + numbers[index], chosen)
if result is not None:
return result
chosen.pop() # Undo
# Choice 2: Skip this number
return backtrack(index + 1, current_sum, chosen)
return backtrack(0, 0, [])
Pruning: Fail fast
Backtracking can be slow. The key optimization is detecting failure early:
def solve_puzzle(grid, pieces):
"""Place all pieces on grid."""
def backtrack(piece_idx):
if piece_idx == len(pieces):
return True # All pieces placed
piece = pieces[piece_idx]
# Pruning: Can remaining pieces even fit?
empty = count_empty(grid)
remaining_size = sum(len(p) for p in pieces[piece_idx:])
if empty < remaining_size:
return False
# Try each position
for r in range(rows):
for c in range(cols):
if can_place(grid, piece, r, c):
place(grid, piece, r, c)
if backtrack(piece_idx + 1):
return True
remove(grid, piece, r, c)
return False
return backtrack(0)
That pruning check eliminates entire branches of the search tree.
Finding all solutions
Sometimes you need every solution, not just one:
def all_solutions(state, solutions):
if is_solution(state):
solutions.append(copy_state(state))
return # Don't return early—keep searching
for choice in get_choices(state):
make_choice(state, choice)
all_solutions(state, solutions)
undo_choice(state, choice)
Counting solutions with memoization
If you only need the count, combine backtracking with memoization:
from functools import lru_cache
@lru_cache(maxsize=None)
def count_arrangements(index, remaining):
"""Count ways to arrange remaining items starting at index."""
if remaining == 0:
return 1
if index >= len(items) or remaining < 0:
return 0
# Include or skip current item
return (count_arrangements(index + 1, remaining - items[index]) +
count_arrangements(index + 1, remaining))
Union-Find: Dynamic Connected Components
Union-Find (also called Disjoint Set Union) efficiently tracks which elements belong to the same group, with groups that can merge over time.
The problem it solves
- “Are nodes A and B in the same connected component?”
- “Merge the component containing A with the component containing B.”
Both operations in nearly O(1) time.
The data structure
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
def find(self, x):
"""Find root of x's component, with path compression."""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""Merge components containing x and y."""
px, py = self.find(x), self.find(y)
if px == py:
return False # Already same component
# Union by rank: attach smaller tree under larger
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def connected(self, x, y):
"""Check if x and y are in same component."""
return self.find(x) == self.find(y)
def component_size(self, x):
"""Get size of component containing x."""
return self.size[self.find(x)]
How it works
Each element has a parent pointer. Initially, everyone is their own parent (each element is its own component). When you union two elements, you link one root to the other.
Two optimizations make it fast:
-
Path compression: In
find(), we update each node to point directly to the root. Future finds are faster. -
Union by rank: We attach the shorter tree under the taller one, keeping trees balanced.
Example: Counting islands dynamically
Given a grid that starts empty, cells become land one at a time. After each addition, count the number of islands.
def count_islands_dynamic(rows, cols, land_cells):
"""
land_cells is a list of (r, c) positions that become land.
Return list of island counts after each addition.
"""
uf = UnionFind(rows * cols)
grid = [[False] * cols for _ in range(rows)]
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def idx(r, c):
return r * cols + c
island_count = 0
results = []
for r, c in land_cells:
if grid[r][c]: # Already land
results.append(island_count)
continue
grid[r][c] = True
island_count += 1 # New island (might merge)
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc]:
if uf.union(idx(r, c), idx(nr, nc)):
island_count -= 1 # Merged two islands
results.append(island_count)
return results
Each new land cell starts as its own island. If it’s adjacent to existing land and merging actually joins two different components, the count decreases.
Example: Kruskal’s MST
Find minimum spanning tree using Union-Find:
def kruskal_mst(n, edges):
"""
edges is [(cost, u, v), ...]
Returns total cost of minimum spanning tree.
"""
edges.sort() # Sort by cost
uf = UnionFind(n)
total = 0
used = 0
for cost, u, v in edges:
if uf.union(u, v): # If this edge connects new components
total += cost
used += 1
if used == n - 1: # MST complete
break
return total if used == n - 1 else -1
Grid coordinates to indices
Union-Find uses integer indices. For grids, convert coordinates:
def idx(r, c, cols):
return r * cols + c
def coords(idx, cols):
return idx // cols, idx % cols
Putting It All Together
A classic AoC-style problem: Find the shortest path through a maze, but you need to collect all keys before reaching the exit, and doors can only be opened with matching keys.
import heapq
def solve_key_maze(grid):
"""
Find shortest path collecting all keys.
Keys are a-z, doors are A-Z, start is @, exit is !
"""
rows, cols = len(grid), len(grid[0])
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Find start and count keys
start = None
all_keys = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '@':
start = (r, c)
elif grid[r][c].islower():
all_keys |= (1 << (ord(grid[r][c]) - ord('a')))
# State: (row, col, keys_bitmask)
# Dijkstra with state
pq = [(0, start[0], start[1], 0)] # (cost, r, c, keys)
visited = set()
while pq:
cost, r, c, keys = heapq.heappop(pq)
if (r, c, keys) in visited:
continue
visited.add((r, c, keys))
# Win condition
if grid[r][c] == '!' and keys == all_keys:
return cost
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if not (0 <= nr < rows and 0 <= nc < cols):
continue
cell = grid[nr][nc]
if cell == '#':
continue
# Door requires key
if cell.isupper():
key_bit = 1 << (ord(cell.lower()) - ord('a'))
if not (keys & key_bit):
continue
# Collect key
new_keys = keys
if cell.islower():
new_keys |= (1 << (ord(cell) - ord('a')))
if (nr, nc, new_keys) not in visited:
heapq.heappush(pq, (cost + 1, nr, nc, new_keys))
return -1
This combines:
- Dijkstra (finding shortest path with state)
- Bitmasks (tracking collected keys)
- Grid navigation (movement and bounds checking)
Exercises
-
Weighted grid: Given a grid where each cell has a cost 1-9, find the lowest-cost path from top-left to bottom-right.
-
Sudoku solver: Use backtracking to solve a 9×9 Sudoku puzzle.
-
Percolation: Use Union-Find to check if water can flow from the top row to the bottom row through open cells.
-
Traveling salesman (small): Given 10 cities and distances, use backtracking with pruning to find the shortest tour visiting all cities.
-
Key collection: Modify the maze solver to find the shortest path that collects keys in alphabetical order.
What’s Next
You now have the complete toolkit for Advent of Code:
- Foundation: Parse any input, manipulate data structures fluently
- Core Skills: Navigate grids, traverse graphs, think recursively
- Advanced: Handle weighted graphs, explore systematically, track dynamic components
The only thing left is practice. Work through past AoC puzzles. When you get stuck, identify which technique applies. The pattern recognition comes with repetition.
See you in December.
Ready to put it all together? The Advent of Code archives are waiting. Days 15+ from any year will test these advanced techniques.
This was part 3 of a three-part series. Return to the main overview for the complete roadmap.