aoc/year2019/
day17.rs

1//! # Set and Forget
2//!
3//! The key insight is that this is not a pathfinding problem but a *compression*
4//! problem. We need to reduce the robot's path into repetitions of three patterns.
5//! This is essentially a very simple version of the well-known
6//! [LZW](https://en.wikipedia.org/wiki/Lempel-Ziv-Welch)
7//! algorithm used by the `GIF` and `ZIP` file formats.
8//!
9//! First we find the complete path with a simple heuristic:
10//! * Rotate left or right to face the current path segment (a horizontal or vertical line).
11//! * Go forward until we hit the end of the current path segment.
12//! * If it's a dead end then finish.
13//!
14//! Then we look for three patterns that can be repeated in any order to form the whole path.
15//! Without loss of generality the first pattern anchored at the start is always `A`,
16//! the next `B` and the last `C`.
17//!
18//! A good chunk of the Intcode runtime is spent on unpacking compressed memory into the grid
19//! that is first displayed to the user. This effort is the same between both parts. Running the
20//! entire solution in parse thus reduces the overall runtime.
21use std::fmt::Write as _;
22use std::iter::once;
23use std::ops::ControlFlow;
24
25use super::intcode::*;
26use crate::util::hash::*;
27use crate::util::parse::*;
28use crate::util::point::*;
29
30type Input = (FastSet<Point>, i64);
31
32struct Movement<'a> {
33    routine: String,
34    functions: [Option<&'a str>; 3],
35}
36
37/// The camera output points from left to right, top to bottom.
38pub fn parse(input: &str) -> Input {
39    // Only run the part two program. Its initial output matches part one, and avoiding the
40    // startup costs of a second machine results in a faster solution.
41    let code: Vec<_> = once(2).chain(input.iter_signed().skip(1)).collect();
42    let mut computer = Computer::new(&code);
43
44    let mut x = 0;
45    let mut y = 0;
46    let mut scaffold = FastSet::new();
47    let mut position = ORIGIN;
48    let mut direction = ORIGIN;
49
50    while let State::Output(next) = computer.run() {
51        let next = next as u8;
52        let point = Point::new(x, y);
53
54        match next {
55            b'\n' => {
56                y += 1;
57                x = 0;
58                continue;
59            }
60            b'#' => {
61                scaffold.insert(point);
62            }
63            b'<' | b'>' | b'^' | b'v' => {
64                scaffold.insert(point);
65                position = point;
66                direction = Point::from(next);
67            }
68            _ => (),
69        }
70
71        x += 1;
72    }
73
74    // With the scaffold now available, construct the compressed path.
75    let path = build_path(&scaffold, position, direction);
76    let mut movement = Movement { routine: String::new(), functions: [None; 3] };
77
78    let _unused = compress(&path, &mut movement);
79
80    // Convert trailing comma ',' into a trailing newline '\n'
81    let mut rules = String::new();
82    let parts = once(movement.routine.as_str()).chain(movement.functions.into_iter().flatten());
83    for s in parts {
84        rules.push_str(s);
85        rules.pop();
86        rules.push('\n');
87    }
88
89    computer.input_ascii(&rules);
90    let score = visit(computer);
91
92    (scaffold, score)
93}
94
95pub fn part1(input: &Input) -> i32 {
96    let (scaffold, _) = input;
97    scaffold
98        .iter()
99        .filter(|&point| ORTHOGONAL.iter().all(|&delta| scaffold.contains(&(*point + delta))))
100        .map(|point| point.x * point.y)
101        .sum()
102}
103
104pub fn part2(input: &Input) -> i64 {
105    input.1
106}
107
108/// Use a simple heuristic to build a path that visits every part of the scaffold at least once.
109/// This string will be too long to use directly in the robot's movement functions, so we'll
110/// need to compress it first.
111fn build_path(scaffold: &FastSet<Point>, mut position: Point, mut direction: Point) -> String {
112    let mut path = String::new();
113
114    loop {
115        let left = direction.counter_clockwise();
116        let right = direction.clockwise();
117
118        if scaffold.contains(&(position + left)) {
119            direction = left;
120        } else if scaffold.contains(&(position + right)) {
121            direction = right;
122        } else {
123            break path;
124        }
125
126        let mut next = position + direction;
127        let mut magnitude = 0;
128
129        while scaffold.contains(&next) {
130            position = next;
131            next += direction;
132            magnitude += 1;
133        }
134
135        let direction = if direction == left { 'L' } else { 'R' };
136        let _ = write!(path, "{direction},{magnitude},");
137    }
138}
139
140/// Find three patterns that can be repeated in any order to build the whole path.
141///
142/// Uses a greedy backtracking algorithm that attempts to match as much of the remaining string
143/// as possible with known patterns, before trying combinations of a new pattern (up to the maximum
144/// movement function length of 20 characters).
145fn compress<'a>(path: &'a str, movement: &mut Movement<'a>) -> ControlFlow<()> {
146    // Nothing left to match, we've finished successfully.
147    if path.is_empty() {
148        return ControlFlow::Break(());
149    }
150    // Safety check just in case very short sequences can match the entire input.
151    if movement.routine.len() > 21 {
152        return ControlFlow::Continue(());
153    }
154
155    for (i, &name) in ['A', 'B', 'C'].iter().enumerate() {
156        movement.routine.push(name);
157        movement.routine.push(',');
158
159        if let Some(needle) = movement.functions[i] {
160            // Try known patterns first.
161            if let Some(remaining) = path.strip_prefix(needle) {
162                compress(remaining, movement)?;
163            }
164        } else {
165            // Then combinations up to length 20 characters.
166            for (needle, remaining) in segments(path) {
167                movement.functions[i] = Some(needle);
168                compress(remaining, movement)?;
169                movement.functions[i] = None;
170            }
171        }
172
173        movement.routine.pop();
174        movement.routine.pop();
175    }
176
177    ControlFlow::Continue(())
178}
179
180/// Fun with iterators.
181fn segments(path: &str) -> impl Iterator<Item = (&str, &str)> {
182    path.bytes()
183        .enumerate()
184        // Index of every comma ',' in the string.
185        .filter_map(|(i, b)| (b == b',').then_some(i))
186        // Maximum length for movement function is 20 characters.
187        .take_while(|&i| i < 21)
188        // Include trailing comma in "needle" to make matching easier.
189        .map(|i| path.split_at(i + 1))
190        // Movement is always pairs of (rotation, magnitude) so return every second comma.
191        .skip(1)
192        .step_by(2)
193}
194
195#[cfg(not(feature = "frivolity"))]
196fn visit(mut computer: Computer) -> i64 {
197    // Disable continuous video feed.
198    computer.input_ascii("n\n");
199
200    let mut result = 0;
201    while let State::Output(next) = computer.run() {
202        result = next;
203    }
204    result
205}
206
207/// Non essential but fun. Animates the robot traversing the scaffold.
208#[cfg(feature = "frivolity")]
209fn visit(mut computer: Computer) -> i64 {
210    use std::thread::sleep;
211    use std::time::Duration;
212
213    use crate::util::ansi::*;
214
215    let mut result = 0;
216    let mut previous = ' ';
217    let mut buffer = String::new();
218
219    // Enable continuous video feed.
220    computer.input_ascii("y\n");
221
222    while let State::Output(next) = computer.run() {
223        result = next;
224        let ascii = (next as u8) as char;
225
226        // Highlight the robot's position.
227        match ascii {
228            '^' | 'v' | '<' | '>' => {
229                let _ = write!(&mut buffer, "{BOLD}{YELLOW}{ascii}{RESET}");
230            }
231            _ => buffer.push(ascii),
232        }
233
234        // Each frame is separated by a blank line.
235        if ascii == '\n' && previous == '\n' {
236            print!("{HOME}{CLEAR}{buffer}");
237            sleep(Duration::from_millis(25));
238            buffer.clear();
239        }
240
241        previous = ascii;
242    }
243
244    result
245}
aoc/year2019/day17.rs

aoc/year2019/
day17.rs
