Today’s puzzle involves a combination lock with a rotating dial. We’re given a series of left (L) and right (R) rotations, and we need to count how many times the dial lands exactly on position 0 after completing each rotation.

The dial has 100 positions (0-99) and starts at position 50.

Let’s start by modeling the problem. A list of integers is perfect for representing rotations—we’ll use positive integers for right rotations and negative integers for left rotations. This lets us simply add the rotation value to our current position without branching logic.

To solve this, we’ll fold over the list of rotations while maintaining a tuple of (count, currentRotation):

• count: the number of times we’ve landed exactly on 0
• currentRotation: our current position on the dial

After each rotation, we check if our new position modulo 100 equals 0—meaning we’ve landed precisely on position 0.

All that’s left is to compose parsing with solving:

Part 2 increases the difficulty: now we need to track how many times the indicator passes through position 0, including positions crossed during a rotation (not just where it lands).

For example, if we’re at position 80 and rotate right by 30, we pass through position 0 once during that rotation (80 → 90 → 100/0 → 10).

The base algorithm remains a fold over the rotation list, but now we need a more sophisticated way to count zero crossings:

The numberOfClicks function calculates how many times we pass through zero during a single rotation.

The logic breaks down as follows:

1. Normalize the current position to be in range [0, 99]
2. Calculate complete rotations: Dividing the rotation amount by 100 gives us how many full loops around the dial we make (totalRotations)
3. Check the remainder: After the complete rotations, does the remainder push us through 0?
   • Right rotation: We pass through 0 if currentPos + remainder >= 100
   • Left rotation: We pass through 0 if we’re not already at 0 and currentPos - remainder <= 0

One important edge case: Haskell’s mod operator doesn’t wrap negative numbers the way we need for a circular dial. Our custom normalization function ensures that -10 becomes 90, -110 becomes 90, and so on—wrapping properly in the reverse direction.

With all the pieces in place, Part 2 comes together:

Today’s puzzle gives us a list of numeric ranges:

(90 - 10000)
(57 - 82345)

Our task: find all “invalid IDs” within each range and sum them together.

An ID is invalid if its digits can be split into two equal halves. For example:

• 1010 splits into 10 and 10 ✓ invalid
• 123123 splits into 123 and 123 ✓ invalid
• 88 splits into 8 and 8 ✓ invalid
• 123 has odd length ✗ valid
• 1234 splits into 12 and 34 ✗ valid

The input is comma-separated ranges, which we’ll model as pairs of integers.

The algorithm is straightforward: for each range, check every number to see if it’s invalid, sum those that are, then sum across all ranges.

The isInvalid function checks if a number has even digit length and whether its first half equals its second half.

Part 2 generalizes the pattern: now an ID is invalid if it consists of any repeating segment, not just two halves. For example:

• 111 → 1 repeated 3 times ✓ invalid
• 123123123 → 123 repeated 3 times ✓ invalid
• 88 → 8 repeated 2 times ✓ invalid
• 1234 → no repeating pattern ✗ valid

We need to find all possible chunk sizes that could divide the number evenly, then check if chunking by that size produces identical chunks.

For a number with length 6, we check chunk sizes 1, 2, and 3 (divisors of 6). If any chunking produces all-equal chunks, the number is invalid.

The implementation changes only the isInvalid function—everything else stays the same.

Today’s input gives us rows of digits—think of each row as a “bank of batteries”:

987654321111111
811111111111119
234234234234278
818181911112111

Each digit represents a battery, and our job is to calculate the maximum “joltage” for each bank, then sum them all together.

For Part 1, the joltage of a bank is determined by picking any two digits (in order, no reversing) and forming a two-digit number. For example, from 987654321111111, we could pick the 9 and 8 to get 98, or the 9 and 7 to get 97. The maximum joltage is the largest such number we can form.

Our data model is simple: a list of banks, where each bank is a list of digit values.

Parsing is straightforward—we split into lines and convert each character to a single digit.

The algorithm: generate all possible pairs of digits (maintaining order), form two-digit numbers from each pair, and take the maximum. Sum across all banks for the final answer.

Part 2 escalates things: now we need to pick 12 digits to form a 12-digit number, and maximize that.

Here’s the key insight: we can solve this greedily by picking digits from most significant to least significant.

