Module aoc::year2019::day17

Set and Forget

The key insight is that this is not a path finding problem but a compression problem. We need to reduce the robot’s path into repetitions of three patterns. This is essentially a very simple version of the well known LZW algorithm used by the GIF and ZIP file formats.

First we find the complete path with a simple heuristic:

• Rotate left or right to face the current path segment (a horizontal or vertical line).
• Go forwards until we hit the end of the current path segment.
• If it’s a dead end then finish.

Then we look for three patterns that can be repeated in any order to form the whole path. Without loss of any generality the first pattern anchored at the start is always A, the next B and the last C.

Structs

• Input
• Movement 🔒

Functions

• build_path 🔒
  Use a simple heuristic to build a path that visits every part of the scaffold at least once. This string will be too long to use directly in the robot’s movement functions, so we’ll need to compress it first.
• compress 🔒
  Find three patterns that can be repeated in any order to build the whole path.
• parse
  The camera output points from left to right, top to bottom.
• part1
• part2
• segments 🔒
  Fun with iterators.
• visit 🔒