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`.
17use super::intcode::*;
18use crate::util::hash::*;
19use crate::util::parse::*;
20use crate::util::point::*;
21use std::fmt::Write as _;
22use std::iter::once;
23use std::ops::ControlFlow;
24
25pub struct Input {
26    code: Vec<i64>,
27    scaffold: FastSet<Point>,
28    position: Point,
29    direction: Point,
30}
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    let code: Vec<_> = input.iter_signed().collect();
40    let mut computer = Computer::new(&code);
41
42    let mut x = 0;
43    let mut y = 0;
44    let mut scaffold = FastSet::new();
45    let mut position = ORIGIN;
46    let mut direction = ORIGIN;
47
48    while let State::Output(next) = computer.run() {
49        let next = next as u8;
50        let point = Point::new(x, y);
51
52        match next {
53            b'\n' => {
54                y += 1;
55                x = 0;
56                continue;
57            }
58            b'#' => {
59                scaffold.insert(point);
60            }
61            b'<' | b'>' | b'^' | b'v' => {
62                scaffold.insert(point);
63                position = point;
64                direction = Point::from(next);
65            }
66            _ => (),
67        }
68
69        x += 1;
70    }
71
72    Input { code, scaffold, position, direction }
73}
74
75pub fn part1(input: &Input) -> i32 {
76    input
77        .scaffold
78        .iter()
79        .filter(|&point| ORTHOGONAL.iter().all(|&delta| input.scaffold.contains(&(*point + delta))))
80        .map(|point| point.x * point.y)
81        .sum()
82}
83
84pub fn part2(input: &Input) -> i64 {
85    let path = build_path(input);
86    let mut movement = Movement { routine: String::new(), functions: [None; 3] };
87
88    let _unused = compress(&path, &mut movement);
89
90    // Convert trailing comma ',' into a trailing newline '\n'
91    let mut rules = String::new();
92    let parts = once(movement.routine.as_str()).chain(movement.functions.into_iter().flatten());
93    for s in parts {
94        rules.push_str(s);
95        rules.pop();
96        rules.push('\n');
97    }
98
99    let mut modified = input.code.clone();
100    modified[0] = 2;
101
102    let mut computer = Computer::new(&modified);
103    computer.input_ascii(&rules);
104
105    visit(computer)
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(input: &Input) -> String {
112    let scaffold = &input.scaffold;
113    let mut position = input.position;
114    let mut direction = input.direction;
115    let mut path = String::new();
116
117    loop {
118        let left = direction.counter_clockwise();
119        let right = direction.clockwise();
120
121        if scaffold.contains(&(position + left)) {
122            direction = left;
123        } else if scaffold.contains(&(position + right)) {
124            direction = right;
125        } else {
126            break path;
127        }
128
129        let mut next = position + direction;
130        let mut magnitude = 0;
131
132        while scaffold.contains(&next) {
133            position = next;
134            next += direction;
135            magnitude += 1;
136        }
137
138        let direction = if direction == left { 'L' } else { 'R' };
139        let _ = write!(path, "{direction},{magnitude},");
140    }
141}
142
143/// Find three patterns that can be repeated in any order to build the whole path.
144///
145/// Uses a greedy backtracking algorithm that attempts to match as much of the remaining string
146/// as possible with known patterns, before trying combinations of a new pattern (up to the maximum
147/// movement function length of 20 characters).
148fn compress<'a>(path: &'a str, movement: &mut Movement<'a>) -> ControlFlow<()> {
149    // Nothing left to match, we've finished successfully.
150    if path.is_empty() {
151        return ControlFlow::Break(());
152    }
153    // Safety check just in case very short sequences can match the entire input.
154    if movement.routine.len() > 21 {
155        return ControlFlow::Continue(());
156    }
157
158    for (i, &name) in ['A', 'B', 'C'].iter().enumerate() {
159        movement.routine.push(name);
160        movement.routine.push(',');
161
162        if let Some(needle) = movement.functions[i] {
163            // Try known patterns first.
164            if let Some(remaining) = path.strip_prefix(needle) {
165                compress(remaining, movement)?;
166            }
167        } else {
168            // Then combinations up to length 20 characters.
169            for (needle, remaining) in segments(path) {
170                movement.functions[i] = Some(needle);
171                compress(remaining, movement)?;
172                movement.functions[i] = None;
173            }
174        }
175
176        movement.routine.pop();
177        movement.routine.pop();
178    }
179
180    ControlFlow::Continue(())
181}
182
183/// Fun with iterators.
184fn segments(path: &str) -> impl Iterator<Item = (&str, &str)> {
185    path.bytes()
186        .enumerate()
187        // Index of every comma ',' in the string.
188        .filter_map(|(i, b)| (b == b',').then_some(i))
189        // Maximum length for movement function is 20 characters.
190        .take_while(|&i| i < 21)
191        // Include trailing comma in "needle" to make matching easier.
192        .map(|i| path.split_at(i + 1))
193        // Movement is always pairs of (rotation, magnitude) so return every second comma.
194        .skip(1)
195        .step_by(2)
196}
197
198#[cfg(not(feature = "frivolity"))]
199fn visit(mut computer: Computer) -> i64 {
200    // Disable continuous video feed.
201    computer.input_ascii("n\n");
202
203    let mut result = 0;
204    while let State::Output(next) = computer.run() {
205        result = next;
206    }
207    result
208}
209
210/// Non essential but fun. Animates the robot traversing the scaffold.
211#[cfg(feature = "frivolity")]
212fn visit(mut computer: Computer) -> i64 {
213    use crate::util::ansi::*;
214    use std::thread::sleep;
215    use std::time::Duration;
216
217    let mut result = 0;
218    let mut previous = ' ';
219    let mut buffer = String::new();
220
221    // Enable continuous video feed.
222    computer.input_ascii("y\n");
223
224    while let State::Output(next) = computer.run() {
225        result = next;
226        let ascii = (next as u8) as char;
227
228        // Highlight the robot's position.
229        match ascii {
230            '^' | 'v' | '<' | '>' => {
231                let _ = write!(&mut buffer, "{BOLD}{YELLOW}{ascii}{RESET}");
232            }
233            _ => buffer.push(ascii),
234        }
235
236        // Each frame is separated by a blank line.
237        if ascii == '\n' && previous == '\n' {
238            print!("{HOME}{CLEAR}{buffer}");
239            sleep(Duration::from_millis(25));
240            buffer.clear();
241        }
242
243        previous = ascii;
244    }
245
246    result
247}
aoc/year2019/day17.rs

aoc/year2019/
day17.rs