Let’s think through a simpler example: picking 4 digits from a 6-digit bank. The first digit we pick can’t be in the last 3 positions—we need to leave room for the 3 digits that follow. Among the valid positions (first 3 positions), we pick the largest digit.

If there’s a tie, we pick the earliest occurrence. Why? Because choosing earlier gives us more options for subsequent digits—we preserve flexibility down the line.

Once we’ve picked the first digit, we repeat the process for the second digit (starting from just after our first pick), then the third, and so on.

The structure mirrors Part 1, except we use getMaxJoltageOf to generalize to any number of digits (12 in this case).

The getMaxJoltageOf function implements our greedy strategy. For each digit position, we calculate which indices in the original bank are valid candidates (ensuring we leave enough room for remaining digits), then pick the largest digit from those positions.

The recursion tracks three things: how many digits we’ve picked so far, the minimum index we can pick from (to maintain order), and our accumulated result.

Finally, we need to merge our list of digits into an actual number. We reverse the list (since we built it backwards), then combine digits by multiplying each by the appropriate power of 10 based on its position.

Today’s puzzle presents us with a 2D grid containing rolls of paper (marked with @) scattered among empty spaces.

Our task: count how many rolls are accessible. A roll is accessible if it has fewer than 4 neighboring rolls in the 8 adjacent positions (including diagonals). In other words, rolls that are too crowded (4+ neighbors) are inaccessible.

We’ll use V2 Int from the linear package to represent positions, and a HashSet to store the grid.

Since we only care about where the rolls are (not empty spaces), we store just the positions containing rolls. This gives us efficient O(1) average-case lookups to check “is there a roll at this position?”

The solution filters the grid to keep only rolls with fewer than 4 neighbors, then counts them.

The getAdjacentRolls helper generates all 8 adjacent positions (using vector addition) and counts how many contain rolls.

Part 2 introduces a removal process: we repeatedly remove all accessible rolls (those with fewer than 4 neighbors) until no more can be removed. The answer is the total count of removed rolls.

This is a classic fixed-point iteration. Each round, we:

1. Identify accessible rolls (using our Part 1 logic)
2. Remove them from the grid
3. Repeat until the grid stops changing

The trick: when we remove rolls, previously inaccessible rolls might become accessible (they now have fewer neighbors). So we keep iterating until we reach a stable state.

The final answer is the difference between the original grid size and the final grid size.

Today’s puzzle gives us a database containing two pieces of information:

1. A list of valid ranges (e.g., 100-500, 600-1000)
2. A list of ID numbers to check

Our task for Part 1: count how many of the given IDs fall within at least one of the valid ranges. An ID is “fresh” if it’s covered by any range.

We’ll represent ranges as pairs of integers and bundle everything into a Database type for clean organization.

The input format has ranges first (one per line), then a blank line, then a list of IDs. We split on the blank line and parse each section accordingly.

Part 1 is straightforward: for each ID, check if any range contains it. Count the IDs that pass this test.

The contains helper checks if a value falls within a range’s bounds (inclusive).

Part 2 asks a different question: what’s the total count of unique integers covered by all the ranges combined?

For example, if we have ranges 1-5 and 3-8, the unique integers covered are [1,2,3,4,5,6,7,8], giving us a count of 8 (not 11, which would be if we counted overlaps twice).

The key insight: if we sort the ranges by their start position, we know that each subsequent range never starts before any previous range. This makes merging overlaps much simpler.

As we fold through the sorted ranges, we track: - The previous range’s maximum value - The running count of unique integers covered

For each new range, we calculate how many new integers it contributes by ensuring we don’t double-count overlaps with the previous range.

Today’s puzzle gives us a grid of numbers followed by a line of operations.

The twist? We need to read the grid vertically (column by column) rather than horizontally. Each column of numbers gets paired with an operation from the last line, and we apply that operation to get a result. The final answer is the sum of all column results.

For example, if a column is [2, 3, 5] and the operation is +, we get 10. If the operation is *, we get 30.

The algorithm is straightforward:

1. Split the input into rows and the final operations line
2. Parse each row as space-separated numbers
3. Transpose to get columns instead of rows
4. Zip operations with columns and apply each operation
5. Sum the results

