For prior days, please check out my Advent of Code 2025 Overview post. To see my final solution for this puzzle, go here.
Puzzle#
After yesterday’s Day 1: Secret Entrance solution, we now have access to the North Pole. Once we enter, we notice that the Gift Shop is having issues because an elf was playing around and added invalid IDs to the database. In order to save the day, we must go through the database (Puzzle Input) and find all invalid product IDs.
The puzzle input will look like this:
1
| 11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124
|
Part 1#
An invalid ID is any ID that is made up of two identical sequences of numbers. For example, 55 because it is made up of 5 twice, or 123123 because it is made up of 123 twice.
We must first parse each ID range, which is , separated. Then, check the inclusive range for any invalid IDs. Adding all the invalid IDs together will give the solution to the puzzle. Doing this on the above example would look like:
1
2
3
4
5
6
7
8
9
10
11
| 11-22 -> 11 & 22
95-115 -> 99
998-1012 -> 1010
1188511880-1188511890 -> 1188511885
222220-222224 -> 222222
1698522-1698528 -> (all valid IDs)
446443-446449 -> 446446
38593856-38593862 -> 38593859
565653-565659 -> (all valid IDs)
824824821-824824827 -> (all valid IDs)
2121212118-2121212124 -> (all valid IDs)
|
final answer: 1227775554
Part 1 Solution#
When doing similar LeetCode problems, I learned that anytime you are looking for patterns it is much easier to do all the logic on a string rather than a number. This means that when I loop through the range of IDs, I need to take the extra step to convert the value n to "n" (i.e. 123123 becomes "123123"). This becomes especially useful because Zig allows the use of string slices.
This will be very similar each day. If you are confused, reference my Day 01 solution for a more detailed explanation.
1
2
3
4
5
6
7
8
9
10
11
| var id_ranges = std.mem.splitScalar(u8, input, ',');
while (id_ranges.next()) |id_range| {
var bounds = std.mem.splitScalar(u8, id_range, '-');
const start_id = try std.fmt.parseInt(usize, bounds.next().?, 10);
const end_id = try td.fmt.parseInt(usize, bounds.next().?, 10);
for (start_id..end_id + 1) |id| {
const id_str = try std.fmt.bufPrint(&buf, "{d}", .{id});
// Check if ID is Valid or Invalid
}
}
|
Checking IDs#
My thought process was to split each ID string into two halves. If those halves are equal, then it is an invalid ID.
1
2
3
4
5
6
7
8
9
10
| pub fn bad_id(id: []const u8) bool {
const len = id.len;
const first_half = id[0 .. len / 2];
const second_half = id[len / 2 .. len];
if (std.mem.eql(u8, first_half, second_half)) {
return true;
}
return false;
}
|
Solution#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| pub fn part1(input: []const u8) !usize {
var bad_id_sum: usize = 0;
var id_ranges = std.mem.splitScalar(u8, input, ',');
var buf: [32]u8 = undefined;
while (id_ranges.next()) |id_range| {
var bounds = std.mem.splitScalar(u8, id_range, '-');
const start_id = try std.fmt.parseInt(usize, bounds.next().?, 10);
const end_id = try std.fmt.parseInt(usize, bounds.next().?, 10);
for (start_id..end_id + 1) |id| {
const id_str = try std.fmt.bufPrint(&buf, "{d}", .{id});
if (bad_id(id_str)) {
bad_id_sum += id;
}
}
}
return bad_id_sum;
}
pub fn bad_id(id: []const u8) bool {
const len = id.len;
const first_half = id[0 .. len / 2];
const second_half = id[len / 2 .. len];
if (std.mem.eql(u8, first_half, second_half)) {
return true;
}
return false;
}
|
Part 2#
There are still invalid IDs in the database. In this section, the rules for an invalid ID have been expanded. Now, an ID is invalid if it is made only of some sequence of digits repeated at least twice. This means that all IDs found invalid in the first part are still invalid, but now IDs such as 123123123 are invalid as well. Some examples of new invalid IDs are:
1
2
3
4
| 12341234 -> 1234 x2
123123123 -> 123 x3
1212121212 -> 12 x5
1111111 -> 1 x7
|
This means that our original example set would expand to:
1
2
3
4
5
6
7
8
9
10
11
| 11-22 -> 11 & 22
95-115 -> 99 & 111
998-1012 -> 1010
1188511880-1188511890 -> 1188511885
222220-222224 -> 222222
1698522-1698528 -> (all valid IDs)
446443-446449 -> 446446
38593856-38593862 -> 38593859
565653-565659 -> 565656
824824821-824824827 -> 824824824
2121212118-2121212124 -> 2121212121
|
Part 2 Solution#
Just like in Part 1, treating each ID as a string instead of a number will make this problem much more manageable. Also, for anyone familiar with LeetCode, you may recognize this puzzle as being very similar to question 459. Repeated Substring Pattern.
The only thing we will have to change from Part 1 is the bad_id() function. Now we must check all substrings from the first character up to half the length of the ID to see whether any of these substrings repeat. This means that for the ID 123123, we would need to check:
112123
This can be done using the following loop:
1
2
3
4
5
| const len = id.len;
for (1..(len / 2) + 1) |i| {
const substr = id[0..i];
// check each substring
}
|
Once a substring is built, we need to check if it can be repeated to form the ID. Because we don’t know how many times it may need to repeat, we loop until we match the length of the ID.
1
2
3
4
5
6
7
8
9
10
| var is_repeated = true;
var j: usize = i;
while (j < len) : (j += i) {
if (!std.mem.eql(u8, substr, id[j .. j + i])) {
is_repeated = false;
break;
}
}
if (is_repeated) return true;
|
We can make this more efficient by only checking substrings that divide evenly into the final ID length. This gives us the following updated bad_id() function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| pub fn bad_id(id: []const u8) bool {
const len = id.len;
for (1..(len / 2) + 1) |i| {
if (len % i == 0) {
const substr = id[0..i];
var is_repeated = true;
var j: usize = i;
while (j < len) : (j += i) {
if (!std.mem.eql(u8, substr, id[j .. j + i])) {
is_repeated = false;
break;
}
}
if (is_repeated) return true;
}
}
return false;
}
|