️🎄 Advent of Code 2021, Day 7

The Treachers of Whales

2022-08-27

#rust #advent-of-code

Day 7: The Treachery of Whales

While I've completed every star for each year of Advent of Code, I recently realised I hadn't written up my notes from some of the days from last year. Taking the opportunity to revisit my efforts, here's the first missing day from 2021, along with some obvervations as to where I fundamentally misunderstood the input data.

Part One

This is not an auspicious start: looking back at this from the far future of 2022, I'm not actually sure that I did this correctly (or at least not efficiently.)

Parsing the input is straightforward enough (note we're using isize as we'll be doing some subtracting later and this makes it much simpler; similarly, I opted to use a flat_map() which will drop any Err which come from failed parsing, a bad practice I'll likely revisit in the future):

fn get_positions(input: &str) -> Vec<isize> {
    input
        .trim()
        .split(',')
        .flat_map(|pos| pos.parse::<isize>())
        .collect()
}

This was the solution I came up with for Part One:

pub fn get_part_one(input: &str) -> isize {
    let positions = get_positions(input);

    (0..positions.len())
        .map(|alignment| {
            positions
                .iter()
                .map(|position| (position - alignment as isize).abs())
                .sum()
        })
        .min()
        .unwrap()
}

While this worked, there are (at least) two things wrong with it:

• I'm looping over the input and then determining the fuel consumption for each other position. However, even in the example given there are duplicates so the outer loop will repeat unecessarily.
• I'm not even looping over the right thing! I'm looping over the input's length, not the actual values therein: it's pure coincidence that all the positions listed therein actually fall in that range.

Assuming that that initial loop is instead positions.map(…, there are 1,000 crabs coming to aid us but only 667 unique positions so there are definitely efficiencies to be made.

Part Two

There's one further assumption I made in the first part that doesn't hold true here: that the correct position is actually represented in the input.

Take the input of 16,1,2,0,4,2,7,1,2,14: the answer is 5 which is not present in that list. Instead, the range of positions should be from the minimum up to the maximum value represented in that list (I think we can safely assume that moving the crabs outside of that range would take more fuel than moving within that range.)

It's more verbose but instead I should have something more like:

    let min = positions.iter().min().unwrap();
    let max = positions.iter().max().unwrap();
    (*min..=*max)
        .map(…

Here I originally did the calculation of the fuel consumption via this (diff being the distance moved):

(diff * (diff + 1)) / 2

However, now looking at it, I'm not ever sure I understand it at first glance (though thankfully I left myself a note about this being a Arithmetic progression.) Instead, I could have opted to do this:

(0..=diff).sum()

That (now, at least) makes more sense to me: the fuel consumed is the sum of the range between the two (i.e. 1 + 2 + 3, etc.)

Furthermore, I don't even need that sum(): I don't care about the sum of each individual crab's movements, just the sum of all the crabs' movements:

.flat_map(|position| {
    let diff = (position - alignment).abs();
    0..=diff
})
.sum()

So my final solution for the second part ends up being:

pub fn get_part_two(input: &str) -> isize {
    let positions = get_positions(input);

    let min = positions.iter().min().unwrap();
    let max = positions.iter().max().unwrap();
    (*min..=*max)
        .map(|alignment| {
            positions
                .iter()
                .flat_map(|position| {
                    0..=(position - alignment).abs()
                })
                .sum()
        })
        .min()
        .unwrap()
}

Curiously, the cargo run for Part Two takes an extraordinarily long time (to the point I lose patience waiting for it to finish); using cargo run --release, however, is single-digit milliseconds. I'm aware of the differences between the two, the extent of the difference for such a seemingly straightforward problem is surprising.