-
Notifications
You must be signed in to change notification settings - Fork 9
/
day12.rs
94 lines (79 loc) · 2.5 KB
/
day12.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
//! # The N-Body Problem
//!
//! There are two insights needed to solve part two:
//!
//! * Each axis is independent
//! * Each axis is periodic somewhat like
//! [simple harmonic motion](https://en.wikipedia.org/wiki/Simple_harmonic_motion).
//! The velocity returns to zero twice per period.
//!
//! First find the period of each axis, then the answer is the
//! [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of all three
//! combined.
//!
//! The [`signum`] function comes in handy when updating the velocity.
//!
//! [`signum`]: i32::signum
use crate::util::math::*;
use crate::util::parse::*;
type Axis = [i32; 8];
type Input = [Axis; 3];
/// Group each axis together
pub fn parse(input: &str) -> Input {
let n: Vec<_> = input.iter_signed().collect();
[
[n[0], n[3], n[6], n[9], 0, 0, 0, 0],
[n[1], n[4], n[7], n[10], 0, 0, 0, 0],
[n[2], n[5], n[8], n[11], 0, 0, 0, 0],
]
}
pub fn part1(input: &Input) -> i32 {
let [mut x, mut y, mut z] = *input;
for _ in 0..1000 {
x = step(x);
y = step(y);
z = step(z);
}
let e: Vec<_> = (0..8).map(|i| x[i].abs() + y[i].abs() + z[i].abs()).collect();
e[0] * e[4] + e[1] * e[5] + e[2] * e[6] + e[3] * e[7]
}
pub fn part2(input: &Input) -> usize {
let [mut x, mut y, mut z] = *input;
let [mut a, mut b, mut c] = [0, 0, 0];
let mut count = 0;
while a == 0 || b == 0 || c == 0 {
count += 1;
if a == 0 {
x = step(x);
if stopped(x) {
a = count;
}
}
if b == 0 {
y = step(y);
if stopped(y) {
b = count;
}
}
if c == 0 {
z = step(z);
if stopped(z) {
c = count;
}
}
}
// a, b and c are the half period, so multiply by 2 to get final result.
2 * a.lcm(b.lcm(c))
}
fn step(axis: Axis) -> Axis {
// "p" is position and "v" velocity
let [p0, p1, p2, p3, v0, v1, v2, v3] = axis;
let n0 = v0 + (p1 - p0).signum() + (p2 - p0).signum() + (p3 - p0).signum();
let n1 = v1 + (p0 - p1).signum() + (p2 - p1).signum() + (p3 - p1).signum();
let n2 = v2 + (p0 - p2).signum() + (p1 - p2).signum() + (p3 - p2).signum();
let n3 = v3 + (p0 - p3).signum() + (p1 - p3).signum() + (p2 - p3).signum();
[p0 + n0, p1 + n1, p2 + n2, p3 + n3, n0, n1, n2, n3]
}
fn stopped(axis: Axis) -> bool {
axis[4] == 0 && axis[5] == 0 && axis[6] == 0 && axis[7] == 0
}