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

aoc/year2019/
day12.rs
