Day 3 has come and gone. It was perhaps less fun than Day 2, but knowing the techniques is essential. I’ll use this post to briefly discuss my workflow for solving AoC puzzles before diving into the Day 3 solution.
Tooling
As I’m doing this year’s AoC in Rust, I took the easy route and used the advent-of-code-rust template. This allows me to quickly initialize a problem:
cargo scaffold 03Download the inputs:
cargo download 03Your project structure will now contain the input and description for the requested day. Unfortunately, it doesn’t
automatically populate the example file. You’ll need to manually copy the example lines from the problem description
into the example file generated by scaffold.
Next, open your day.rs file (today’s is 03.rs). You’ll find two functions—one for each part—along with their
respective tests using the example data.
The first thing I usually do is update the test with the expected example value.
pub fn part_one(input: &str) -> Option<u64> {
None
}
pub fn part_two(input: &str) -> Option<u64> {
None
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_part_one() {
let result = part_one(&advent_of_code::template::read_file("examples", DAY));
assert_eq!(result, Some(357));
}
#[test]
fn test_part_two() {
let result = part_two(&advent_of_code::template::read_file("examples", DAY));
assert_eq!(result, None);
}
}This clearly marks part_one as failing, setting the stage for implementation.
You could run tests with cargo test 03, but for better interactivity and speed, I prefer using cargo-watch:
cargo watch -x 'test --bin 03`This compiles and runs the tests every time I save the file.
The next step is to write a function to parse your puzzle, and add tests for each example in your example file:
#[test]
fn test_jolt() {
assert_eq!(unit_fn("sub_example"), 99);
/// ...
}A Test-Driven Development (TDD) approach is invaluable when writing complex code.
Now, before we look at the Day 03 puzzle, please make sure you take a look at the problem statement before reading further. Here’s a generated image to prevent you from accidentally seeing the solution below.
Part 1
In this part, you are asked to select two digits from a 15-digit string to form the largest possible number. The digits
must be selected in their original order. For example, in 818181911112111, the result is 92. Reordering is not
allowed.
First things first: we write our tests:
#[test]
fn test_jolt() {
assert_eq!(jolt("987654321111111"), 98);
assert_eq!(jolt("811111111111119"), 89);
assert_eq!(jolt("234234234234278"), 78);
assert_eq!(jolt("818181911112111"), 92);
}The core idea is to treat the first digit as the current maximum “tens” digit. We then iterate through the remaining digits, attempting to build a number with the current digit as the “units” part. If we encounter a digit larger than our current “tens” digit, we switch to using it as the new “tens” digit. Which we can implement using a linear solution like this:
fn jolt(input: &str) -> u64 {
let bytes = input.as_bytes();
let mut max_tens = (bytes[0] - b'0') as u64;
let mut max_val = 0;
for &b in bytes.iter().skip(1) {
let current_digit = (b - b'0') as u64;
let pair = max_tens * 10 + current_digit;
if pair > max_val {
max_val = pair;
}
if current_digit > max_tens {
max_tens = current_digit;
}
}
max_val
}This results in a fast, linear solution:
Part 1: 1xxx4 (18.1µs @ 10000 samples)Part 2
Part 2 asks us to find 12 digits that form the largest number from the 15 given. Once again, we start with a test:
#[test]
fn test_jolt_select() {
assert_eq!(jolt_select("987654321111111", 12), 987654321111);
assert_eq!(jolt_select("811111111111119", 12), 811111111119);
assert_eq!(jolt_select("234234234234278", 12), 434234234278);
assert_eq!(jolt_select("818181911112111", 12), 888911112111);
}We can apply the same greedy strategy as in Part 1. At each step, we search for the largest possible digit within a specific range, ensuring enough digits remain to fulfill the length requirement.
For instance, with 15 input digits and a requirement of 12, we can drop or skip up to 3 digits.
Therefore, the first iteration searches for the largest digit within the first 4 positions (1 + 3). Once found, we move the cursor to the digit immediately following our maximum. The range for the next search depends on how many digits were skipped in the previous step.
fn jolt_select(input: &str, select: usize) -> u64 {
let bytes = input.as_bytes();
let n = bytes.len();
let mut result: u64 = 0;
let mut search_start = 0;
for count in (1..=select).rev() {
let mut max_val = 0;
let mut max_idx = search_start;
// where we can stop, depends on how many we can skip at this iteration
// e.g. 15 - 12 = 3, means we w'll stop at index 3 inclusive
let search_end = n - count;
for i in search_start..=search_end {
let digit = bytes[i];
if digit > max_val {
max_val = digit;
max_idx = i;
// early break as we can never get bigger than 9
// this will help us skip less digits
if digit == b'9' {
break;
}
}
}
result = result * 10 + (max_val - b'0') as u64;
search_start = max_idx + 1;
}
result
}Here is an LLM-generated visualization of the algorithm applied to 234234234234278:
-
Step 1, 1st digit:
Indices: [0] [1] [2] [3] 4 5 6 ... Values: | 2 | 3 | 4 | 2 | 3 | 4 | 2 ... └─┬─┴─┬─┴─┬─┴─┬─┘ │ │ │ │ Search: 2 3 4 2 (Max is 4 at Index 2) ^ ACTION: Pick 4. Skip indices 0 and 1 (Cost: 2 skips) Remaining Budget: 3 - 2 = 1 skip -
Step 2: 2nd digit:
Indices: 0 1 2 [3] [4] 5 6 ... Values: x x 4 | 2 | 3 | 4 | 2 ... └─┬─┴─┬─┘ │ │ Search: 2 3 (Max is 3 at Index 4) ^ ACTION: Pick 3. Skip index 3 (Cost: 1 skip) Remaining Budget: 1 - 1 = 0 skips left -
Step 3: no budget left
Remaining: 4 2 3 4 2 3 4 2 7 8 Action: Take all.
Using this greedy approach, we get:
Part 2: 1xxxxxxxxxxxxx0 (40.5µs @ 10000 samples)Improve the algorithm
We can optimize this using a specific algorithm: monotonic stacks. As far as I know, this approach is commonly associated with “Next Greater Element” problems.
The concept is simple: Iterate through the digits. If the current digit is larger than the last one picked and we have enough “budget” (skips remaining), discard the previous digit and take the larger one. A stack is the ideal data structure for this, hence the name.
fn jolt_select_stack(input: &str, select: usize) -> u64 {
let bytes = input.as_bytes();
let mut stack = Vec::with_capacity(select);
let mut budget = bytes.len() - select;
for &b in bytes {
// As long as we have budget, that we can remove items, and that the current digit is
// larger than the top of the stack, we can replace the top by the new max
while budget > 0 && !stack.is_empty() && b > *stack.last().unwrap() {
stack.pop();
budget -= 1;
}
stack.push(b);
}
stack
.iter()
// in situations where digits are in in order, our comparison above wont pop, and we'll end
// up with all digits in the stack
// for ex 987654321111111 will keep all the 1s at the end with budget = 3
// hence we need to take the bottom of our stack
.take(select)
.fold(0, |acc, &b| acc * 10 + (b - b'0') as u64)
}Here is an explanation (again, generated by an LLM to save time):
1. Read '2' 2. Read '3' (3 > 2) 3. Read '4' (4 > 3)
(Stack Empty) (Drop Available!) (Drop Available!)
Incoming: 2 Incoming: 3 Incoming: 4
↓ ↓ ↓
| | | | 💥 Pop 2 | | 💥 Pop 3
| 2 | | 3 | 📉 Drops: 2 | 4 | 📉 Drops: 1
└———┘ └———┘ └———┘
PUSH SWAP SWAPThe next value is 2, which is smaller than 4:
4. Read '2' (2 < 4) 5. Read '3' (3 > 2)
(No Drop triggered) (Last Drop Available!)
Incoming: 2 Incoming: 3
↓ ↓
| 2 | | 3 | 💥 Pop 2
| 4 | | 4 | 📉 Drops: 0 (EMPTY)
└———┘ └———┘
PUSH SWAPThe next value is 4, while our stack top is 3. Unfortunately, we are out of budget:
6. Read '4' (4 > 3)
(BUT Drops = 0 🛑)
Incoming: 4
↓
| 4 | <-- Cannot Pop '3'
| 3 | because budget is 0.
| 4 |
└———┘
FORCED PUSHThis means we simply push the remaining digits:
Remaining Input: 2 3 4 2 3 4 2 7 8
Action: Push All -> -> ->
Final Stack:
| 8 | (Top)
| 7 |
| 2 |
| 4 |
| 3 |
| 2 |
| 4 |
| 3 |
| 2 |
| 4 |
| 3 |
| 4 | (Bottom)
└———┘Sadly, we do not get a better performance, as the input size is not large enough:
Part 2: 1xxxxxxxxxxxxx0 (44.2µs @ 7263 samples)