Advent of Code is an annual set of daily programming challenges every December.
Read the challenge for 2025, Day 2
The Problem
We have to find all of the invalid IDs within an inclusive range of IDs for multiple ranges of IDs. In part one, an invalid ID is one that is composed of a sequence of digits repeated twice. In part two, an invalid ID is one that is composed only of repeated sequences of digits.
My Solution
I was up late last night. I didn’t mean to be, I was just playing around with a side project and time got away from me. So I did part one pretty close to midnight.
The input data looks like this.
"11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124" This is a series of ranges of IDs. Each range is comma separated and gives the lowest and highest values IDs in the range. I created a Range struct to hold each range and wrote code to parse the string into a vector of the Range type.
#[derive(Debug)]
struct Range {
from: u64,
to: u64,
}
fn parse_input(input: &str) -> Result<Vec<Range>, anyhow::Error> {
input.split(',').map(parse_line).collect()
}
fn parse_line(line: &str) -> Result<Range, anyhow::Error> {
let (from, to) = line
.split_once('-')
.ok_or(anyhow!("Missing dash in range"))?;
Ok(Range {
from: from.parse()?,
to: to.parse()?,
})
}For part one, it helped me to rephrase the statement of what made an ID invalid.
The puzzle explains it like this.
…you can find the invalid IDs by looking for any ID which is made only of some sequence of digits repeated twice.
Instead, I framed it as “Invalid IDs can be cut into identical halves”.
I wrote the is_invalid_part_1 (née is_invalid) function to check if a given ID was invalid given that framing.
fn has_even_n_digits(num: u64) -> bool {
num.to_string().len().is_multiple_of(2)
}
// In part one, an ID is invalid if it is composed of two repeated digit sequences.
fn is_invalid_part_1(id: u64) -> bool {
// the invalid IDs can only include numbers with an even number of digits.
if !has_even_n_digits(id) {
return false;
}
let s = id.to_string();
let (left, right) = s.split_at(s.len() / 2);
left == right
}Here, we have encoded the statement above into a function. If an invalid ID can be cut in halves, this means all invalid IDs must have an even number of digits. I converted all of the IDs with an even number of digits into strings which I split in half and compared the two halves of the string. If they were equivalent, the ID was invalid.
Don’t tell me it’s not efficient because I cast the ID to a string twice. I know. We’re having fun with computers here. It’s ok.
I then wrote a function to perform this validity check on every ID in each range in the set.
fn part_1(ranges: &[Range]) -> i32 {
ranges
.iter()
.flat_map(|range| range.from..=range.to)
.filter(|&id| is_invalid_part_1(id))
.sum()
}This solved the example case the problem gives, but when I ran it on the full puzzle input, I got a negative number.
TIP:
If you are ever incrementing a counter and the counter outputs a negative number, the first thing you should check is if you got an integer overflow.
I just needed to change my accumulator to a u64.
-fn part_1(ranges: &[Range]) -> i32 {
+fn part_1(ranges: &[Range]) -> u64 {
ranges
.iter()
.flat_map(|range| range.from..=range.to)
.filter(|&id| is_invalid_part_1(id))
.sum()
}With this change, I had the correct solution to part one. I read the problem statement for part two and went to bed.
Over lunch, I returned to part two. In this part of the problem, an ID is invalid if it is composed only of repeating sequences. I started off thinking about what would have to be true of those sequences. I only had to check sequences that are shorter than or equal to half the length of the ID. If a sequence is longer than half the length of the ID, it can’t repeat enough times to make up the full ID.
I could check these sequences by iterating through all possible sequence lengths from 2 through half the length of the ID (inclusive). For each sequence length, I could split the ID into chunks of that length and collect them into a hash set. If the hash set only had one entry, then the ID was made up of a single repeating sequence and was invalid.
I also identified a base case that would be quick to check. If the ID is all the same repeating digit, it must be invalid. This actually came back to bite me later.
With my first attempt at the is_invalid_part_2 function, I included a circuit-breaker for the case that the ID is composed of one repeating digit.
// In part two, an ID is invalid if it is composed exclusively
// of any repeated digit sequences.
fn is_invalid_part_2(id: u64) -> bool {
// If every digit is the same, the ID is invalid.
if id.to_string().chars().collect::<HashSet<char>>().len() == 1 {
return true;
}
let id_str = id.to_string();
for seq_len in 2..=id_str.len() / 2 {
let unique_sequences = id_str
.as_bytes()
.chunks(seq_len)
.collect::<HashSet<&[u8]>>();
if unique_sequences.len() == 1 {
return true;
}
}
false
}This got me into the worst possible situation that can happen with Advent of Code. My solution solved the example perfectly, but failed on the full puzzle input. The problem here was also not as simple as an integer overflow. I set this down until after work.
Before I left to pick up my wife from work, I put on a 30 minute timer to debug this and solve the problem.
What’s tough about debugging this kind of issue with Advent of Code is that there must be some edge case that shows up in the full puzzle data that does not show up in the example scenario.
I started by writing out the full logic of my solution line-by-line. I knew my answer is too high which meant that I am marking IDs as invalid that are definitely valid.
I wondered if when checking the possible sequences I was allowing IDs like 1234123 to get marked as invalid. If the seq_len got to 4, it could find the 1234 as the only sequence in the ID and mark it as invalid. I wrote a short test case. This wasn’t the issue.
I then broke down the code here and approached it a different way. I couldn’t think of an edge case that would cause a problem. Instead, I assumed that I misunderstood how collecting the bytes into a hash set would identify IDs consisting of only a single repeating sequence. You can see my comments and dbg statement from when I tried to parse it out.
// The issue must exist here.
// Go from a 2 length sequence to a sequence that is half the length of id_str
for seq_len in 2..=id_str.len() / 2 {
dbg!(seq_len);
let sequences: Vec<&str> = id_str
.as_bytes()
.chunks(seq_len)
.map(|seq| std::str::from_utf8(seq).unwrap())
.collect();
dbg!(&sequences);
let first = sequences.first().unwrap();
let all_same = sequences.iter().all(|seq| seq == first);
if all_same {
return true;
}
}This passed all the same tests and gave me the exact same answer I got before. Still too high.
I also tried filtering out sequence lengths that were not factors of the length of the id_str. This reduces the number of sequence checks that need to be done, but it doesn’t change the output.
for seq_len in 2..=id_str.len() / 2 {
+ if !id_str.len().is_multiple_of(seq_len) {
+ continue;
+ }
// ...Then I returned to my “base case” check. Maybe it was too general and I was assuming something incorrect about it. I could cover the base case with the “sequence checking” code by starting at a sequence of length 1. I removed my base case check and changed the iteration range for the sequence checking code.
// In part two, an ID is invalid if it is composed exclusively of any repeated digit sequences.
fn is_invalid_part_2(id: u64) -> bool {
let id_string = id.to_string();
for seq_len in 1..=id_string.len() / 2 {
// The length of the sequence must be a factor of the length of the ID.
// In other words, the sequence must fit into the ID a "whole" number of times.
if !id_string.len().is_multiple_of(seq_len) {
continue;
}
let sequences: Vec<&str> = id_string
.as_bytes()
.chunks(seq_len)
.map(|seq| std::str::from_utf8(seq).unwrap())
.collect();
let first = sequences.first().unwrap();
let all_same = sequences.iter().all(|seq| seq == first);
if all_same {
return true;
}
}
false
}This gave me the correct answer.
Why did my base case helper give me the wrong answer? Well the answer it gave was 66500947388 and the correct answer was 66500947346. The difference here was 42. My function wouldn’t have marked an ID of 42 as invalid. The issue must be multiple IDs which added together to 42. I realized this is likely the single-digit IDs that I was incorrectly marking as invalid. Because an invalid ID needed to be a sequence repeated at least twice, single digit IDs are valid. My base case was marking them as invalid.
I was able to verify this by adding a condition on my base case that required the number of digits in an invalid ID to be greater than 1.
With that mystery solved, I tidied up my is_invalid_part_2 function and tried to squeeze out more performance by using byte slices instead of iterating over characters in a string.
// In part two, an ID is invalid if it is composed exclusively of any repeated digit sequences.
fn is_invalid_part_2(id: u64) -> bool {
let id_string = id.to_string();
let len = id_string.len();
let bytes = id_string.as_bytes();
// We check the set of sequence lengths using:
// (1..=len / 2).filter(|&seq_len| len.is_multiple_of(seq_len))
// Which includes all sequence lengths 1 to half the length of the ID (inclusive),
// filtering out all sequence lengths that are not a factor of the length of the ID.
// In other words, the sequence must fit into the ID a "whole" number of times.
for seq_len in (1..=len / 2).filter(|&seq_len| len.is_multiple_of(seq_len)) {
// The first chunk...
let first = &bytes[0..seq_len];
// ...must be equal to all of the other chunks.
if bytes.chunks(seq_len).all(|seq| seq == first) {
return true;
}
}
false
} With a release build, my solution ran in 133.82ms on my MacBook Pro M2 Max.
2025-12-03T05:27:59.939Z DEBUG [advent_2025::day_02] Day 2
41294979841
66500947346
2025-12-03T05:28:00.073Z DEBUG [advent_2025::day_02] Duration 133.82msThings I Learned
When I wrote my test for has_even_digits(), I got a Clippy warning for using assert_eq!(has_even_n_digits(5), false). It suggests using assert!(!has_even_n_digits(5)). I don’t love this correction. It is objectively shorter, but I think the more verbose option breaks up the visual pattern of the asserts to more clearly convey that the false case is being evaluated here.
Still, I made the change given that it’s seen to be more idiomatic.
#[test]
fn test_has_even_digits() {
// Even digits
assert!(has_even_n_digits(20));
assert!(has_even_n_digits(4242));
// Odd digits
- assert_eq!(has_even_n_digits(0), false);
+ assert!(!has_even_n_digits(0));
- assert_eq!(has_even_n_digits(5), false);
+ assert!(!has_even_n_digits(5));
- assert_eq!(has_even_n_digits(100), false);
+ assert!(!has_even_n_digits(100));
- assert_eq!(has_even_n_digits(3429504), false);
+ assert!(!has_even_n_digits(3429504));
}I also learned that I can filter the values I’m iterating over instead of having a “continue” in the loop body.
When I first wrote the code to iterate through the sequence lengths in part two and wanted to exclude the sequence lengths that were not a factor of the ID length (i.e. wouldn’t fit evenly), I wrote it using a continue.
for seq_len in 1..=len / 2 {
if !len.is_multiple_of(seq_len) {
continue;
}
// ...But with some messing around as I cleaned up the solution at the end, I found that I could instead filter on the iterator itself.
// VVV This does the same thing as the continue
for seq_len in (1..=len / 2).filter(|&seq_len| len.is_multiple_of(seq_len)) {
// ... This one I also feel a little iffy on. There’s nothing that says the filter is more idiomatic and I can’t imagine there is a runtime difference. It feels kind of sleek to use the filter, but I feel like untrained eyes might miss it more often than they miss the continue which is seen often in other programming languages.