aoc/year2019/
day19.rs

1//! # Tractor Beam
2//!
3//! Finds the approximate boundary of the upper and lower edges of the beam expressed as a slope.
4//! We then skip the relatively expensive intcode test if the x and y coordinates lie outside.
5use super::intcode::*;
6use crate::util::parse::*;
7
8pub struct Input {
9    code: Vec<i64>,
10    lower: i64,
11    upper: i64,
12}
13
14pub fn parse(input: &str) -> Input {
15    let code: Vec<_> = input.iter_signed().collect();
16    let mut lower = 0;
17    let mut upper = 0;
18
19    // Find slope of lower and upper edges, rounding down to prevent false negatives.
20    while !test(&code, lower + 1, 50) {
21        lower += 1;
22    }
23    while !test(&code, 50, upper + 1) {
24        upper += 1;
25    }
26
27    Input { code, lower, upper }
28}
29
30pub fn part1(input: &Input) -> i64 {
31    let code = &input.code;
32    // Handle origin specially.
33    let mut result = test(code, 0, 0) as i64;
34
35    // The beam is continuous so we only need to find the left and right edges.
36    for y in 0..50 {
37        let left = (0..50).find(|&x| precheck(input, x, y) && test(code, x, y));
38        let right = (0..50).rfind(|&x| precheck(input, x, y) && test(code, x, y));
39        if let (Some(l), Some(r)) = (left, right) {
40            result += r - l + 1;
41        }
42    }
43
44    result
45}
46
47pub fn part2(input: &Input) -> i64 {
48    let code = &input.code;
49    let mut x = 0;
50    let mut y = 0;
51    let mut moved = true;
52
53    // Increase the right and bottom edges of our box until they are both inside the beam.
54    while moved {
55        moved = false;
56
57        while !precheck(input, x, y + 99) || !test(code, x, y + 99) {
58            x += 1;
59            moved = true;
60        }
61
62        while !precheck(input, x + 99, y) || !test(code, x + 99, y) {
63            y += 1;
64            moved = true;
65        }
66    }
67
68    10000 * x + y
69}
70
71/// Quick check with some false positives but no false negatives.
72fn precheck(input: &Input, x: i64, y: i64) -> bool {
73    50 * y > input.upper * x && 50 * x > input.lower * y
74}
75
76/// Definitive but slower check.
77fn test(code: &[i64], x: i64, y: i64) -> bool {
78    let mut computer = Computer::new(code);
79    computer.input(x);
80    computer.input(y);
81
82    let State::Output(result) = computer.run() else { unreachable!() };
83    result == 1
84}
aoc/year2019/day19.rs

aoc/year2019/
day19.rs
