1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

//! # Tractor Beam
//!
//! Finds the approximate boundary of the upper and lower edges of the beam expressed as a slope.
//! We then skip the relatively expensive intcode test if the x and y coordinates lie outside.
use super::intcode::*;
use crate::util::parse::*;

pub struct Input {
    code: Vec<i64>,
    lower: i64,
    upper: i64,
}

pub fn parse(input: &str) -> Input {
    let code: Vec<_> = input.iter_signed().collect();
    let mut lower = 0;
    let mut upper = 0;

    // Find slope of lower and upper edges, rounding down to prevent false negatives.
    while !test(&code, lower + 1, 50) {
        lower += 1;
    }
    while !test(&code, 50, upper + 1) {
        upper += 1;
    }

    Input { code, lower, upper }
}

pub fn part1(input: &Input) -> i64 {
    let code = &input.code;
    // Handle origin specially
    let mut result = test(code, 0, 0) as i64;

    // The beam is continuous so we only need to find the left and right edges.
    for y in 0..50 {
        let mut left = i64::MAX;
        let mut right = i64::MIN;

        for x in 0..50 {
            if precheck(input, x, y) && test(code, x, y) {
                left = x;
                break;
            }
        }
        for x in (0..50).rev() {
            if precheck(input, x, y) && test(code, x, y) {
                right = x;
                break;
            }
        }
        if left <= right {
            result += right - left + 1;
        }
    }

    result
}

pub fn part2(input: &Input) -> i64 {
    let code = &input.code;
    let mut x = 0;
    let mut y = 0;
    let mut moved = true;

    // Increase the right and bottom edges of our box until they are both inside the beam.
    while moved {
        moved = false;

        while !precheck(input, x, y + 99) || !test(code, x, y + 99) {
            x += 1;
            moved = true;
        }

        while !precheck(input, x + 99, y) || !test(code, x + 99, y) {
            y += 1;
            moved = true;
        }
    }

    10000 * x + y
}

/// Quick check with some false positives but no false negatives.
fn precheck(input: &Input, x: i64, y: i64) -> bool {
    50 * y > input.upper * x && 50 * x > input.lower * y
}

/// Definitive but slower check.
fn test(code: &[i64], x: i64, y: i64) -> bool {
    let mut computer = Computer::new(code);
    computer.input(x);
    computer.input(y);

    let State::Output(result) = computer.run() else { unreachable!() };
    result == 1
}