Advent of Rust 16 and 17: Really, That’s More Iterators Than I Wanted; and More Adventures With NumRust

The last couple of days I took a break from this chronicle of my attempt to teach myself the Rust programming language by solving the programming puzzles on Advent of Code 2020. But now I’m back with another two days’ worth of puzzles!

One thing that I read in the meantime, thanks to a tip from Federico was the first installment of someone else’s blog who’s doing the same thing as I am. That blog is a really good read, and I think the main difference with my series is that the author is already a Rust expert! The style is also very different, as well; I am mostly trying to emphasize the things that I found surprising, struggled with, or didn’t understand. Their blog is much more didactic.¹

One really cool thing that I picked up from that blog post is the include_str!() macro, which makes it possible to read the input file into a string at compile time, and dispense with the read_lines() boilerplate and most of the error handling. I think I will be using this from now on. This way also makes it easy to substitute in the example inputs from the puzzle descriptions.

Also in the meantime, I spent a lot of time trying to configure either of the Rust Enhanced or SublimeLinter-contrib-rustc plugins for my Sublime Text editor. I had a surprisingly hard time with this, neither of them seemed to work. In the latter case it was because the plugin was out of sync with the API of the newest version of SublimeLinter. I thought the former plugin, Rust Enhanced, would be a smooth experience since it claims to be the officially sanctioned Rust plugin for Sublime Text, but it didn’t work either! Whenever I would try to run any of the Rust commands, I would get this message:

Blocking waiting for file lock on build directory

I finally figured out that this error goes away if you run cargo clean. My guess, it’s probably because I copied the puzzle15 folder to puzzle16 today, instead of creating it with cargo new! My bad!

The editor plugin makes development much smoother, since I can get the compiler’s answer directly when I save the file, without even leaving my editor. This makes the endless rounds of compile, add a &, compile, add a *, go much faster.

It is mildly annoying that the plugin shows the compiler messages inline, instead of in the editor gutter like all the SublimeLinter plugins do. One day when I have time, I’ll investigate to see if there is a setting that controls this.

On to the puzzle.

Day 16, Part 1

This puzzle is about train tickets. We get a more free-form input file than usual, and we have to use it to deduce the meanings of fields on train tickets that we’ve scanned. In the input file there is a list of valid ranges for each field, and lists of fields on train tickets. Some of the train tickets are invalid, and that’s what Part 1 of the puzzle is about. The answer is the sum of all the values on any ticket that are not valid no matter what field they belong to.

I start by thinking about what data structure I would use to store the ranges. Some of them are overlapping and it would be nice to be able to collapse those. I google “rust collapse range” and land in the intervallum package, where the IntervalSet type seems like exactly what I want for this. It can collapse two intervals into a single interval set which covers the two intervals, and it is allowed to have one or more holes in the middle. So I can collapse all the valid ranges together, and then check each ticket field value to see if it is contained within the any of the valid ranges.

Here’s the program that I write. I split the input into three blocks, and process the first one (the one with the valid ranges in it.)

extern crate gcollections;
extern crate interval;
#[macro_use]
extern crate scan_fmt;

use gcollections::ops::set::Union;
use interval::interval_set::ToIntervalSet;

fn main() {
    let input = "class: 1-3 or 5-7\n\
row: 6-11 or 33-44\n\
seat: 13-40 or 45-50\n\
\n\
your ticket:\n\
7,1,14\n\
\n\
nearby tickets:\n\
7,3,47\n\
40,4,50\n\
55,2,20\n\
38,6,12\n";
    // let input = include_str!("input");
    let mut blocks = input.split("\n\n");

    let mut constraints = vec![].to_interval_set();
    blocks
        .next()
        .unwrap()
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            (parts.next().unwrap(), parts.next().unwrap())
        })
        .flat_map(|(_, intervals)| intervals.split(" or "))
        .map(|interval| {
            scan_fmt!(interval, "{d}-{d}", u16, u16)
                .unwrap()
                .to_interval_set()
        })
        .for_each(|interval| constraints = constraints.union(&interval));
    println!("{}", constraints);

    let my_ticket_block = blocks.next().unwrap();
    assert!(my_ticket_block.starts_with("your ticket:\n"));

    let other_tickets_block = blocks.next().unwrap();
    assert!(other_tickets_block.starts_with("nearby tickets:\n"));
}

I initially thought .collect::<Vec<(u16, u16)>>().to_interval_set() would work, but that gives me a panic: “This operation is only for pushing interval to the back of the array, possibly overlapping with the last element.” so apparently we have to use union() on each item. Having a bit of experience with Rust and its reputation for safety, I’d expect it to return a Result or something if you tried this, instead of crashing. This seems consistent with my impression that some Rust packages are high quality and others are a bit rough around the edges, similar to NPM packages. This one seems a bit rough and underdocumented, but good enough that we can still use it.

To use the union() method, I inexplicably have to include the gcollections package as well.

