year2019/
day19.rs

1use crate::intcode::Interpreter;
2use crate::intcode::features::Day09Features;
3use core::assert_matches;
4use utils::geometry::Vec2;
5use utils::prelude::*;
6
7/// Interpreting machine code to scan a beam.
8#[derive(Clone, Debug)]
9pub struct Day19 {
10    interpreter: Interpreter,
11}
12
13impl Day19 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        Ok(Self {
16            interpreter: Interpreter::parse(input, 1)?,
17        })
18    }
19
20    #[must_use]
21    pub fn part1(&self) -> u32 {
22        let mut interpreter = Interpreter::new(Vec::new());
23        let (mut min_x, mut max_x) = (49, 49);
24        let mut affected = 0;
25        for y in (0..50).rev() {
26            let mut new_max_x = max_x;
27            while new_max_x > 0 && !self.is_affected(&mut interpreter, new_max_x, y) {
28                new_max_x -= 1;
29            }
30            if new_max_x == 0 && !self.is_affected(&mut interpreter, 0, y) {
31                // Input has (0, 0) affected then a few blank lines before the beam resumes at y=6
32                continue;
33            }
34            max_x = new_max_x;
35
36            min_x = min_x.min(max_x);
37            while min_x > 0 && self.is_affected(&mut interpreter, min_x - 1, y) {
38                min_x -= 1;
39            }
40
41            affected += max_x - min_x + 1;
42        }
43        affected
44    }
45
46    #[must_use]
47    #[expect(clippy::maybe_infinite_iter)]
48    pub fn part2(&self) -> u32 {
49        let mut interpreter = Interpreter::new(Vec::new());
50        let inside_x = (0..=50)
51            .rev()
52            .chain(51..)
53            .find(|&x| self.is_affected(&mut interpreter, x, 50))
54            .expect("no solution found");
55
56        let initial = Vec2::new(inside_x.max(1), 50);
57        let mut row_start = self.find_row_start(&mut interpreter, 0, 50, initial);
58        let mut column_start =
59            self.find_column_start(&mut interpreter, row_start.x + 99, 0, initial);
60
61        loop {
62            let next_row_start = self.find_row_start(
63                &mut interpreter,
64                row_start.x,
65                column_start.y + 99,
66                row_start,
67            );
68            let next_column_start = self.find_column_start(
69                &mut interpreter,
70                next_row_start.x + 99,
71                column_start.y,
72                column_start,
73            );
74            if next_column_start.y == column_start.y {
75                return next_row_start.x * 10_000 + column_start.y;
76            }
77            (row_start, column_start) = (next_row_start, next_column_start);
78        }
79    }
80
81    fn find_row_start(
82        &self,
83        interpreter: &mut Interpreter,
84        mut x: u32,
85        y: u32,
86        last: Vec2<u32>,
87    ) -> Vec2<u32> {
88        let guess = x.max((last.x * y).div_ceil(last.y));
89        if guess > x && self.is_affected(interpreter, guess, y) {
90            x = guess;
91            while x > 0 && self.is_affected(interpreter, x - 1, y) {
92                x -= 1;
93            }
94        } else {
95            while !self.is_affected(interpreter, x, y) {
96                x += 1;
97            }
98        }
99        Vec2::new(x, y)
100    }
101
102    fn find_column_start(
103        &self,
104        interpreter: &mut Interpreter,
105        x: u32,
106        mut y: u32,
107        last: Vec2<u32>,
108    ) -> Vec2<u32> {
109        let guess = y.max((last.y * x).div_ceil(last.x));
110        if guess > y && self.is_affected(interpreter, x, guess) {
111            y = guess;
112            while y > 0 && self.is_affected(interpreter, x, y - 1) {
113                y -= 1;
114            }
115        } else {
116            while !self.is_affected(interpreter, x, y) {
117                y += 1;
118            }
119        }
120        Vec2::new(x, y)
121    }
122
123    fn is_affected(&self, interpreter: &mut Interpreter, x: u32, y: u32) -> bool {
124        interpreter.mem.clone_from(&self.interpreter.mem);
125        interpreter.ip = 0;
126        interpreter.relative_base = 0;
127        interpreter.push_input(i64::from(x));
128        interpreter.push_input(i64::from(y));
129
130        let output = interpreter.expect_output::<Day09Features>();
131        assert_matches!(output, 0 | 1, "expected output zero or one");
132        output == 1
133    }
134}
135
136examples!(Day19 -> (u32, u32) []);
year2019/day19.rs

year2019/
day19.rs
