aoc/year2021/
day07.rs

1//! # The Treachery of Whales
2//!
3//! Part one is a disguised definition of the mathematical [median](https://en.wikipedia.org/wiki/Median).
4//! We can calculate the result immediately using the standard algorithm. Even though there
5//! are an even number of crabs, any integer between the 500th and 501st crab inclusive will
6//! work (the extra fuel spent by half the crabs perfectly cancels the fuel saved by the other
7//! half, when switching between integers in that range).
8//!
9//! Part two is found by using the [mean](https://en.wikipedia.org/wiki/Mean).
10//! However, since this could be a floating point value and we are using integers we need to check
11//! both the floor and the ceiling of that result to ensure the correct answer.
12use crate::util::parse::*;
13
14pub fn parse(input: &str) -> Vec<i32> {
15    input.iter_signed().collect()
16}
17
18pub fn part1(input: &[i32]) -> i32 {
19    let median = median(input);
20    input.iter().map(|n| (n - median).abs()).sum()
21}
22
23pub fn part2(input: &[i32]) -> i32 {
24    let fuel = |target: i32| -> i32 {
25        input
26            .iter()
27            .map(|x| {
28                let n = (x - target).abs();
29                (n * (n + 1)) / 2
30            })
31            .sum()
32    };
33
34    let mean = mean(input);
35    fuel(mean).min(fuel(mean + 1))
36}
37
38fn median(input: &[i32]) -> i32 {
39    // A radix sort followed by a short-circuiting .position() would also work, but takes
40    // more lines of code without much more speed.
41    let mut crabs = input.to_vec();
42    let middle = crabs.len() / 2;
43    *crabs.select_nth_unstable(middle).1
44}
45
46fn mean(input: &[i32]) -> i32 {
47    input.iter().sum::<i32>() / (input.len() as i32)
48}
aoc/year2021/day07.rs

aoc/year2021/
day07.rs