Once that’s done I can process the third block as well, and calculate the answer with one long iterator chain:

let other_tickets_block = blocks.next().unwrap();
assert!(other_tickets_block.starts_with("nearby tickets:\n"));
let error_rate: u16 = other_tickets_block
    .lines()
    .skip(1)
    .flat_map(|line| line.split(','))
    .map(|s| s.parse().unwrap())
    .filter(|val| !constraints.contains(val))
    .sum();

println!("Error rate: {}", error_rate);

Day 16, Part 2

In Part 2 of the puzzle we have to discard all the tickets that had an invalid value, and with the remaining tickets figure out which field belongs to which field name, by comparing the fields with the valid ranges for each field name. The answer is the product of all the values on our own ticket that correspond to fields whose name starts with “departure”.

A lot of the logic will be the same as in Part 1, so I start by rewriting Part 1 to save the intermediate steps that we’ll need for Part 2 as well:

let mut blocks = input.split("\n\n");

let constraints_block = blocks.next().unwrap();
let field_descriptions: HashMap<&str, interval::interval_set::IntervalSet<u16>> =
    constraints_block
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            let field_name = parts.next().unwrap();
            let intervals = parts.next().unwrap();
            let interval_set = intervals
                .split(" or ")
                .map(|interval| scan_fmt!(interval, "{d}-{d}", u16, u16).unwrap())
                .collect::<Vec<(u16, u16)>>()
                .to_interval_set();
            (field_name, interval_set)
        })
        .collect();

let mut all_valid_values = vec![].to_interval_set();
for interval in field_descriptions.values() {
    all_valid_values = all_valid_values.union(interval);
}

let my_ticket_block = blocks.next().unwrap();
assert!(my_ticket_block.starts_with("your ticket:\n"));

let other_tickets_block = blocks.next().unwrap();
assert!(other_tickets_block.starts_with("nearby tickets:\n"));
let (valid_tickets, invalid_tickets): (Vec<Vec<u16>>, Vec<Vec<u16>>) = other_tickets_block
    .lines()
    .skip(1)
    .map(|line| {
        line.split(',')
            .map(|s| s.parse().unwrap())
            .collect::<Vec<u16>>()
    })
    .partition(|ticket| ticket.iter().all(|val| all_valid_values.contains(val)));

if is_part2() {
} else {
    let error_rate: u16 = invalid_tickets
        .iter()
        .flat_map(|ticket| ticket.iter().filter(|val| !all_valid_values.contains(val)))
        .sum();
    println!("Error rate: {}", error_rate);
}

I am excited to use the partition() method, that I found by browsing the documentation, to split the iterator into two vectors, one of valid and one of invalid tickets.

I now have vectors of the numbers from each ticket. However, to solve this puzzle I’ll have to transform those into vectors of all the numbers in each position on the tickets (for example, a vector of all numbers coming first on each ticket, coming second, etc.) instead of vectors of each ticket. This sounds like something I should be able to do with a zip() method which I’m familiar with from Python.

Rust’s zip() takes only two iterators. At first I think that itertools::multizip will solve my problem, but that takes a number of iterators that must be known at compile time, which is not the case here. After some more googling I find this Stack Overflow answer and find a code snippet which I simply copy as-is into my program. I don’t really understand it, but I understand enough to see approximately what it does.

I decide to store the possible fields for each position on the ticket as a vector of hashsets, possible_fields_by_position. The order of the vector is by position of the number on the ticket. The elements of the vector are hash sets consisting of zero or more field numbers, which the numbers in this position might be valid for.

To do this, I have to pre-fill the vector with empty hashsets, and I’m not sure how to do this. Googling “rust fill vector of hashset” sends me here.

If the problem is solvable, then there will be at least one element of the vector where the hash set has only one item in it, and then we will know what field corresponds with that position on the ticket. We can then consider that field “determined” and remove it from all the other hash sets in the vector, which hopefully leaves at least one more hash set with only one item, allowing is to uniquely determine another field, and so on.

One interesting thing to note is that I first had this:

for (_, remaining_fields) in possible_fields_by_position {
    remaining_fields.remove(field_ix);
}

Here, for the first time that I’ve seen, the compiler gives a plain wrong suggestion:

error[E0382]: borrow of moved value: `possible_fields_by_position`
   --> puzzle16.rs:97:15
    |
