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 mut left = i64::MAX;
38        let mut right = i64::MIN;
39
40        for x in 0..50 {
41            if precheck(input, x, y) && test(code, x, y) {
42                left = x;
43                break;
44            }
45        }
46        for x in (0..50).rev() {
47            if precheck(input, x, y) && test(code, x, y) {
48                right = x;
49                break;
50            }
51        }
52        if left <= right {
53            result += right - left + 1;
54        }
55    }
56
57    result
58}
59
60pub fn part2(input: &Input) -> i64 {
61    let code = &input.code;
62    let mut x = 0;
63    let mut y = 0;
64    let mut moved = true;
65
66    // Increase the right and bottom edges of our box until they are both inside the beam.
67    while moved {
68        moved = false;
69
70        while !precheck(input, x, y + 99) || !test(code, x, y + 99) {
71            x += 1;
72            moved = true;
73        }
74
75        while !precheck(input, x + 99, y) || !test(code, x + 99, y) {
76            y += 1;
77            moved = true;
78        }
79    }
80
81    10000 * x + y
82}
83
84/// Quick check with some false positives but no false negatives.
85fn precheck(input: &Input, x: i64, y: i64) -> bool {
86    50 * y > input.upper * x && 50 * x > input.lower * y
87}
88
89/// Definitive but slower check.
90fn test(code: &[i64], x: i64, y: i64) -> bool {
91    let mut computer = Computer::new(code);
92    computer.input(x);
93    computer.input(y);
94
95    let State::Output(result) = computer.run() else { unreachable!() };
96    result == 1
97}
aoc/year2019/day19.rs

aoc/year2019/
day19.rs
