Parse two-digit numbers from text

Question

I am participating in this year's Advent of Code for fun.

Challenge 1.2 states:

The newly-improved calibration document consists of lines of text; each line originally contained a specific calibration value that the Elves now need to recover. On each line, the calibration value can be found by combining the first digit and the last digit (in that order) to form a single two-digit number.

--- Part Two ---

Your calculation isn't quite right. It looks like some of the digits are actually spelled out with letters: one, two, three, four, five, six, seven, eight, and nine also count as valid "digits".

Equipped with this new information, you now need to find the real first and last digit on each line. For example:

eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen

In this example, the calibration values are 29, 83, 13, 24, 42, 14, and 76. Adding these together produces 281.

What is the sum of all of the calibration values?

Cargo.toml

[package]
name = "aoc1_2"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
clap = { version = "4.4.10", features = ["derive"] }
env_logger = "0.10.1"
log = "0.4.20"

lib.rs

const DIGIT_NAMES: [&str; 9] = [
    "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
];

#[must_use]
pub fn two_digit_number(line: &str) -> Option<u8> {
    let mut digits = Digits::new(line);
    let first_digit = digits.next()?;
    let mut number = String::from(first_digit);

    if let Some(last_digit) = digits.last() {
        number.push(last_digit);
    } else {
        number.push(first_digit);
    }

    number.parse().ok()
}

#[derive(Debug)]
struct Digits<'a> {
    text: &'a str,
    size: usize,
    start: usize,
    end: usize,
}

impl<'a> Digits<'a> {
    #[must_use]
    pub fn new(text: &'a str) -> Self {
        Self {
            text,
            size: text.chars().count(),
            start: 0,
            end: 0,
        }
    }
}

impl<'a> Iterator for Digits<'a> {
    type Item = char;

    fn next(&mut self) -> Option<Self::Item> {
        if self.start == self.size {
            return None;
        }

        if self.end > self.size {
            self.start += 1;
            self.end = self.start + 1;
            return self.next();
        }

        match is_digit(&self.text[self.start..self.end]) {
            IsDigit::Yes(digit) => {
                self.end += 1;
                Some(digit)
            }
            IsDigit::Maybe => {
                self.end += 1;
                self.next()
            }
            IsDigit::No => {
                self.start += 1;
                self.end = self.start + 1;
                self.next()
            }
        }
    }
}

