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

aoc/year2019/
day17.rs