78  |         let mut possible_fields_by_position: Vec<(usize, HashSet<usize>)> = (0..valid_tickets[0]
    |             ------------------------------- move occurs because `possible_fields_by_position` has type `Vec<(usize, std::collections::HashSet<usize>)>`, which does not implement the `Copy` trait
...
97  |         while possible_fields_by_position.len() > 0 {
    |               ^^^^^^^^^^^^^^^^^^^^^^^^^^^ value borrowed here after move
...
102 |             for (_, remaining_fields) in possible_fields_by_position {
    |                                          ---------------------------
    |                                          |
    |                                          value moved here, in previous iteration of loop
    |                                          help: consider borrowing to avoid moving into the for loop: `&possible_fields_by_position`

error[E0596]: cannot borrow `remaining_fields` as mutable, as it is not declared as mutable
   --> puzzle16.rs:103:17
    |
102 |             for (_, remaining_fields) in possible_fields_by_position {
    |                     ---------------- help: consider changing this to be mutable: `mut remaining_fields`
103 |                 remaining_fields.remove(field_ix);
    |                 ^^^^^^^^^^^^^^^^ cannot borrow as mutable

Even without the above, I certainly had more trouble than usual with getting the & operators right! Maybe it’s time for a re-read of the chapter on ownership in the Rust book.

For the last step I am also left wondering how to pre-fill a vector with zeros. The syntax is [0; number_of_zeros]. I do actually stumble upon a Github issue complaining about it not being documented well enough.

Here is the very long full program:

extern crate gcollections;
extern crate interval;
#[macro_use]
extern crate scan_fmt;

use gcollections::ops::set::{Contains, Union};
use interval::interval_set::{IntervalSet, ToIntervalSet};
use std::collections::HashSet;
use std::env;

// https://stackoverflow.com/a/55292215/172999
struct Multizip<T>(Vec<T>);

impl<T> Iterator for Multizip<T>
where
    T: Iterator,
{
    type Item = Vec<T::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.iter_mut().map(Iterator::next).collect()
    }
}

fn main() {
    let input = include_str!("input");
    let mut blocks = input.split("\n\n");

    let constraints_block = blocks.next().unwrap();
    let field_descriptions: Vec<(&str, IntervalSet<u16>)> = constraints_block
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            let field_name = parts.next().unwrap();
            let interval_set = parts
                .next()
                .unwrap()
                .split(" or ")
                .map(|interval| scan_fmt!(interval, "{d}-{d}", u16, u16).unwrap())
                .collect::<Vec<(u16, u16)>>()
                .to_interval_set();
            (field_name, interval_set)
        })
        .collect();

    let mut all_valid_values = vec![].to_interval_set();
    for (_, interval) in &field_descriptions {
        all_valid_values = all_valid_values.union(interval);
    }

    let my_ticket_block = blocks.next().unwrap();
    assert!(my_ticket_block.starts_with("your ticket:\n"));

    let other_tickets_block = blocks.next().unwrap();
    assert!(other_tickets_block.starts_with("nearby tickets:\n"));
    let (valid_tickets, invalid_tickets): (Vec<Vec<u16>>, Vec<Vec<u16>>) = other_tickets_block
        .lines()
        .skip(1)
        .map(read_csv_numbers)
        .partition(|ticket| ticket.iter().all(|val| all_valid_values.contains(val)));

    if is_part2() {
        let mut possible_fields_by_position: Vec<_> = (0..valid_tickets[0].len())
            .map(|_| HashSet::new())
            .enumerate()
            .collect();
        for (position, position_values) in
            Multizip(valid_tickets.iter().map(|ticket| ticket.iter()).collect()).enumerate()
        {
            for (field_ix, (_, interval)) in field_descriptions.iter().enumerate() {
                if position_values.iter().all(|val| interval.contains(val)) {
                    possible_fields_by_position[position].1.insert(field_ix);
                }
            }
        }

        possible_fields_by_position.sort_by_key(|(_, set)| set.len());
        possible_fields_by_position.reverse();

        let mut determined_fields_by_position = vec![0; possible_fields_by_position.len()];
        while !possible_fields_by_position.is_empty() {
            let (position, possible_fields) = possible_fields_by_position.pop().unwrap();
            assert!(possible_fields.len() == 1, "unable to determine fields");
            let field_ix = possible_fields.iter().next().unwrap();
            determined_fields_by_position[position] = *field_ix;
            for (_, remaining_fields) in &mut possible_fields_by_position {
                remaining_fields.remove(field_ix);
            }
        }

        let my_ticket_values: Vec<u16> = my_ticket_block
            .lines()
            .skip(1)
            .flat_map(read_csv_numbers)
            .collect();

        let answer: u64 = determined_fields_by_position
            .iter()
            .map(|field_ix| field_descriptions[*field_ix].0)
            .zip(my_ticket_values.iter())
            .filter(|(field_name, _)| field_name.starts_with("departure"))
            .map(|(_, value)| *value as u64)
            .product();

        println!("My ticket values {:?}", answer);
    } else {
        let error_rate: u16 = invalid_tickets
            .iter()
            .flat_map(|ticket| ticket.iter().filter(|val| !all_valid_values.contains(val)))
            .sum();
        println!("Error rate: {}", error_rate);
    }
}

fn read_csv_numbers(line: &str) -> Vec<u16> {
    line.split(',').map(|s| s.parse().unwrap()).collect()
}

Day 17, Part 1

I didn’t manage to finish the Day 16 blog post before I started working on Day 17’s puzzle, so I’m tacking it on here. Day 17 brings us a three-dimensional Conway’s Game of Life!

I remember very well implementing Game of Life with a different twist on Day 11, so today I will write some more code using ndarray, copying from Day 11 where I can.

In three dimensions we have 3³ − 1 = 26 neighbours instead of the 3² − 1 = 8 that we have in two dimensions. I “hand-unrolled”² the loop over the 8 neighbours in the calc_neighbours() function from Day 11:

fn calc_neighbours(seats: &Array2<i8>) -> Array2<i8> {
    let shape = seats.shape();
    let width = shape[0];
    let height = shape[1];
    let mut neighbours = Array2::<i8>::zeros(seats.raw_dim());
    // Add slices of the occupied seats shifted one space in each direction
    let mut slice = neighbours.slice_mut(s![1.., 1..]);
    slice += &seats.slice(s![..width - 1, ..height - 1]);
    slice = neighbours.slice_mut(s![.., 1..]);
    slice += &seats.slice(s![.., ..height - 1]);
    slice = neighbours.slice_mut(s![..width - 1, 1..]);
    slice += &seats.slice(s![1.., ..height - 1]);
    slice = neighbours.slice_mut(s![1.., ..]);
    slice += &seats.slice(s![..width - 1, ..]);
    slice = neighbours.slice_mut(s![..width - 1, ..]);
    slice += &seats.slice(s![1.., ..]);
    slice = neighbours.slice_mut(s![1.., ..height - 1]);
    slice += &seats.slice(s![..width - 1, 1..]);
    slice = neighbours.slice_mut(s![.., ..height - 1]);
    slice += &seats.slice(s![.., 1..]);
    slice = neighbours.slice_mut(s![..width - 1, ..height - 1]);
    slice += &seats.slice(s![1.., 1..]);
    neighbours
}

That will simply not do when we have 26 neighbours! I decide to first rewrite it in the Day 11 code with the outer product of two vectors [-1, 0, 1] and make sure that it still gives the same answer. I find that the cartesian_product() method from Itertools is ideal for this:

fn calc_neighbours(seats: &Array2<i8>) -> Array2<i8> {
    let shape = seats.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let mut neighbours = Array2::<i8>::zeros(seats.raw_dim());
    // Add slices of the occupied seats shifted one space in each direction
    for (xstart, ystart) in (-1..=1).cartesian_product(-1..=1) {
        if xstart == 0 && ystart == 0 {
            continue;
        }
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let mut slice = neighbours.slice_mut(s![xdest, ydest]);
        slice += &seats.slice(s![xsource, ysource]);
    }
    neighbours
}

It’s still pretty verbose, and I suspect it could be done more cleverly, but this is good enough to be straightforwardly adapted to three dimensions for Day 17:

fn calc_neighbours(grid: &Array3<i8>) -> Array3<i8> {
    let shape = grid.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let depth = shape[2] as isize;
    let mut neighbours = Array3::<i8>::zeros(grid.raw_dim());
    // Add slices of the occupied grid shifted one space in each direction
    for starts in iter::repeat(-1..=1).take(3).multi_cartesian_product() {
        if starts.iter().all(|start| *start == 0) {
            continue;
        }
        let (xstart, ystart, zstart) = (starts[0], starts[1], starts[2]);
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let zdest = zstart.max(0)..(depth + zstart).min(depth);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let zsource = (-zstart).max(0)..(depth - zstart).min(depth);
        let mut slice = neighbours.slice_mut(s![xdest, ydest, zdest]);
        slice += &grid.slice(s![xsource, ysource, zsource]);
    }
    neighbours
}

Unlike on Day 11, the game board is infinite and has no walls. However, also unlike on Day 11 where we had a termination condition for the game, today we have to simulate exactly 6 iterations of the game, so we can actually pretend the board is finite. The occupied cells can expand at by 1 every turn at most, so the board can be bounded at the size of the input board plus the number of iterations in every direction.

In the example given in the puzzle description, the board is 3×3×1 and we simulate 3 iterations, so the maximum board size would be 9×9×7 in the example. (The example’s actual output fits in 7×7×5, but we need an upper bound.)

I’m able to reuse a lot of the code from Day 11, so this should look very familiar if you’ve been following along:

use itertools::Itertools;
use ndarray::{s, Array3};
use std::iter;

fn main() {
    // let input = ".#.\n..#\n###\n";
    let input = include_str!("input");
    let n_turns = 6;
    let mut grid = read_grid(input, n_turns);

    for _ in 0..n_turns {
        let neighbours = calc_neighbours(&grid);
        let activations = &neighbours.mapv(|count| (count == 3) as i16)
            * &grid.mapv(|active| (active == 0) as i16);
        let deactivations = &neighbours.mapv(|count| (count < 2 || count > 3) as i16) * &grid;
        grid = grid + activations - deactivations;
    }

    dump_grid(&grid);
    println!("{}", grid.sum());
}

fn calc_neighbours(grid: &Array3<i16>) -> Array3<i16> {
    let shape = grid.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let depth = shape[2] as isize;
    let mut neighbours = Array3::<i16>::zeros(grid.raw_dim());
    // Add slices of the occupied grid shifted one space in each direction
    for starts in iter::repeat(-1..=1).take(3).multi_cartesian_product() {
        if starts.iter().all(|start| *start == 0) {
            continue;
        }
        let (xstart, ystart, zstart) = (starts[0], starts[1], starts[2]);
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let zdest = zstart.max(0)..(depth + zstart).min(depth);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let zsource = (-zstart).max(0)..(depth - zstart).min(depth);
        let mut slice = neighbours.slice_mut(s![xdest, ydest, zdest]);
        slice += &grid.slice(s![xsource, ysource, zsource]);
    }
    neighbours
}

fn read_grid(input: &str, padding: usize) -> Array3<i16> {
    let lines: Vec<&str> = input.lines().collect();
    let height = lines.len();
    let width = lines[0].len();
    let mut cells = Array3::zeros((width + 2 * padding, height + 2 * padding, 2 * padding + 1));
    for (y, line) in lines.iter().enumerate() {
        for (x, tile) in line.bytes().enumerate() {
            cells[[x + padding, y + padding, padding]] = match tile {
                b'#' => 1,
                b'.' => 0,
                _ => panic!("Bad tile '{}'", tile),
            };
        }
    }
    cells
}

fn dump_grid(grid: &Array3<i16>) {
    for xy in grid.axis_iter(ndarray::Axis(2)) {
        for x in xy.axis_iter(ndarray::Axis(1)) {
            println!(
                "{}",
                x.mapv(|active| if active != 0 { '#' } else { '.' })
                    .iter()
                    .collect::<String>()
            )
        }
        println!("");
    }
}

The main difference is that I’ve written a dump_grid() function as well.

I remarked on Day 11 that in my opinion the ndarray package suffers from a few deficiencies compared to NumPy, and I ran into those same problems today:

• The return value of sum() is limited to the data type of the array it is being called on.
• You can’t easily use boolean arrays as a mask.

Day 17, Part 2

Part 2 of the puzzle is exactly the same as Part 1, only four-dimensional! I briefly wish that I had spent the time on generalizing calc_neighbours() to work with any number of dimensions. But on the other hand, I really don’t feel confident enough with either Rust or ndarray that I could anticipate being able to do that without spending all day on it.

So instead I decide to do the simplest thing: copy the file to another puzzle17-2.rs and add another section to Cargo.toml:

[[bin]]
name = "puzzle17-2"
path = "puzzle17-2.rs"

I notice that you now need to specify which binary to run, which is nice, because I wasn’t sure how I would choose between the two:

error: `cargo run` could not determine which binary to run. Use the `--bin` option to specify a binary, or the `default-run` manifest key.
available binaries: puzzle17, puzzle17-2

Then I just change all the Array3 to Array4 and add an extra index where needed:

use itertools::Itertools;
use ndarray::{s, Array4};
use std::iter;

fn main() {
    let input = include_str!("input");
    let n_turns = 6;
    let mut grid = read_grid(input, n_turns);

    for _ in 0..n_turns {
        let neighbours = calc_neighbours(&grid);
        let activations = &neighbours.mapv(|count| (count == 3) as i16)
            * &grid.mapv(|active| (active == 0) as i16);
        let deactivations = &neighbours.mapv(|count| (count < 2 || count > 3) as i16) * &grid;
        grid = grid + activations - deactivations;
    }

    println!("{}", grid.sum());
}

fn calc_neighbours(grid: &Array4<i16>) -> Array4<i16> {
    let shape = grid.shape();
    let width = shape[0] as isize;
    let height = shape[1] as isize;
    let depth = shape[2] as isize;
    let limit4 = shape[3] as isize;
    let mut neighbours = Array4::<i16>::zeros(grid.raw_dim());
    // Add slices of the occupied grid shifted one space in each direction
    for starts in iter::repeat(-1..=1).take(4).multi_cartesian_product() {
        if starts.iter().all(|start| *start == 0) {
            continue;
        }
        let (xstart, ystart, zstart, wstart) = (starts[0], starts[1], starts[2], starts[3]);
        let xdest = xstart.max(0)..(width + xstart).min(width);
        let ydest = ystart.max(0)..(height + ystart).min(height);
        let zdest = zstart.max(0)..(depth + zstart).min(depth);
        let wdest = wstart.max(0)..(limit4 + wstart).min(limit4);
        let xsource = (-xstart).max(0)..(width - xstart).min(width);
        let ysource = (-ystart).max(0)..(height - ystart).min(height);
        let zsource = (-zstart).max(0)..(depth - zstart).min(depth);
        let wsource = (-wstart).max(0)..(limit4 - wstart).min(limit4);
        let mut slice = neighbours.slice_mut(s![xdest, ydest, zdest, wdest]);
        slice += &grid.slice(s![xsource, ysource, zsource, wsource]);
    }
    neighbours
}

fn read_grid(input: &str, padding: usize) -> Array4<i16> {
    let lines: Vec<&str> = input.lines().collect();
    let height = lines.len();
    let width = lines[0].len();
    let mut cells = Array4::zeros((
        width + 2 * padding,
        height + 2 * padding,
        2 * padding + 1,
        2 * padding + 1,
    ));
    for (y, line) in lines.iter().enumerate() {
        for (x, tile) in line.bytes().enumerate() {
            cells[[x + padding, y + padding, padding, padding]] = match tile {
                b'#' => 1,
                b'.' => 0,
                _ => panic!("Bad tile '{}'", tile),
            };
        }
    }
    cells
}

This gives me the right answer.

Afterword

The puzzles seem to be getting harder as we go along, particularly Day 16 more than Day 17. I am almost certain that Day 16 could be solved much more elegantly than the solution that I had. Day 17, on the other hand, gave me a chance to improve on the solution that I already had for Day 11.

Having the compiler messages directly in my editor is a mixed blessing! It’s definitely streamlined things, but on the other hand I think it has actually made me more lazy and less inclined to learn about when the & operator is necessary — I’ve caught myself just adding them here and there in likely places without bothering to think, and letting the compiler sort the rest out. I’m definitely not this careless with pointers in C!

---

[1] And therefore probably more useful if you actually want to learn Rust yourself ↩

[2] Or more like, the loop was never rolled in the first place because it was too complicated for me to write at the time ↩

Advent of Rust 10: When All You Have is Itertools, Every Problem Looks like an Iter

Welcome back to episode 10 of the previously-stream-of-consciousness-now-abbreviated log of me trying to teach myself the Rust programming language, stumbling my way through the puzzles from Advent of Code 2020.

I have noticed that by now doing a puzzle each day and writing about it is somewhat tiring. I’ve found myself eager to solve the puzzle in the quickest way possible rather than to use each day’s puzzle as an excuse to learn a new language feature in Rust. But on the other hand I think that’s OK! Despite that, I am still enjoying it and looking forward each day to seeing what the new puzzle is.

It’s just fine to want to solve puzzles in a hacky way; once the puzzle is solved, it’s done!

Day 10, Part 1

The first part of the puzzle is to figure out how to chain “joltage” (a made-up kind of voltage?) adapters together. Each adapter is rated for a different number of “jolts” and they all have to be connected in increasing order such that there is no more than a difference of 3 jolts between them, and all the adapters are used. I think this is a roundabout way of describing that the list has to be sorted in ascending numerical order?!

The answer to the puzzle is the number of adapters with 1 jolt difference between them, times the number of adapters with 3 jolts difference between them. This reminds me of Day 5 when I wanted to find which seat number was missing from a list and so looked for the item that did not have a number one higher than its predecessor.

This sounds like a job for … Itertools!

The initial approach of forging ahead and writing the code that I think will work, compiling it until it runs, and then trying the answer on the website, has worked many times so far, so I try it again now. I will sort the input array, add the device’s built-in adapter which is always 3 jolts higher than the highest adapter in the list, calculate the differences between consecutive elements using tuple_windows(), and then count the number of occurrences of each of those differences.

It’s for the latter step that I spend some time browsing the Itertools documentation to see if there is a method that already does this. The closest I come is to sort the vector of differences and then use group_by() on it, helpfully copying the code from the example usage of group_by() in the documentation, and then count the length of each of the groups.

Here’s the code:

let mut adapters: Vec<u8> = read_lines(file).map(|s| s.parse().unwrap()).collect();
adapters.sort_unstable();
adapters.push(adapters.last().unwrap() + 3); // add built-in adapter

let mut differences: Vec<u8> = adapters
    .iter()
    .tuple_windows()
    .map(|(j1, j2)| j2 - j1)
    .collect();
differences.sort_unstable();

let mut occurrences = vec![0, 0, 0];
for (key, group) in &differences.iter().group_by(|d| *d) {
    occurrences[*key as usize - 1] = group.count();
}

println!("{}", occurrences[0] * occurrences[2]);

Clippy helpfully reminds me to use sort_unstable() instead of sort() for u8 which doesn’t need to preserve the order of equal elements, and to use count() instead of the much less readable collect::<Vec<&u8>>().len(). Also, the * operators that you see in the code above were definitely the compiler’s idea, not mine.

I get an answer and put it into the Advent of Code website, and it’s too low. I print out adapters, differences, and occurrences to see if they make sense, and they do, but I notice the problem: I’ve added the built-in adapter on one end, which is 3 jolts higher than the highest one in the list, but I’ve forgotten to add the charging outlet on the other end, which is always rated 0 jolts. I do this (add adapters.push(0); before the sort) and this time get the right answer.

Before going on to Part 2, I look at this code again and think that maybe this is maybe just a tiny a bit too much Itertools, and I’m trying too hard to be clever. I refactor it into this, which still gives me the correct answer but only iterates through the sorted adapters once:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let mut adapters: Vec<u8> = read_lines(file).map(|s| s.parse().unwrap()).collect();
    adapters.push(0); // add charging outlet
    adapters.sort_unstable();
    adapters.push(adapters.last().unwrap() + 3); // add built-in adapter

    let mut ones = 0;
    let mut threes = 0;
    for difference in adapters.iter().tuple_windows().map(|(j1, j2)| j2 - j1) {
        match difference {
            1 => ones += 1,
            3 => threes += 1,
            _ => (),
        }
    }

    println!("{}", ones * threes);
    Ok(())
}

