Advent of Code 2023: Day 01

Code for solutions available on GitHub.

I figured I would chronicle my solving of Advent of Code 2023. At least as far as I have time to solve it, and the energy to post about it. Posts may not appear on the day of the puzzle, and all puzzles may not be solved, but I’ll do my best. The puzzles can be found on the Advent of Code website. My solutions will be available on GitHub even if I don’t blog about them. My solutions will be in Rust, of course ;)

I am using an Advent of Code template repository, which takes care of downloading puzzle inputs, scaffolding solutions, reading the files, benchmarking, and submitting solutions. I’m really liking it so far. The input is given as a &str to functions named part_one and part_two, which return an Option<T: Display>.

Enough with the preamble. Let’s get to solving!

Trebuchet?!

The problem statement for day 1 is very simple. Given some lines of text, find the first and last digit in each line, create a two-digit number from them, and add them all together.

The example given is

1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet

It’s pretty clear that the list of numbers from this text will be 12, 38, 15, and 77. The last line only has one digit, which is both the first and last digit. The sum of these is 12 + 38 + 15 + 77 = 144.

Using str::lines will be used heavily throughout the event to iterate through the lines of the input. Each line can then be mapped from a &str to a byte slice (&[u8]) with str::as_bytes.

input
    .lines()
    .map(str::as_bytes)

For each byte slice, the first and last digits can be found by iterating over the byte slice first from the front, then from the back, matching for ASCII digits. A funny thing with ASCII digits is that they start at 0x30 and go up to 0x39. The decimal value is in the lower nybble. This means converting from an ASCII byte to the digit is easily done by bit-anding with the inverse of ‘0’. This is a kind of silly way to do it when you could just use a proper parsing procedure¹, but it works well.

input
    .lines()
    .map(str::as_bytes)
    .map(|line| {
        let a = line
            .iter()
            .find(|b| b.is_ascii_digit())
            .unwrap() & !b'0';
        let b = line
            .iter()
            .rfind(|b| b.is_ascii_digit())
            .unwrap() & !b'0';
        10 * a + b
    })

Finally, slapping a .sum() on the end will give the right answer. Iterators are great.

Part 2

As always, the second part adds a twist to the problem. Some of the digits in each line of the input are actually spelled out as words. The example given is

two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen

First solution - regex

Yeah, yeah, I know.

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

• Jamie Zawinski

So my first instinct was to simply use the regex crate to match the input with the strings one, two, three, etc as follows:

let re = regex::Regex::new(
    "one|two|three|four|five|six|seven|eight|nine|[0-9]"
);

This could have worked, but there is a slight complication. Some of the numbers can overlap, and the regex crate does not support overlapping matches. For example, if a line consisted of abcdtwoneqwerty, the correct number to construct would be 21. But the crate would only match two and be done, giving the incorrect number 22. To continue solving this problem with regex, lookahead is required, i.e. matching characters in the input without including them in the match. The regex crate doesn’t support this, but the pcre2 crate does.

So using that crate instead, I crafted the following regex:

(on(?=e)|tw(?=o)|thre(?=e)|four|five|six|seve(?=n)|eigh(?=t)|nine|[0-9])

So iterating through the matches on the input, together with a translation function, the first and last digit, whether spelled with numbers or letters, can be found. The final number and summation is then very similar to the first solution.

input
    .lines()
    .map(|line| {
        let mut matches = re.find_iter(line.as_bytes());
        let a = matches.next().unwrap();
        let b = matches.next().unwrap();

        let a = digit_string_to_digit(a.unwrap().as_bytes());
        let b = digit_string_to_digit(a.unwrap().as_bytes());
        10 * a + b
    })
    .sum()

This worked fine, but something bugged me with it. Part 1 ran in about 40 microseconds on the input, while this solution to part 2 ran in 1.5 milliseconds. Still not super slow, but having a bigger unit bugged me, so I wanted a better solution.

Second solution - transform and reuse part 1

Wouldn’t it be great if we could just replace all spelled out numbers in the string with the number they spell? Just replacing one with 1 and so on, then reuse the solution for part 1? I thought so too. But the overlap problem will rear its head again. Taking twone as an example again, depending on which number is replaced first can be rendered as tw1 or 2ne. So the replacing has to be done with more care, keeping the overlapping characters.

Instead of naïvely replacing one with 1, replace it with o1e. Keeping the first and last characters, which could overlap with two or eight respectively, allows for further replacements. This could be done for all digits, but I only did it for the ones that had overlaps with other digits. If no overlap, I did the naïve substitution. All that said, here’s the entire solution for part 2:

pub fn part_two(input: &str) -> Option<u32> {
    let input = input
        .replace("one", "o1e") // Keeping overlaps
        .replace("two", "t2o")
        .replace("three", "t3e")
        .replace("four", "4") // No overlap, can replace entire thing
        .replace("five", "5")
        .replace("six", "6")
        .replace("seven", "7n")
        .replace("eight", "e8t")
        .replace("nine", "n9");
    part_one(&input)
}

This runs in about 250 microseconds, which makes me happy :)