fn is_digit(text: &str) -> IsDigit {
    if text.len() == 1 {
        if let Some(chr) = text.chars().next() {
            if chr.is_ascii_digit() {
                return IsDigit::Yes(chr);
            }
        }
    }

    match text {
        "one" => IsDigit::Yes('1'),
        "two" => IsDigit::Yes('2'),
        "three" => IsDigit::Yes('3'),
        "four" => IsDigit::Yes('4'),
        "five" => IsDigit::Yes('5'),
        "six" => IsDigit::Yes('6'),
        "seven" => IsDigit::Yes('7'),
        "eight" => IsDigit::Yes('8'),
        "nine" => IsDigit::Yes('9'),
        text => {
            if DIGIT_NAMES.iter().any(|name| name.starts_with(text)) {
                IsDigit::Maybe
            } else {
                IsDigit::No
            }
        }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub enum IsDigit {
    Yes(char),
    Maybe,
    No,
}

#[cfg(test)]
mod tests {
    use crate::two_digit_number;

    const LINES: [(&str, u8); 7] = [
        ("two1nine", 29),
        ("eightwothree", 83),
        ("abcone2threexyz", 13),
        ("xtwone3four", 24),
        ("4nineeightseven2", 42),
        ("zoneight234", 14),
        ("7pqrstsixteen", 76),
    ];

    #[test]
    fn test_lines() {
        for (line, number) in LINES {
            assert_eq!(two_digit_number(line), Some(number));
        }
    }
}

main.rs

use aoc1_2::two_digit_number;
use clap::Parser;
use log::{error, warn};
use std::fs::read_to_string;
use std::path::PathBuf;
use std::process::exit;

#[derive(Debug, Parser)]
pub struct Args {
    #[arg(index = 1)]
    input: PathBuf,
}

impl Args {
    #[must_use]
    pub fn input(&self) -> String {
        read_to_string(&self.input).unwrap_or_else(|error| {
            error!("{error}");
            exit(1);
        })
    }
}

fn main() {
    env_logger::init();
    let args = Args::parse();
    let mut sum: u64 = 0;

    for line in args.input().lines() {
        two_digit_number(line).map_or_else(
            || {
                warn!("No number in: {line}");
            },
            |number| {
                sum += u64::from(number);
            },
        );
    }

    println!("The sum is: {sum}");
}

I don't like the fact, that I have the digit names twice, once in an array and once in the match statement. How can I improve the code?

Answer 1

Looking good

Your code is looking pretty good. Nice to see tests, notably.

Documentation?

Your code could do with some documentation.

Simplifying Match

The simple answer here is NOT to use match. You have an array of &str, in order from 1 to 9.

Simply doing a look-up for text in the array, then taking the index + 1 would give you the matching index. No need for duplication.

Beware indexing on strings

Indexing on strings uses byte indexes, and panics if they're not aligned on UTF-8 boundaries.

If the challenge specifies the text is ASCII... then it'll work. But you should be checking for it (.is_ascii()) and you then should use text.len() instead of text.chars().count().

The mix of Unicode-aware and ASCII-only code is jarring so far.

And if you need to be Unicode-aware, you may want to use the underlying bytes directly to avoid this boundary issue.

Algorithmic complexity

Your use of iteration is smart, in terms of code saved, but in terms of algorithmic it's not so great. Imagine a 1 million characters line: do you really need to go through all 1 million characters when you only care about the first and last match? Most likely NOT.

This suggests that you should instead find the first match and the last match, and outright ignore the middle of the line.

Algorithmic complexity (bis)

The way you do match the digits is also a bit... strange.

You have a quadratic algorithm here, mostly because you're not using efficient text searching algorithms. You don't even have to know those algorithms, you just need to use them by calling str.find(str).

Sketch Solution

Here is a proposed sketch addressing the algorithmic improvements in particular, you can see it on the playground:

use std::cmp;

/// Returns the two digits number as per specification.
///
/// That is, identifies the first and last digit, either spell as numerals or
/// literals, and catenates them to form a number.
///
/// If a single digit can be identified, it is used as both first and last.
///
/// If no digit can be identified, `None` is returned.
pub fn two_digit_number(text: &str) -> Option<u8> {
    assert!(text.is_ascii());

    let first = find_first_digit(text)?;
    let last = find_last_digit(text)?;

    Some(first * 10 + last)
}

//
//  Implementation
//

const DIGITS: [&str; 9] = [
    "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
];

//  Returns the first digit, as a number.
fn find_first_digit(text: &str) -> Option<u8> {
    const WINDOW: usize = 128;

    debug_assert!(text.is_ascii());

    let overlap = DIGITS
        .iter()
        .map(|d| d.len() - 1)
        .max()
        .expect(">= 1 digit");

    let mut start = 0;

    loop {
        let end = cmp::min(text.len(), start + WINDOW);

        let window = &text[start..end];

        let numeral = window.find(|c: char| c.is_ascii_digit());

        let literal = DIGITS
            .iter()
            .enumerate()
            .filter_map(|(v, literal)| window.find(literal).map(|i| (i, v)))
            .min();

        match (numeral, literal) {
            (None, None) => {
                start += WINDOW - overlap;
                if start < text.len() {
                    continue;
                } else {
                    break;
                }
            }
            (Some(numeral), None) => return Some(window.as_bytes()[numeral] - b'0'),
            (None, Some((_, v))) => return Some(v as u8 + 1),
            (Some(numeral), Some((literal, v))) => {
                if numeral < literal {
                    return Some(window.as_bytes()[numeral] - b'0');
                } else {
                    return Some(v as u8 + 1);
                }
            }
        }
    }

    None
}

#[test]
fn test_first_digit() {
    assert_eq!(None, find_first_digit("foobar"));
    assert_eq!(Some(1), find_first_digit("a1bc"));
    assert_eq!(Some(2), find_first_digit("23four"));
    assert_eq!(Some(3), find_first_digit("athree4five"));
}

//  Returns the last digit, as a number.
fn find_last_digit(text: &str) -> Option<u8> {
    const WINDOW: usize = 128;

    debug_assert!(text.is_ascii());

    let overlap = DIGITS
        .iter()
        .map(|d| d.len() - 1)
        .max()
        .expect(">= 1 digit");

    let mut end = text.len();

    loop {
        let start = if end >= WINDOW { end - WINDOW } else { 0 };

        let window = &text[start..end];

        let numeral = window.rfind(|c: char| c.is_ascii_digit());

        let literal = DIGITS
            .iter()
            .enumerate()
            .filter_map(|(v, literal)| window.rfind(literal).map(|i| (i, v)))
            .max();

        match (numeral, literal) {
            (None, None) => {
                if start > 0 {
                    end -= WINDOW - overlap;
                    continue;
                } else {
                    break;
                }
            }
            (Some(numeral), None) => return Some(window.as_bytes()[numeral] - b'0'),
            (None, Some((_, v))) => return Some(v as u8 + 1),
            (Some(numeral), Some((literal, v))) => {
                if numeral > literal {
                    return Some(window.as_bytes()[numeral] - b'0');
                } else {
                    return Some(v as u8 + 1);
                }
            }
        }
    }

    None
}

#[test]
fn test_last_digit() {
    assert_eq!(None, find_last_digit("foobar"));
    assert_eq!(Some(1), find_last_digit("a1bc"));
    assert_eq!(Some(2), find_last_digit("four32"));
    assert_eq!(Some(3), find_last_digit("five4threea"));
}

The repetition between first and last is annoying, and could be abstracted over... but the cost of abstracting the iteration, find/rfind, and min/max, would likely exceed the cost of duplication in the first place.