Day 10, Part 2

Part 2 is to figure out the number of possible configurations of adapters with which you can connect the charging outlet to the device. Each adapter must have a higher number than the one before it, but no more than 3 higher.

The way they describe the puzzle, it sounds like brute force is not an option here! I first start thinking of a tree structure, but quickly discard that idea, because if there are trillions of possible configurations, then the tree would need to have trillions of branches.

For quite a long time I stare at the worked example in the puzzle description which has 8 possible configurations, scrolling back and forth between the list of adapters and the list of configurations. In the list of configurations I notice that many of the numbers remain the same because you have only one choice for the adapter that goes there. Looking at all 8 configurations, they all follow this pattern:

0, 1, 4, 5?, 6?, 7, 10, 11?, 12, 15, 16, 19, 22

Only 5, 6 and 11 are optional. Each one may occur or it may not, so that’s 2³ = 8 combinations. And in fact, when you have reached adapter 4 you have 3 choices for the next adapter (5, 6, or 7), when you have reached adapter 10 you have 2 choices for the next adapter (11 or 12), and all the other adapters only have one possible choice for the next adapter. So the number of combinations is the product of 2^{n − 1} for each adapter where n is the number of possible choices for the next adapter.

For a little while I think this is how to get the answer, but then I realize this can’t be true, because according to this formula the answer can only be a power of 2 (since it’s calculated by multiplying powers of 2 together.) The answer to the second worked example, however, is 19280, not a power of 2.

