23 Jan

AoC Day 1: Trebuchet

Before I get stuck into the first challenge for the most recent year’s contest, a few words about my general approaches this year.

My AoC 2023 Challenge

In previous years, I’ve used languages like Java and Python (and the aforementioned Excel spreadsheet) to solve the daily challenges. Even using languages I know and use and teach, I always learn something new, like modulo math, or really deepen my understanding of other techniques, like depth- and breadth-first searches. This year, I decided to change things up, and take on learning a new language as well, namely Rust.

Why Rust? In my reading, it’s been gaining a lot of traction in the system programming community — there’s a project to bring Rust into the Linux kernel, and even Microsoft is bringing it into certain core libraries. It combines some of the low-level capabilities of C with the modern infrastructure of Python or JavaScript. It’s also very strict, using language constructs and compiler checks to prevent a lot of potential errors that can lead to crashes and security issues. This strictness is what caused me the most challenges this year.

I started learning Rust by reading The Rust Programming Language Book — I used the web site and an ebook version I procured a while ago. I also got turned on to the Rustlings Course, which I highly recommend as a great supplement to your Rust learning. It definitely helped me grok concepts like borrowing and lifetimes that I haven’t needed to worry about in Python or Java. I also read a lot at the Rust subreddit, which has a lot of great resource links at the top of the page.

So as you read these articles, you’ll not only get a sense of how I solve them, but also how I worked around and through the strictures of this language, and how my ideas of how a problem should be solved were modified by the language.

One word of warning — if you are a seasoned Rustacean, forgive me, and be prepared for some truly horrendous code at first. I didn’t really start to grok the the code I stole until Day 7 or later…

Day 1: Trebuchet

Day 1 of the Advent of Code is usually a warm-up, although there is a bit of trick to this one. I encourage you to read the problem description for yourself before continuing.

From the description, you are given a list of lines which contain numbers and letters. You are to retrieve the first and last single digit number in each line, combine them to form one two digit number, then add them all to form a single value.

The sample looks like this:

1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet

So for the first line, you get 1 and 2 to make 12. The next lines give you 38, 15, and 77. Note that there is only one number in the last line — in this case, it serves as both the first and last number, so you get 77. Adding them gives you 142, which is the answer you need.

Of course, this is just the sample data — your real data will be different, as was mine.

For those interested, all my code can be found on my Codeberg repo. More on Codeberg later…

Setup

First, I need to read all the lines from the input file. Since this is a normal first step for most day’s problems, I use some boilerplate code to read all the lines from a given file:

let _filename = "/home/jon/git/AoC2023/day01/input";
// let _filename = "/home/jon/git/AoC2023/day01/sample";

// Open the file
let file = File::open(_filename).expect("Error opening file");
let reader = BufReader::new(file);
let lines = reader.lines()
                  .map(|l| l.expect("Could not parse line"))
                  .collect();

This creates a dynamic array (called a vector) filled with strings in the variable called lines. I can feed lines into functions which solve the problem. I used this boilerplate for all my AoC problems in Rust — I’ve used similar standard code in previous years in Python and Java as well.

Approach

Figuring out how I am going to approach a problem is more important than the code. Once I have an approach in mind, I can start figuring out how to accomplish all the little parts to create a coherent whole, and the language doesn’t matter — the right approach can be implemented in Rust, Python, Java, or any other language.

My initial thoughts for this problem were to do the followiing:

  • Read each line, character by character, from left to right
  • Identify all the characters which are numeric
  • Figure out which is the first digit, and which is the last
  • Create a single number from them to add together

This early in my Rust journey, the very first step was the first stumbling block. How do you inspect every character in a string in Rust?

String Operations

In Python, you can treat a string like a list, and just use a for loop to get to the individual characters:

s = "1abc2"
for c in s:
    if c.isdigit():
        # Do something here

This simple loop will work in Rust, but because Rust is really really picky about what you do with variables, there are some additional steps.

You can’t just treat a String like a list in Rust — you need to get a vector (basically a Python list, or a Java ArrayList) of the characters in the string to work with. So how do you do that? As it turns out, there is a simple way using the .chars() method:

for ch in line.chars(){
    if ch >= '0' && ch <= '9'{
        // Do something here
    }
}

