My thought process through a random Advent of Code problem

I tried Advent of Code for the first time last year. It was good fun. The process of being given a new, fresh problem every day was stimulating for the brain, and I’m waiting patiently for this years installment.

Not patiently enough, because today for NaBloPoMo I’m going to walk through solving a random problem from the past.

The problem

I picked day 5 of 2018. Very early on, so hopefully not too hard. I’m rusty ok.

Since I’m rusty, I’ll write my solution in Rust.

Not because it’s my favourite language or anything.

$ mkdir aoc2018 && cd aoc2018
$ cargo init .

I’ll add a binary to Cargo.toml:

[[bin]]
name = "day5"
path = "src/day5.rs"

and I’ll put a placeholder in src/day5.rs:

fn main() {
    println!("hi there!");
}

$ cargo run --bin day5
hi there!

Now lets actually read the problem. If you didn’t open the link above: have it again.

Ok, I think I have a pretty good idea of how this will be solved. We have a long string, and we want to delete any occurrences of a lowercase letter followed by the uppercase of the same letter, or vice-versa. This deletion creates a new string, where the process is repeated. We are done when there are no more deletions to do.

Conceptually, I can check the absolute difference (max - min) of the ASCII code of each sequential pair of letters. If the result is 32, that means we have a matching pair. After deleting the pair of letters, we continue from just before the deletion. When we hit the end of the string, we know we’re done.

In practice, I’ll use a Vec<char> (list of characters) for the string, and a usize (positive integer) for an index cursor. I can just do index lookups and run .remove(cursor) twice to delete the pair.

One tricky thing is handling the start and end of the list nicely. I’ll simply account for that.

Cool, lets get code down:

fn parse_polymer(fname: &str) -> Vec<char> {
    if let Some(file) = fs::read_to_string(fname).ok() {
        return file.trim().chars().collect();
    } else {
        panic!("`{}` not found.", fname);
    }
}

This turns a file into its component chars, and returns the whole thing as a list.

if let is nice here. The call to fs::read_to_string(fname) returns a Result type, and .ok() turns that into an Option. This means that if the read succeeded, file gets populated and we enter the ‘true’ part of the statement. If the file doesn’t exist we simply give up. panic!() terminates the program and gives the contained formatted string back to the user.

For completeness: .trim() removes any whitespace before/after, .chars() converts a String into an iterator of chars, and .collect() converts an iterator into whatever collection seems reasonable. The return type is Vec<char>, so Rust is smart enough to collect the iterator as that type.

I’ll also set up an empty function and my main:

fn deconstruct_polymer() -> Vec<char> {
    vec![]
}

fn main() {
    println!("part one: {}", deconstruct_polymer().len());
}

Good start.

The placeholder in deconstructed_polymer() is an implicit return. Rust lets you omit the return and semicolon. It’s... one of the language features I’ve ever seen. I guess it makes it more OCaml-y. I like OCaml. I’m not massively convinced.

Now for the hard part of the problem: actually getting rid of things.

First I’ll define the polymer and the cursor, and also a function for checking if they’re the right distance from each other:

fn deconstruct_polymer() -> Vec<char> {
    let mut polymer = parse_polymer("data/5.test");
    let mut cur = 1;

    fn split_case(c1: char, c2: char) -> bool {
        u32::from(c1).abs_diff(u32::from(c2)) == 32
    }
}

Yeah cool, might as well just throw the function inside the other function.

Now I just need to check each position and do the cursor movements:

fn deconstruct_polymer() -> Vec<char> {
    // ...

    while cur != polymer.len() - 1 {
        if split_case(polymer[cur], polymer[cur + 1]) {
            polymer.remove(cur);
            polymer.remove(cur);

            if cur != 0 { cur -= 1 }
        } else {
            cur += 1;
        }

    }

    polymer
}

Not too bad, just a little bit of checking to make sure I don’t move the cursor too far in either direction. Let’s give it a spin!

part one: 10

Ayy, now I’ll swap over to the big input.

part one: 10972

Right answer! Onto part two.

If you try to use 10972 to solve the problem, you’ll learn each user gets a different puzzle input. I don’t know why you’re so upset: I just gave you all the code.

Part two:

Ok this part seems a lot less ‘elegant’: we’re just trying out removing a bunch of items from the list before each deconstruction. I wanna be fancy and do some sort of filter thing. Advent of Code is all about finding a solution to a given problem, but it’s also all about showing off.

I’ll modify main, and make a slight change to how we’re giving deconstruct_polymer the polymer Vec.

fn main() {
    let polymer = parse_polymer("5.input");
    println!("part one: {}", deconstruct_polymer(polymer).len());
    println!("part two: {}", best_shortened_polymer());
}

fn deconstruct_polymer(mut polymer: Vec<char>) -> Vec<char> {
    // ...
}

Now for best_shortened_polymer. First we’ll grab a set of lowercase letters, so we’re not doing redundant operations:

use std::collections::HashSet;

fn best_shortened_polymer() -> usize {
    let polymer = parse_polymer("src/5.input");
    let polymer_set = polymer
        .iter()
        .map((c) => c.to_ascii_lowercase())
        .collect::<HashSet<char>>();

    // ...
}

...and then I’ll just throw the character removal in a loop, followed by a call to part one:

fn best_shortened_polymer() -> usize {
    //...

    let shortest = polymer_set.iter().map(|check| {
        let test = polymer
            .clone()
            .into_iter()
            .filter(|c| !c.eq_ignore_ascii_case(check))
            .collect::<Vec<char>>();

        deconstruct_polymer(test).len()
    }).min();

    // .min() returns an option, in case it didn’t check any elements.
    if let Some(v) = shortest { v } else { panic!("No shortest polymer") }
}

part one: 10972
part two: 5278

Success!

That was pretty nice

I purposefully chose an early-day problem because I didn’t want things to get too off-the-rails. There’s probably a better and fancier solution to this, like building the polymer list based on a two char buffer. If the buffer doesn’t create a matching pair, push the first element onto the list and move the second element to the first position. You’d avoid a lot of removing, which is an O(n)-ish operation in rust.

remove(i) on a list with n elements is O(n-i)

But that’s part of it when you do advent of code: there are always better ways to do things, which is why it’s good to talk about your solutions. You learn how others tackle problems, which helps you tackle new problems.

I am pretty excited for December.