I suppose if you had the sequence 0, 3, 4, 5, 6, 7, 10 then things would be a bit different! (Unlike the first worked example, there are five adapters next to each other in the list with a difference of 1 between them, not four.)

These would be the valid configurations for that sequence:

0, 3, 4, 5, 6, 7, 10
0, 3, 4, 5,    7, 10
0, 3, 4,    6, 7, 10
0, 3, 4,       7, 10
0, 3,    5, 6, 7, 10
0, 3,    5,    7, 10
0, 3,       6, 7, 10

There are 7 of them, clearly not a power of 2. My scheme was thrown off because the number of choices at one adapter can affect the number of choices at another adapter. At 5 you can choose to skip 6, but you can’t skip 6 if you’ve already skipped 4.

I did notice when I debug-printed occurrences in Part 1¹, that there were no differences of 2 in the list. They were all differences of 1 or 3. My hunch is that a difference of 3 “resets” things, since the two numbers on either side of it must always occur. So we can consider each “run” of ones in isolation.

We know from the original worked example (differences of 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 3) that a run of one one yields only one choice, a run of two ones yields two choices (10, 11?, 12), a run of three ones yields four choices (4, 5?, 6?, 7), and now we know from my new example above that a run of four ones yields seven choices.

I check what the valid configurations are for a run of five ones, let’s say 0, 3, 4, 5, 6, 7, 8, 11:

