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 23 = 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 2n − 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 11, 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 2n − 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 lengthchoices
120 = 1
221 = 2
322 = 4
423 − 1 = 7
524 − 3 = 13
625 − 8 = 24
726 − 20 = 44
827 − 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 nchoices f(n)
11 = 1
22 × f(1) = 2
32 × f(2) = 4
42 × f(3) − 1 = 7
52 × f(4) − 1 = 13
62 × f(5) − 2 = 24
72 × f(6) − 4 = 44
82 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

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

  1. Pingback: Advent of Rust 13: Lucky Numbers | The Mad Scientist Review

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.