summaryrefslogtreecommitdiff
path: root/src/bin/day_7.rs
blob: b568e07089c511f2dc2e0b39cc4ebe4804b1ac59 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
use nom::{
    bytes::complete::tag, character::complete::u64 as nom_u64, combinator::map,
    multi::separated_list1, IResult,
};
use std::fs;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_7.txt")?;
    let crabs = parse_swarm(&input).unwrap().1;
    dbg!(crabs.linear_min_fuel_sum());
    dbg!(crabs.exponential_min_fuel_sum());
    Ok(())
}

#[derive(
    Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, derive_more::Add, derive_more::Sum,
)]
struct Fuel(u64);

#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct CrabPosition(u64);

impl CrabPosition {
    fn linear_fuel(&self, rhs: &Self) -> Fuel {
        if self > rhs {
            Fuel(self.0 - rhs.0)
        } else {
            Fuel(rhs.0 - self.0)
        }
    }

    fn exponential_fuel(&self, rhs: &Self) -> Fuel {
        let linear_difference = if self > rhs {
            self.0 - rhs.0
        } else {
            rhs.0 - self.0
        };
        Fuel(linear_difference * (linear_difference + 1) / 2)
    }
}

#[derive(Default, Debug)]
struct CrabSwarm {
    crabs: Vec<CrabPosition>,
}

impl CrabSwarm {
    fn new(mut crabs: Vec<CrabPosition>) -> CrabSwarm {
        crabs.sort();
        CrabSwarm { crabs }
    }

    fn linear_min_fuel_sum(&self) -> (CrabPosition, Fuel) {
        (self.crabs[0].0..self.crabs[self.crabs.len() - 1].0)
            .map(CrabPosition)
            .map(|pos| {
                (
                    pos,
                    self.crabs.iter().map(|crab| crab.linear_fuel(&pos)).sum(),
                )
            })
            .min_by_key(|(_pos, fuel)| *fuel)
            .expect("Expected at least one crab")
    }

    fn exponential_min_fuel_sum(&self) -> (CrabPosition, Fuel) {
        (self.crabs[0].0..self.crabs[self.crabs.len() - 1].0)
            .map(CrabPosition)
            .map(|pos| {
                (
                    pos,
                    self.crabs
                        .iter()
                        .map(|crab| crab.exponential_fuel(&pos))
                        .sum(),
                )
            })
            .min_by_key(|(_pos, fuel)| *fuel)
            .expect("Expected at least one crab")
    }
}

fn parse_swarm(input: &str) -> IResult<&str, CrabSwarm> {
    map(
        separated_list1(tag(","), map(nom_u64, CrabPosition)),
        CrabSwarm::new,
    )(input)
}