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::*;
19use std::array::from_fn;
20
21type Axis = [i32; 8];
22type Input = [Axis; 3];
23
24/// Group each axis together.
25pub fn parse(input: &str) -> Input {
26    let n: Vec<_> = input.iter_signed().collect();
27    from_fn(|i| [n[i], n[i + 3], n[i + 6], n[i + 9], 0, 0, 0, 0])
28}
29
30pub fn part1(input: &Input) -> i32 {
31    let [mut x, mut y, mut z] = *input;
32
33    for _ in 0..1000 {
34        x = step(x);
35        y = step(y);
36        z = step(z);
37    }
38
39    let [p0, p1, p2, p3, v0, v1, v2, v3] = from_fn(|i| x[i].abs() + y[i].abs() + z[i].abs());
40    p0 * v0 + p1 * v1 + p2 * v2 + p3 * v3
41}
42
43pub fn part2(input: &Input) -> usize {
44    let [mut x, mut y, mut z] = *input;
45    let [mut a, mut b, mut c] = [0, 0, 0];
46    let mut count = 0;
47
48    while a * b * c == 0 {
49        count += 1;
50
51        if a == 0 {
52            x = step(x);
53            if stopped(x) {
54                a = count;
55            }
56        }
57
58        if b == 0 {
59            y = step(y);
60            if stopped(y) {
61                b = count;
62            }
63        }
64
65        if c == 0 {
66            z = step(z);
67            if stopped(z) {
68                c = count;
69            }
70        }
71    }
72
73    // a, b and c are the half period, so multiply by 2 to get final result.
74    2 * a.lcm(b.lcm(c))
75}
76
77fn step(axis: Axis) -> Axis {
78    // "p" is position and "v" velocity.
79    let [p0, p1, p2, p3, v0, v1, v2, v3] = axis;
80
81    let a = (p1 - p0).signum();
82    let b = (p2 - p0).signum();
83    let c = (p3 - p0).signum();
84    let d = (p2 - p1).signum();
85    let e = (p3 - p1).signum();
86    let f = (p3 - p2).signum();
87
88    let n0 = v0 + a + b + c;
89    let n1 = v1 - a + d + e;
90    let n2 = v2 - b - d + f;
91    let n3 = v3 - c - e - f;
92
93    [p0 + n0, p1 + n1, p2 + n2, p3 + n3, n0, n1, n2, n3]
94}
95
96fn stopped(axis: Axis) -> bool {
97    axis[4] == 0 && axis[5] == 0 && axis[6] == 0 && axis[7] == 0
98}
aoc/year2019/day12.rs

aoc/year2019/
day12.rs
