aoc/year2019/
day19.rs

1//! # Tractor Beam
2//!
3//! The intcode program computes a linear inequality: returning true if an integer point lies on
4//! or between two lines through the origin, often with irrational slope. The intcode program was
5//! designed so that the two lines are close enough that there are no integer solutions when `y=1`,
6//! so there are intentionally one or two discontinuities between the origin and the bulk of the
7//! beam. This solution finds the approximate boundary of the upper and lower edges of the beam
8//! expressed as an integer ratio for slope. We then skip the relatively expensive intcode test if
9//! the x and y coordinates lie outside. Once we identify an edge past the initial discontinuities,
10//! scaling along the lines buys more accuracy and thus fewer later intcode runs.
11//!
12//! For part 2, we can further speed up the process by using geometry to hone in on a viable
13//! target to start searching at. Our target point `(x,y)` is related to our two slopes as:
14//! ```none
15//!   scale*y = upper*(x+99)
16//!   scale*x = lower*(y+99)
17//! ```
18//! Those two equations can be represented in matrix form:
19//! ```none
20//!   [upper-scale][x] = [-99*upper]
21//!   [scale-lower][y] = [ 99*lower]
22//! ```
23//! where inverting the matrix gives a solution:
24//! ```none
25//!   determinant = scale * scale - lower * upper
26//!   x = 99 * (lower * upper + lower * scale) / determinant
27//!   y = 99 * (lower * upper + upper * scale) / determinant
28//! ```
29use super::intcode::*;
30use crate::util::parse::*;
31
32pub struct Input {
33    code: Vec<i64>,
34    scale: i64,
35    lower: i64, // The slope scale/lower just outside left boundary.
36    upper: i64, // The slope upper/scale just outside right boundary.
37}
38
39pub fn parse(input: &str) -> Input {
40    // Pick an initial scale large enough to be past the discontinuities for all known inputs.
41    let code: Vec<_> = input.iter_signed().collect();
42    let mut lower = 1;
43    let mut upper = 1;
44    let mut scale = 5;
45
46    // Find approximate slope of lower and upper edges, rounding down to prevent false negatives.
47    // Each scaling iteration adds another bit of accuracy to our approximation.
48    while scale < 1024 {
49        scale *= 2;
50        lower *= 2;
51        upper *= 2;
52        while !test(&code, lower + 1, scale) {
53            lower += 1;
54        }
55        while !test(&code, scale, upper + 1) {
56            upper += 1;
57        }
58    }
59
60    Input { code, scale, lower, upper }
61}
62
63pub fn part1(input: &Input) -> i64 {
64    // The origin is always set, but no other point occurs on that row or column.
65    let mut result = 1;
66
67    // Scan all remaining points; this works even on lines with no integer hits.
68    for y in 1..50 {
69        let left = (1..50).find(|&x| inside(input, x, y));
70        let right = (left.unwrap_or(50)..50).rfind(|&x| inside(input, x, y));
71        if let Some((left, right)) = left.zip(right) {
72            result += right - left + 1;
73        }
74    }
75
76    result
77}
78
79pub fn part2(input: &Input) -> i64 {
80    // See comments above about derivation of initial guess for x and y.
81    let determinant = input.scale * input.scale - input.lower * input.upper;
82    let mut x = 99 * (input.lower * input.upper + input.lower * input.scale) / determinant;
83    let mut y = 99 * (input.lower * input.upper + input.upper * input.scale) / determinant;
84    let mut moved = true;
85
86    // Increase the right and bottom edges of our box until they are both inside the beam.
87    while moved {
88        moved = false;
89
90        while !inside(input, x, y + 99) {
91            x += 1;
92            moved = true;
93        }
94
95        while !inside(input, x + 99, y) {
96            y += 1;
97            moved = true;
98        }
99    }
100
101    10000 * x + y
102}
103
104/// Skip the relatively expensive intcode test if the point lies outside the beam's slopes.
105/// The slope check has some false positives but no false negatives.
106fn inside(input: &Input, x: i64, y: i64) -> bool {
107    input.scale * y > input.upper * x
108        && input.scale * x > input.lower * y
109        && test(&input.code, x, y)
110}
111
112/// Definitive but slower check.
113fn test(code: &[i64], x: i64, y: i64) -> bool {
114    let mut computer = Computer::new(code);
115    computer.input(x);
116    computer.input(y);
117
118    let State::Output(result) = computer.run() else { unreachable!() };
119    result == 1
120}
aoc/year2019/day19.rs

aoc/year2019/
day19.rs
