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)
}
|