We support two operations: sum (+) and product (*).

Part 2 changes the parsing rules. Now the grid can contain empty spaces within columns, and we need to treat sequences of numbers separated by spaces as distinct groups within each column.

For example, a column might look like:

1
2

3
4

This represents two groups: [1, 2] and [3, 4]. We split on empty spaces, apply operations to each group separately, then sum everything.

The key difference is in how we process the transposed data:

1. Strip whitespace from each cell
2. Split on empty strings to get groups
3. Parse each group as numbers
4. Apply operations as before

We need helpers to strip whitespace and split on a predicate.

Today’s puzzle involves a beam of light traveling through a grid containing tachyons (represented by ^ symbols). The beam starts at position S and travels upward through columns.

When the beam hits a tachyon, something interesting happens: it splits into two beams that move horizontally (one left, one right), then continue upward from their new positions.

Our task: count how many unique tachyons the beam(s) will hit.

We need to track:

• Where the beam starts (S position)
• Where all the tachyons are (organized by column for efficient lookup)

We scan the grid for special characters: S marks the start position, and ^ marks tachyons. We organize tachyons by column and sort their y-coordinates for efficient upward traversal.

A simple grouping function that clusters consecutive elements with the same key.

The beam simulation is a recursive traversal:

1. From the current position (x, y), look up the column and find the next tachyon above the current y-coordinate
2. If we find one and haven’t visited it yet:
   • Mark it as visited
   • Remove it from the available tachyons
   • Split: recursively simulate beams going left (x-1, newY) and right (x+1, newY)
3. If no tachyon found or already visited, return the current visited set

The union of all visited tachyons gives us the answer.

Part 2 asks: how many distinct paths does the beam take to reach the end?

Instead of just counting visited tachyons, we now count all the different ways the beam can split and travel through the grid. This is a classic path-counting problem that benefits from memoization—if we reach the same tachyon from the same direction multiple times, the number of paths from there is always the same.

The algorithm is similar to Part 1, but now:

• We track a cache of (position -> path_count) instead of a set
• When we reach a position we’ve seen before, return the cached count
• When we reach the end (no more tachyons), that’s 1 complete path
• The total count is the sum of paths going left and right at each split

Today’s puzzle gives us electrical junctions floating in 3D space, each described by x,y,z coordinates:

162,817,812
57,618,57
906,360,560
...

Our task: repeatedly pick the two closest junctions and connect them into a circuit. This happens 1000 times, and each connection can play out in three ways:

• Both unconnected: Create a new circuit containing both junctions
• One connected: Add the unconnected junction to the existing circuit
• Both connected: Merge their two circuits into one

After 1000 connections, we multiply the sizes of the three largest circuits together.

If this sounds like a job for a Union-Find (Disjoint Set) data structure, you’re absolutely right. That’s the textbook efficient solution for this kind of problem.

Here’s the thing: this puzzle is actually why I learned about disjoint sets in the first place—but only after I’d already solved it my own way. So today we’ll walk through my original, more naive approach using the State monad and some good old hashmaps.

Let’s start with our data model. We’ll use integers to identify circuits and 3D vectors from the linear library to represent junction positions.

Parsing is straightforward—each line contains comma-separated x,y,z coordinates.

For distance calculations, we use squared Euclidean distance. Since we only care about relative distances for sorting, we can skip the sqrt—it’s monotonic, so the ordering stays the same and we save some computation.

The distances function generates all possible junction pairs and sorts them by distance, giving us a priority queue of connections to process.

Now for the core state management. Our ProblemState tracks three things:

• nextCircuitId: Counter for assigning IDs to new circuits
• junctions: Maps each junction to its circuit ID (for fast “which circuit am I in?” lookups)
• circuits: Maps each circuit ID to its junctions (for fast “what’s in this circuit?” lookups)

This bidirectional indexing lets us efficiently handle all three connection cases.

We’re using the State monad combined with the lens library to keep our solution clean and readable. Lenses let us update nested state elegantly without the usual record update boilerplate. If you’re new to lenses, I highly recommend Optics By Example.

We alias our computation type as Solver for clarity.

Adding a junction to a circuit requires updating both indexes: we record which circuit the junction belongs to, and add the junction to that circuit’s member list.