0, 3, 4, 5, 6, 7, 8, 11
0, 3, 4, 5, 6,    8, 11
0, 3, 4, 5,    7, 8, 11
0, 3, 4, 5,       8, 11
0, 3, 4,    6, 7, 8, 11
0, 3, 4,    6,    8, 11
0, 3, 4,       7, 8, 11
0, 3,    5, 6, 7, 8, 11
0, 3,    5, 6,    8, 11
0, 3,    5,    7, 8, 11
0, 3,    5,       8, 11
0, 3,       6, 7, 8, 11
0, 3,       6,    8, 11

There are 13 of them. And a run of six ones, let’s say 0, 3, 4, 5, 6, 7, 8, 9, 12:

0, 3, 4, 5, 6, 7, 8, 9, 12
0, 3, 4, 5, 6, 7,    9, 12
0, 3, 4, 5, 6,    8, 9, 12
0, 3, 4, 5, 6,       9, 12
0, 3, 4, 5,    7, 8, 9, 12
0, 3, 4, 5,    7,    9, 12
0, 3, 4, 5,       8, 9, 12
0, 3, 4,    6, 7, 8, 9, 12
0, 3, 4,    6, 7,    9, 12
0, 3, 4,    6,    8, 9, 12
0, 3, 4,    6,       9, 12
0, 3, 4,       7, 8, 9, 12
0, 3, 4,       7,    9, 12
0, 3,    5, 6, 7, 8, 9, 12
0, 3,    5, 6, 7,    9, 12
0, 3,    5, 6,    8, 9, 12
0, 3,    5, 6,       9, 12
0, 3,    5,    7, 8, 9, 12
0, 3,    5,    7,    9, 12
0, 3,    5,       8, 9, 12
0, 3,       6, 7, 8, 9, 12
0, 3,       6, 7,    9, 12
0, 3,       6,    8, 9, 12
0, 3,       6,       9, 12

