aoc/year2021/
day07.rs

1//! # The Treachery of Whales
2//!
3//! Part 1 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.
5//!
6//! Part 2 is found by using the [mean](https://en.wikipedia.org/wiki/Mean).
7//! However since this could a floating point value and we are using integers we need to check
8//! 3 values total, the rounded result and one value on either side to ensure the correct answer.
9use crate::util::parse::*;
10
11pub fn parse(input: &str) -> Vec<i32> {
12    input.iter_signed().collect()
13}
14
15pub fn part1(input: &[i32]) -> i32 {
16    let median = median(input);
17    input.iter().map(|n| (n - median).abs()).sum()
18}
19
20pub fn part2(input: &[i32]) -> i32 {
21    let mean = mean(input);
22    let triangle = |x: i32, mean: i32| {
23        let n = (x - mean).abs();
24        (n * (n + 1)) / 2
25    };
26
27    (-1..=1).map(|delta| input.iter().map(|&x| triangle(x, mean + delta)).sum()).min().unwrap()
28}
29
30fn median(input: &[i32]) -> i32 {
31    let mut crabs = input.to_vec();
32    crabs.sort_unstable();
33
34    let half = input.len() / 2;
35    if crabs.len().is_multiple_of(2) { crabs[half - 1].midpoint(crabs[half]) } else { crabs[half] }
36}
37
38fn mean(input: &[i32]) -> i32 {
39    let sum: i32 = input.iter().sum();
40    sum / (input.len() as i32)
41}
aoc/year2021/day07.rs

aoc/year2021/
day07.rs
