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    pub fn part2(&self) -> u32 {
48        let mut interpreter = Interpreter::new(Vec::new());
49        let inside_x = (0..=50)
50            .rev()
51            .chain(51..)
52            .find(|&x| self.is_affected(&mut interpreter, x, 50))
53            .expect("no solution found");
54
55        let initial = Vec2::new(inside_x.max(1), 50);
56        let mut row_start = self.find_row_start(&mut interpreter, 0, 50, initial);
57        let mut column_start =
58            self.find_column_start(&mut interpreter, row_start.x + 99, 0, initial);
59
60        loop {
61            let next_row_start = self.find_row_start(
62                &mut interpreter,
63                row_start.x,
64                column_start.y + 99,
65                row_start,
66            );
67            let next_column_start = self.find_column_start(
68                &mut interpreter,
69                next_row_start.x + 99,
70                column_start.y,
71                column_start,
72            );
73            if next_column_start.y == column_start.y {
74                return next_row_start.x * 10_000 + column_start.y;
75            }
76            (row_start, column_start) = (next_row_start, next_column_start);
77        }
78    }
79
80    fn find_row_start(
81        &self,
82        interpreter: &mut Interpreter,
83        mut x: u32,
84        y: u32,
85        last: Vec2<u32>,
86    ) -> Vec2<u32> {
87        let guess = x.max((last.x * y).div_ceil(last.y));
88        if guess > x && self.is_affected(interpreter, guess, y) {
89            x = guess;
90            while x > 0 && self.is_affected(interpreter, x - 1, y) {
91                x -= 1;
92            }
93        } else {
94            while !self.is_affected(interpreter, x, y) {
95                x += 1;
96            }
97        }
98        Vec2::new(x, y)
99    }
100
101    fn find_column_start(
102        &self,
103        interpreter: &mut Interpreter,
104        x: u32,
105        mut y: u32,
106        last: Vec2<u32>,
107    ) -> Vec2<u32> {
108        let guess = y.max((last.y * x).div_ceil(last.x));
109        if guess > y && self.is_affected(interpreter, x, guess) {
110            y = guess;
111            while y > 0 && self.is_affected(interpreter, x, y - 1) {
112                y -= 1;
113            }
114        } else {
115            while !self.is_affected(interpreter, x, y) {
116                y += 1;
117            }
118        }
119        Vec2::new(x, y)
120    }
121
122    fn is_affected(&self, interpreter: &mut Interpreter, x: u32, y: u32) -> bool {
123        interpreter.mem.clone_from(&self.interpreter.mem);
124        interpreter.ip = 0;
125        interpreter.relative_base = 0;
126        interpreter.push_input(i64::from(x));
127        interpreter.push_input(i64::from(y));
128
129        let output = interpreter.expect_output::<Day09Features>();
130        assert_matches!(output, 0 | 1, "expected output zero or one");
131        output == 1
132    }
133}
134
135examples!(Day19 -> (u32, u32) []);
year2019/day19.rs

year2019/
day19.rs
