aoc/year2019/
day17.rs

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

aoc/year2019/
day17.rs
