/
day07.rs
111 lines (85 loc) · 2.43 KB
/
day07.rs
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
use std::io::Read;
use itertools::Itertools;
use crate::common::ordered;
fn read_input(input: &mut dyn Read) -> Vec<usize> {
let mut buf = String::new();
input.read_to_string(&mut buf).unwrap();
let mut crabs: Vec<usize> = buf
.trim_end()
.split(',')
.map(|s| s.parse().unwrap())
.collect();
crabs.sort_unstable();
crabs
}
fn cost_at(pos: usize, crabs: &[usize]) -> usize {
crabs
.iter()
.map(|&crab_pos| {
if crab_pos > pos {
crab_pos - pos
} else {
pos - crab_pos
}
})
.sum()
}
pub fn part1(input: &mut dyn Read) -> String {
let crabs = read_input(input);
let median = crabs[crabs.len() / 2 + (crabs.len() % 2)];
cost_at(median, &crabs).to_string()
}
pub fn sum_until(end: usize) -> usize {
(end * (1 + end)) / 2
}
fn cost_at2(pos: usize, groups: &[(usize, usize)]) -> usize {
groups
.iter()
.map(|&(number, new_pos)| {
let (first, last) = ordered(pos, new_pos);
number * sum_until(last - first)
})
.sum()
}
fn ternary_search(mut min: usize, mut max: usize, callback: impl Fn(usize) -> usize) -> usize {
while max - min > 6 {
let mid1 = min + (max - min) / 3;
let mid2 = max - (max - min) / 3;
let cost1 = callback(mid1);
let cost2 = callback(mid2);
if cost1 < cost2 {
max = mid2 - 1
} else {
min = mid1 + 1
}
}
// Ternary search isn't effective at such small intervals so we iterate the remaining part
(min..=max).map(callback).min().unwrap()
}
pub fn part2(input: &mut dyn Read) -> String {
let groups: Vec<_> = read_input(input).into_iter().dedup_with_count().collect();
let min = groups.first().unwrap().1;
let max = groups.last().unwrap().1;
ternary_search(min, max, |pos| cost_at2(pos, &groups)).to_string()
}
#[cfg(test)]
mod tests {
use crate::test_implementation;
use super::*;
const SAMPLE: &[u8] = &*b"16,1,2,0,4,2,7,1,2,14";
#[test]
fn sample_part1() {
test_implementation(part1, SAMPLE, 37);
}
#[test]
fn sample_part2() {
test_implementation(part2, SAMPLE, 168);
}
#[test]
fn test_maths() {
assert_eq!(sum_until(1), 1);
assert_eq!(sum_until(2), 3);
assert_eq!(sum_until(3), 6);
assert_eq!(sum_until(4), 10);
}
}