Here, there are 24 possible combinations. Each time we start with 2^{n − 1} combinations, but eliminate a few due to having gaps larger than 3.

I don’t really see a pattern in the number of choices that have to be eliminated because of gaps larger than 3:

run length	choices
1	20 = 1
2	21 = 2
3	22 = 4
4	23 − 1 = 7
5	24 − 3 = 13
6	25 − 8 = 24
7	26 − 20 = 44
8	27 − 47 = 81

I do notice that any combinations eliminated in one row are also eliminated in all subsequent rows, so maybe it could be defined recursively in terms of doubling the previous entry and removing some more rows:

run length n	choices f(n)
1	1 = 1
2	2 × f(1) = 2
3	2 × f(2) = 4
4	2 × f(3) − 1 = 7
5	2 × f(4) − 1 = 13
6	2 × f(5) − 2 = 24
7	2 × f(6) − 4 = 44
8	2 x f(7) − 7 = 81

This is starting to make sense. When I write out the combinations in order to count the rows, the number of rows I have to remove each time consists of a pattern from one of the earlier entries but with three missing adapters in front of it. (I’m not sure if this is a good way to explain it, but maybe more visually: to get from the combinations for five ones to the combinations for six ones that I wrote out above, I add one to all the numbers except zero, insert a column of threes, copy all the lines and paste them below the existing lines, delete the threes from the newly-pasted lines, and then delete the last two rows since they start with 0, 3, 7 which is not allowed. The number of rows that I delete at the end corresponds to the number of rows in an earlier iteration of the pattern.) I predict that a run of nine ones is going to produce 149 choices, or 2 × 81 − 13, and when I write them out to make sure, that turns out to be correct: so I’m guessing that for larger n, f(n) = 2 × f(n − 1) − f(n − 4).