Only one extra step, but it’s necessary.

Oh, and I also learned later that I could have used ch.is_digit() instead of comparing to '0' and '9', but that’s why I do this — to learn.

So now how do I know which is the first digit, and which is the last?

Bring a Flag

To figure this out, I reasoned that I could classify all the digits in the string in two categories:

  • The first digit
  • Not the first digit

Finding the first digit is relatively easy — just keep reading characters until I find a digit and store it in first.

Once I find the first, I can find the last by simply storing every other digit I read in the last variable. Because I’m reading characters from left to right, the last digit will be the one that remains when the loop is done.

How do I know I found the first digit? None of the digits in the string are zero, so as long as first is zero, we haven’t found it yet. When it’s non-zero, then we know we’ve found it. In short, first is doing double duty, storing the value of the first digit, and as a flag to tell me which other digits I care about.

Here’s what the whole loop looks like:

let mut first = 0;
let mut last = 0;

// Scan each line for numbers
for ch in line.chars(){
    if ch >= '0' && ch <= '9'{
    // Do we have a first number
        if first == 0{
            first = ch.to_digit(10).unwrap();
        } else {
            last = ch.to_digit(10).unwrap();
        }
    }
}
// Did we only find a single digit?
if last == 0 {
    last = first;
}

sum += first*10 + last;

The if last == 0 statement handles the case where there is only one digit in the string.

Part 2

As always with the Advent of Code, part 2 is a complication on the part 1 code. You often need to rework, or even rewrite, your code to solve part 2.

In this case, part 2 added that some of the digits to use aren’t digits, but the digits spelled out with letters ('one', 'two', 'three', and so on). The new sample was:

two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen

The first line should return 29, since 'two' and 'nine' are the first and last digits. Similarly, the next lines return 83, 13, 24, 42, 14, and 76.

My approach was the same — scan the line for digits, save them, and add them up. I just needed to adjust my digit scanning.

Slicing Your Words

As before, I scanned character by character, looking for digits. However, if I didn’t find a digit, I had to see if one of the spelled out digits was present. That required figuring out how to get a substring from a larger string.

Luckily, Rust has the concept of slices, where you can pick out a small span from a string, array, or vector using the starting index and the number of elements to get. I used that to compare the slice to each of the spelled out digits. Of course, I needed to make sure I don’t run off the end of the string as well.

I’m sure there is a more Rusty (?) way to do this, but here’s my take on this:

for (i, ch) in line.char_indices(){
    if ch >= '0' && ch <= '9'{
        digit = ch.to_digit(10).unwrap();
    } else {
        if i+3 <= line.len() && line[i..i+3] == String::from("one"){
            digit = 1;
        }
        if i+3 <= line.len() && line[i..i+3] == String::from("two"){
            digit = 2;
        }
        if i+5 <= line.len() && line[i..i+5] == String::from("three"){
            digit = 3;
        }
        if i+4 <= line.len() && line[i..i+4] == String::from("four"){
            digit = 4;
        }
        if i+4 <= line.len() && line[i..i+4] == String::from("five"){
            digit = 5;
        }
        if i+3 <= line.len() && line[i..i+3] == String::from("six"){
            digit = 6;
        }
        if i+5 <= line.len() && line[i..i+5] == String::from("seven"){
            digit = 7;
        }
        if i+5 <= line.len() && line[i..i+5] == String::from("eight"){
            digit = 8;
        }
        if i+4 <= line.len() && line[i..i+4] == String::from("nine"){
            digit = 9;
        }
    }

I saw some folks on Reddit having problems here because they were substituting the digit in for the words within the string. This causes a problem with strings like:

sevenine
eighthree
oneightwone

Using substitution, the first string yields 7ine, which loses the final nine. Similarly, the other strings lose digits with substitution — 8hree and 1ight2ne.

My code avoids this by just reading the word and leaving the string intact, which is a preferred way of handling data in Rust.

Conclusion

This was an interesting starter puzzle, and gave me some early insight into Rust and what I need to know to solve a problem. I know there are a few things I can do to improve this code, making it more Rust-licious (?). We’ll see some examples of that later.

How did you solve this? Any insights into my code? Questions on my approachj? Let me know in the comments below!