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    let update = |axis: &mut Axis, period: &mut usize, count: usize| {
49        if *period == 0 {
50            *axis = step(*axis);
51            if stopped(*axis) {
52                *period = count;
53            }
54        }
55    };
56
57    while a * b * c == 0 {
58        count += 1;
59        update(&mut x, &mut a, count);
60        update(&mut y, &mut b, count);
61        update(&mut z, &mut c, count);
62    }
63
64    // a, b and c are the half period, so multiply by 2 to get final result.
65    2 * a.lcm(b.lcm(c))
66}
67
68fn step(axis: Axis) -> Axis {
69    // "p" is position and "v" velocity.
70    let [p0, p1, p2, p3, v0, v1, v2, v3] = axis;
71
72    let a = (p1 - p0).signum();
73    let b = (p2 - p0).signum();
74    let c = (p3 - p0).signum();
75    let d = (p2 - p1).signum();
76    let e = (p3 - p1).signum();
77    let f = (p3 - p2).signum();
78
79    let n0 = v0 + a + b + c;
80    let n1 = v1 - a + d + e;
81    let n2 = v2 - b - d + f;
82    let n3 = v3 - c - e - f;
83
84    [p0 + n0, p1 + n1, p2 + n2, p3 + n3, n0, n1, n2, n3]
85}
86
87fn stopped(axis: Axis) -> bool {
88    axis[4] == 0 && axis[5] == 0 && axis[6] == 0 && axis[7] == 0
89}
aoc/year2019/day12.rs

aoc/year2019/
day12.rs