This is by no means a mathematical-level rigorous proof, but I have a working hypothesis that successfully predicted the next result, which is good enough for me to start coding. If this were not a one-off puzzle I would start by verifying the worked examples in the puzzle description, but I will just write the code and see if the first answer I get is correct.

I then laugh out loud as I realize that the totally unnecessary use of group_by() in Part 1 is actually a good way to implement Part 2.

let differences = adapters.iter().tuple_windows().map(|(j1, j2)| j2 - j1);
let groups = differences.group_by(|d| *d);
let total: u64 = groups
    .into_iter()
    .filter(|(key, _)| *key == 1)
    .map(|(_, group)| possible_configurations(group.count()))
    .product();
println!("{}", total);

// ...

fn possible_configurations(run_length: usize) -> u64 {
    match run_length {
        n if n < 1 => panic!("Bad value"),
        1 => 1,
        2 => 2,
        3 => 4,
        4 => 7,
        n => 2 * possible_configurations(n - 1) - possible_configurations(n - 4),
    }
}

I stumble over the return value of group_by() not being an iterator, and not having an iter() method like Vec but instead an into_iter() method. And as in Part 1, the *s are all the compiler’s idea.

Running this gives me the correct answer.

Afterword

I am now curious whether all the trouble I went to, to figure out the number of configurations for long runs of adapters with differences of 1 between them, was actually necessary. With a debug print I find that it wasn’t: the longest run of ones in the input is four. (And in hindsight I can tell that the n => line was never reached, because I initially forgot to multiply it by 2, but still got the correct answer!) I guess the lesson here is, when doing programming puzzles, check the input first, and see if you can get away with not handling cases that aren’t present!

That makes two paths that I took, and spent a lot of time on, that weren’t wrong as such, but were unnecessary. (The second one being, all the time I spent in Part 1 looking for an Itertools method that would count the occurrences in differences even though I knew how to write it with a simple for loop.) Both of them were caused by trying to be too clever. I should learn that for these Advent of Code puzzles, a clever solution doesn’t matter, it only matters that it’s correct! I should have taken my own advice that I wrote in the introduction to this blog post.

I also notice that today’s episode has been much more about figuring out what code to write, than about learning Rust. Once I had figured that out, I wrote the code, added whatever & or * operators the compiler told me to, and for the most part it worked.

I still wish I would understand enough to get the & and * operators right the first time. I suspect that if I set up my editor to show Rust types when hovering over an identifier, or something like that, then I’d be more aware of where I was working with a borrowed type, and be able to write the code accordingly.

---

[1] Debug printing is good for something, after all ↩