Now for the heart of the solution: processing a junction pair. Given junctions (a, b), we need to handle five distinct cases:

1. Only a is connected: Add b to a’s circuit
2. Only b is connected: Add a to b’s circuit
3. Both in same circuit: Nothing to do
4. Both in different circuits: Merge them by moving all junctions from one circuit to the other, then delete the empty circuit
5. Neither connected: Create a new circuit containing both and increment our ID counter

This is where things get interesting—and where a proper Union-Find structure would shine. But our State monad approach keeps the logic explicit and easy to follow.

With our machinery in place, Part 1 is straightforward:

1. Take the 1000 closest junction pairs
2. Process each pair with our state-modifying function
3. Find the three largest circuits and multiply their sizes

That final one-liner does some heavy lifting: it extracts all circuits, maps to their sizes, sorts in descending order, takes the top 3, and multiplies them together.

Part 2 asks a different question: when do all junctions get connected into a single unified circuit? We need to find the specific pair that completes this unification, then multiply their x-coordinates together.

The beautiful part? We’ve already built everything we need. Our state tracks both the number of junctions assigned to circuits and the number of distinct circuits. When those numbers are equal to the total junction count and 1 respectively, we’re done.

The addUntilDone helper processes pairs one by one until it hits that condition, then returns the winning pair. Multiply the x-coordinates, and we have our answer.

Today’s puzzle gives us a collection of points scattered across a 2D grid. Our task: find the largest rectangle we can form by choosing any two points as opposite corners.

The twist? The rectangle’s sides must be axis-aligned (parallel to the x and y axes), and we count tiles inclusively—so a rectangle from (0,0) to (2,2) contains 9 tiles, not 4.

Oooof, these imports are getting out of hand! But hey, we’ve got SVG rendering to do later.

The linear library’s V2 Int type is perfect for 2D points—it gives us vector operations for free if we need them later.

Parsing is straightforward: each line contains comma-separated x,y coordinates.

With a modest number of points, brute force is our friend. We check every possible pair of points, calculate the resulting rectangle’s area, and take the maximum.

The area function adds 1 to each dimension because we’re counting tiles inclusively—a rectangle from (0,0) to (2,2) spans 3 units in each direction, giving us 3×3=9 tiles.

Part 2 cranks up the difficulty: now we need to find the largest rectangle that fits inside a polygon formed by connecting all the input points in sequence.

My first instinct was to implement the classic raycast algorithm for point-in-polygon testing. But that’s a lot of code for something I’ve written before, and—let’s be honest—it’s not that interesting the second time around.

Instead, I got curious. What does the actual input look like? I whipped up a quick SVG visualization:

Jackpot! The polygon is roughly circular with a narrow cut extending inward from the edge.

This observation unlocks a much simpler approach: any rectangle large enough to be worth considering will be entirely on one side of that cut. It either fits in the “upper” region or the “lower” region—it can’t bridge across the cut without intersecting an edge.

So instead of checking if every point inside a candidate rectangle is within the polygon, we just need to verify that the rectangle’s boundary doesn’t intersect any polygon edges.

Armed with our insight, the solution mirrors Part 1’s brute force—except now we filter out any rectangle whose interior intersects with a polygon edge.

The intersects function checks if any polygon edge crosses through our candidate rectangle. We do this by testing whether the edge’s bounding box overlaps with the rectangle’s interior. If any edge overlaps, the rectangle is invalid.

Today’s puzzle presents us with a collection of lights, each composed of multiple LEDs. Our task: figure out the minimum number of button presses needed to configure each light to match a target pattern.

Each light comes with three pieces of information:

• Target configuration: a string like [.##.] where # represents an LED that should be ON and . represents one that should be OFF
• Buttons: each button, when pressed, toggles specific LEDs (e.g., (1,3) toggles LEDs at indices 1 and 3)
• Joltages: power requirements we can safely ignore for Part 1

For example, in [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}: - We want LEDs at positions 1 and 2 to be ON, the rest OFF - We have six buttons available, each toggling different LED combinations - The joltages {3,5,4,7} don’t matter yet

This is essentially a search problem: starting from all LEDs off, find the shortest sequence of button presses to reach the target configuration

We’ll represent each light with a simple record type. The key insight is that we only care about which LEDs are on, not their order, so IntSet is perfect for tracking configurations efficiently.

Parsing this format is a bit fiddly—we need to strip brackets, parentheses, and curly braces, then split on commas and whitespace. Not the most elegant code I’ve written, but it gets the job done without pulling in heavy parsing libraries.

Reminder to Self: find better combinators for parsing. (Although I’d like to keep my solutions parsec and regex free)

When we want the minimum number of steps to reach a goal, breadth-first search (BFS) is our go-to algorithm. It explores all configurations reachable in N steps before trying any configuration that takes N+1 steps—guaranteeing we find the shortest path.

Here’s the game plan: 1. Start with all LEDs off (empty IntSet) 2. For each configuration we’re exploring, try pressing every button 3. Track which configurations we’ve seen before to avoid cycles 4. Stop when we reach the target configuration

The breadth function does the heavy lifting: - states: configurations we’re currently exploring - cache: a map recording how many steps it took to reach each configuration - steps: current depth in our search

Each iteration generates new configurations by clicking every possible button on every current state, filters out ones we’ve seen before, and continues until we hit the target

The helper functions are straightforward: clickButton applies a button press to a configuration by toggling each LED the button affects, and toggleLight flips a single LED on or off.

With BFS handling the search for each individual light, the final solution just sums up the minimum button presses across all lights in our input.

Part 2 adds a delightful twist: now we need to consider the joltages—those power requirements we ignored in Part 1. Each button press consumes power from specific joltage sources, and we need to find the minimum number of button presses that both:

1. Achieves the target LED configuration
2. Uses exactly the specified amount of power from each joltage source

For example, if joltage 0 must total exactly 7, and buttons (0,2) and (1,3) both draw from joltage 0, then we need to press those buttons a combined total of 7 times. The challenge is finding a combination of button presses that satisfies all joltage constraints simultaneously while minimizing total presses.

This transforms our simple BFS problem into something much more sophisticated: a constrained optimization problem.

Unfortunately I couldn’t solve part 2 initially… So instead here’s a picture of my dog:

This is Hugo from the future! I’ve finally been able to link Z3 with Haskell on my MacBook. I’m relatively new to Z3 and SMT (Satisfiability Modulo Theories) solvers in general, so this was a great learning opportunity.

What’s an SMT solver? Think of it as a constraint satisfaction engine on steroids. You describe your problem as a set of mathematical constraints (equations, inequalities, logical formulas), specify what you want to minimize or maximize, and the solver finds a solution that satisfies everything—if one exists.

Z3, developed by Microsoft Research, is one of the most powerful SMT solvers available. It’s used for everything from program verification to test case generation. And for our puzzle? It’s perfect!

The key insight is recognizing this as a system of linear equations with an optimization goal. Let’s break it down:

Variables: For each button i, let button_i represent the number of times we press it.

Objective function (what we want to minimize):

total_presses = button_0 + button_1 + ... + button_n

Constraints (conditions that must be satisfied):

1. Non-negativity: We can’t press a button a negative number of times

   button_i ≥ 0  (for all i)

2. Joltage requirements: For each joltage source, the sum of button presses that draw from that source must equal the required total

   Σ(button_i where button i affects joltage j) = joltage_j

For example, if buttons 2, 5, and 7 all draw from joltage source 3, and joltage 3 requires 15 total power, then:

button_2 + button_5 + button_7 = 15

This is a classic Integer Linear Programming (ILP) problem—and Z3 excels at solving these!

First, we need to extract our linear equations from the puzzle input. For each joltage source, we identify which buttons affect it.

Remember: button index i in the buttons list affects joltage j if j appears in that button’s list. So for joltage source 2, we scan through all buttons looking for those that mention index 2.

The result is a list of tuples: (required_joltage, [button_indices]) where each tuple represents one constraint equation.

Now comes the fun part: encoding our problem in Z3. The Haskell bindings are… let’s say “functional but verbose.” Everything is done monadically through the Z3 monad, which handles the interaction with the underlying solver.

Step 1: Create decision variables

We create one integer variable per button. These represent our unknowns—the number of times each button will be pressed in the optimal solution.

Step 2: Add non-negativity constraints

Each variable must be ≥ 0 since we can’t press a button a negative number of times. We use Z.optimizeAssert to add each constraint to our optimization problem.

Step 3: Add joltage equality constraints

For each joltage equation we extracted earlier, we tell Z3: “the sum of these specific button presses must equal this joltage value.” This is the heart of our constraint system.

Step 4: Define the optimization goal and solve

We create an expression representing the total button presses (sum of all variables), tell Z3 to minimize it, then run the solver. If a solution exists, we extract the value assigned to each variable and sum them up.

The verbosity is unfortunate (those nested mkEq and mkIntNum calls!), but the elegance of the approach shines through: we’ve transformed a complex search problem into a declarative specification that Z3 can solve optimally.

The final step is straightforward: run our Z3 script for each light and sum the results. We use Z.evalZ3 to execute the Z3 monad and get back our answer.

Note on unsafePerformIO: Normally mixing IO into pure functions is dangerous, but here it’s safe because Z3 solving is referentially transparent—given the same input, it always produces the same output with no side effects we care about. We use unsafePerformIO purely to maintain a consistent API with Part 1.

The beauty of this approach is its generality. Once you’ve modeled your problem as constraints and an objective function, Z3 handles all the complexity of finding an optimal solution. No manual search algorithms, no clever heuristics—just declarative problem specification and powerful automated reasoning. This is why SMT solvers are such a fundamental tool in modern software engineering and formal methods!

Day 11 presents us with a network topology puzzle! We’re given a list of network devices and their connections, forming a directed acyclic graph (DAG). Each line describes which devices a particular node connects to.

Here’s a simplified example of the input format:

a: you
you: c d
c: out
d: out

This describes a network where device a connects to you, device you has two outgoing connections to c and d, and both c and d connect to the final destination out.

Our task for Part 1: count all possible paths from the starting node "you" to the destination node "out". In the example above, there are 2 paths: - you → c → out - you → d → out

We’re using Text for efficient string handling (device IDs can be arbitrary strings), and HashMap for fast O(log n) lookups when traversing the graph—much better than linear searches through lists!

The model is straightforward: we represent the entire network as a mapping from each device ID to its list of outgoing connections.

Parsing is mercifully simple: each line has a device ID followed by a colon, then a space-separated list of devices it connects to. We strip the trailing colon with Text.init and collect the rest as a list of outgoing connections.

Here’s where things get interesting. The naive approach—recursively exploring every path from start to end—would repeatedly recompute the same subproblems. If device c is reachable from multiple places in the network, we’d count all paths from c to out multiple times!

Dynamic programming to the rescue! We’ll use memoization to cache the number of paths from each device to our destination. The first time we visit a device, we compute its path count and store it. Every subsequent visit just looks up the cached value.

Think of it as working backwards from the destination: - The destination itself has exactly 1 path (the empty path) - Any device that connects directly to the destination has as many paths as it has outgoing edges to the destination - Any other device has paths equal to the sum of paths from all its children

This is essentially a depth-first search with memoization, a classic DP technique for DAGs.

The countConnections function implements our memoized DFS. Let’s break down what’s happening:

Initial cache setup: We start with a clever optimization—any device that connects directly to end already has at least one path. We pre-populate the cache by counting direct connections to the end node for every device.

The buildMap recursion handles three cases:

1. Base case: If we’ve reached the end device, return a cache with just {end: 1}
2. Cache hit: If we’ve already computed this device’s path count, return the existing cache unchanged
3. Cache miss: This is where the magic happens:
   • Get all children (devices this one connects to)
   • Recursively build the cache for each child using foldl'
   • Sum up the path counts from all children (that’s the total paths through this device!)
   • Insert this device’s count into the cache

The fold accumulates the cache as we explore, ensuring each device is only computed once. When we’re done, we look up our starting device in the final cache to get the total path count.

Part 2 cranks up the complexity: now we need to count only paths from "svr" to "out" that pass through both "fft" and "dac" devices. Not just one or the other—both!

At first glance, this seems like we need a completely different algorithm. But there’s an elegant mathematical trick we can use: the inclusion-exclusion principle.

Think about it in terms of set operations. We want paths that include both checkpoints, which is equivalent to:

allPaths - pathsWithoutDac - pathsWithoutFft + pathsWithoutEither

Why does this work? - Start with all paths from svr to out - Subtract paths that don’t go through dac (removes all paths missing that checkpoint) - Subtract paths that don’t go through fft (removes all paths missing that checkpoint) - Add back paths that avoid both (we subtracted these twice, so we need to add them once)

This is the classic inclusion-exclusion formula: |A ∩ B| = |U| - |Ā| - |B̄| + |Ā ∩ B̄|

And the beautiful part? We can compute “paths that avoid X” by simply removing X from the graph and counting paths normally!

There’s another way to think about this problem that’s perhaps more intuitive. Any path that goes through both dac and fft must visit them in some order:

• Either: svr → ... → dac → ... → fft → ... → out
• Or: svr → ... → fft → ... → dac → ... → out

These are mutually exclusive cases (you can’t visit dac before fft and fft before dac in the same path), so we can count them separately and add the results.

For the first case, we need:

(paths from svr to dac) × (paths from dac to fft) × (paths from fft to out)

Why multiplication? Because each path in the first segment can be paired with each path in the second segment, and each of those combinations can be paired with each path in the third segment. That’s the fundamental counting principle!

Similarly for the second case. Add them together:

This alternative formulation is arguably clearer—it directly expresses the structure of the paths we’re counting. Both solutions produce the same answer, but I find the inclusion-exclusion approach (solvePart2) more elegant and generalizable. If we needed to check for three or four required checkpoints, the combinatorial explosion of cases in the subpath approach would get messy fast, while inclusion-exclusion scales gracefully.

Day 12 brings us a festive packing puzzle! We’re playing Santa’s logistics coordinator, trying to figure out which Christmas trees have enough space underneath to hold all their designated presents.

The input gives us two things: a catalog of present shapes and a list of trees with their packing requirements.

Each present is defined by its shape on a 2D grid:

0:
 ###
 ##.
 ##.

The first line shows the present’s index (0 in this case). The following rows describe the shape, where # represents solid present and . represents empty space. This present occupies 5 cells.

Trees are specified with their dimensions and the presents they need to hold:

4x4: 0 0 0 0 2 0

This tree has a 4×4 grid of space underneath (16 cells total), and needs to accommodate: four copies of present 0, one copy of present 2, and one copy of present 0 again.

Our task: Determine which trees have sufficient area to fit all their assigned presents.

The model is straightforward: we represent each present as a 2D grid of booleans, where True indicates a solid cell. Trees track their dimensions and the list of present indices they need to hold.

Parsing follows the input structure: we split on double newlines to separate the present catalog from the tree list. Each present’s shape is converted to a grid of booleans by testing for '#' characters. Tree parsing extracts dimensions from the WxH: prefix and reads the space-separated present indices.

At first glance, this might look like the classic knapsack problem—we need to fit items into a container. But it’s actually harder! This is a 2D bin packing problem, where we need to arrange irregularly-shaped presents within a rectangular space.

The general version of this problem is NP-complete. A proper solution would need to:

1. Try different rotations of each present (if rotation is allowed)
2. Consider all possible positions for placing each present
3. Ensure presents don’t overlap with each other
4. Backtrack when a configuration doesn’t work

This could involve sophisticated algorithms like genetic algorithms, simulated annealing, or branch-and-bound search. For large inputs, even approximate solutions are challenging!

Here’s where things get interesting. After examining the actual puzzle input, I noticed something: for every tree in the input, a simple area check is sufficient. That is, if the sum of all present areas is less than or equal to the tree’s total area, then those presents will actually fit when properly arranged.

This suggests the puzzle author deliberately crafted the input to avoid the NP-complete complexity. Perhaps the presents are designed to pack efficiently, or the tree spaces are generous enough that optimal packing isn’t required. Either way, we can solve Part 1 with a straightforward area comparison!

The solution filters trees by checking if their total area can accommodate all assigned presents. We pre-compute each present’s area (counting True cells in its grid), then for each tree, sum up the areas of its required presents and compare against the tree’s dimensions.

This elegant simplification turns an intractable problem into an O(n) solution. Sometimes the best algorithm is recognizing when you don’t need one!

There is no Part 2, part 2 is the stars we collected along the way (:

I hope this has been useful to you, if it was please consider leaving a star in the repo.

Merry Christmas,
Hugo Vilela