aoc/year2019/
day12.rs

1//! # The N-Body Problem
2//!
3//! There are two insights needed to solve part two:
4//!
5//! * Each axis is independent
6//! * Each axis is periodic somewhat like
7//!   [simple harmonic motion](https://en.wikipedia.org/wiki/Simple_harmonic_motion).
8//!   The velocity returns to zero twice per period.
9//!
10//! First find the period of each axis, then the answer is the
11//! [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of all three
12//! combined.
13//!
14//! The [`signum`] function comes in handy when updating the velocity.
15//!
16//! [`signum`]: i32::signum
17use crate::util::math::*;
18use crate::util::parse::*;
19
20type Axis = [i32; 8];
21type Input = [Axis; 3];
22
23/// Group each axis together
24pub fn parse(input: &str) -> Input {
25    let n: Vec<_> = input.iter_signed().collect();
26    [
27        [n[0], n[3], n[6], n[9], 0, 0, 0, 0],
28        [n[1], n[4], n[7], n[10], 0, 0, 0, 0],
29        [n[2], n[5], n[8], n[11], 0, 0, 0, 0],
30    ]
31}
32
33pub fn part1(input: &Input) -> i32 {
34    let [mut x, mut y, mut z] = *input;
35
36    for _ in 0..1000 {
37        x = step(x);
38        y = step(y);
39        z = step(z);
40    }
41
42    let e: Vec<_> = (0..8).map(|i| x[i].abs() + y[i].abs() + z[i].abs()).collect();
43    e[0] * e[4] + e[1] * e[5] + e[2] * e[6] + e[3] * e[7]
44}
45
46pub fn part2(input: &Input) -> usize {
47    let [mut x, mut y, mut z] = *input;
48    let [mut a, mut b, mut c] = [0, 0, 0];
49    let mut count = 0;
50
51    while a == 0 || b == 0 || c == 0 {
52        count += 1;
53
54        if a == 0 {
55            x = step(x);
56            if stopped(x) {
57                a = count;
58            }
59        }
60
61        if b == 0 {
62            y = step(y);
63            if stopped(y) {
64                b = count;
65            }
66        }
67
68        if c == 0 {
69            z = step(z);
70            if stopped(z) {
71                c = count;
72            }
73        }
74    }
75
76    // a, b and c are the half period, so multiply by 2 to get final result.
77    2 * a.lcm(b.lcm(c))
78}
79
80fn step(axis: Axis) -> Axis {
81    // "p" is position and "v" velocity
82    let [p0, p1, p2, p3, v0, v1, v2, v3] = axis;
83
84    let n0 = v0 + (p1 - p0).signum() + (p2 - p0).signum() + (p3 - p0).signum();
85    let n1 = v1 + (p0 - p1).signum() + (p2 - p1).signum() + (p3 - p1).signum();
86    let n2 = v2 + (p0 - p2).signum() + (p1 - p2).signum() + (p3 - p2).signum();
87    let n3 = v3 + (p0 - p3).signum() + (p1 - p3).signum() + (p2 - p3).signum();
88
89    [p0 + n0, p1 + n1, p2 + n2, p3 + n3, n0, n1, n2, n3]
90}
91
92fn stopped(axis: Axis) -> bool {
93    axis[4] == 0 && axis[5] == 0 && axis[6] == 0 && axis[7] == 0
94}
aoc/year2019/day12.rs

aoc/year2019/
day12.rs
