Advent of Code 2019 in 130 ms: day 17
Day 17: Set and Forget
Day 17 is an interesting exercise in sequence compression, but the runtime optimization of my solution, running in 1.9 ms, is more about implementation efficiency and a fast Intcode engine than about algorithmic sophistication.
Part 1 is about finding intersections on an ASCII map of tiles. My solution is rather simple: it runs the Intcode program and reads the map into a hash set of the scaffold tiles, then simply iterates through all the tiles to find the ones with more than 2 neighbors. Simple linear time complexity with nothing fancy going on.
Part 2 gets quite a bit more complicated. We need to find a path that visits every scaffold tile at least once, and then compress the path to fit in at most 20 ASCII characters. The movement functions act as the compression code book: a list of building blocks we can use to assemble the main movement routine by referencing the movement functions by index.
My solution begins by finding the simplest eligible path. By inspecting the map generated by my puzzle input, shown in figure 7, I noticed that I can simply move forward until I encounter a gap, then turn whichever of left and right is available - there are no “T” intersections on this map, so this will visit every tile on the map.
000000000011111111112222222222333333333344444444445
012345678901234567890123456789012345678901234567890
0 ......................#######......................
1 ......................#.....#......................
2 ..................####O##...#......................
3 ..................#...#.#...#......................
4 #########.........#...#.#...#......................
5 #.......#.........#...#.#...#......................
6 #.......#.########O####.#...#......................
7 #.......#.#.......#.....#...#......................
8 #.......#.#.......#...##O####......................
9 #.......#.#.......#.....#..........................
10 #######.##O######.######O##........................
11 ......#...#.....#.......#.#........................
12 ......#...#.....#.......#.#........................
13 ......#...#.....#.......#.#........................
14 ......#...#.####O########.#.........#######........
15 ......#...#.#...#.........#.........#.....#........
16 ......#...#.#...#.........#########.#.....#........
17 ......#...#.#...#.................#.#.....#........
18 ......#...##O####.................#.#.....#........
19 ......#.....#.....................#.#.....#........
20 ......#.....#.....................#.#.....#........
21 ......#.....#.....................#.#.....#........
22 ......#######...........R#########O##.####O####....
23 ..................................#...#...#...#....
24 ..................................#...#...#...#....
25 ..................................#...#...#...#....
26 ..................................#...#...####O####
27 ..................................#...#.......#...#
28 ..................................####O########...#
29 ......................................#...........#
30 ................................#######...........#
31 ................................#.................#
32 ................................#.....#############
33 ................................#.....#............
34 ................................#.....#............
35 ................................#.....#............
36 ................................#.....#............
37 ................................#.....#............
38 ................................#######............
# are scaffold tiles, . are empty,
O are intersections
and R is the robot's starting location.
This results in the following path:
R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
L(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1),
F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
R(1), F(1), F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
R(1), F(1), F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
R(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1),
R(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1), F(1), F(1),
R(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), F(1), F(1), F(1), F(1), L(1), F(1), F(1), F(1), F(1), F(1),
R(1), F(1), F(1), F(1), F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1),
F(1), F(1), R(1), F(1), F(1), F(1), F(1), F(1)
Here R(n), L(n) and F(n) respectively mean turn left, right,
or don’t turn, and then move n steps forward.
The next step is to compress this to a more compact representation
by simply merging the F(n) steps into the preceding non-F step:
R(12), L(8), R(6), R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6),
L(8), R(8), R(6), R(12), R(12), L(8), R(6), L(8), R(8), R(6), R(12),
R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6),
R(12), R(12), L(6), R(6), R(8), R(6)
After that, the code gets a bit convoluted, but it goes something like this:
First, find the longest prefix that appears again later in the sequence.
In the above sequence, this works out to [R(12), L(8), R(6), R(12)].
Then remove that prefix from the front and do the same thing two more times
so we have three subsequences, one for each movement function.
This gives us the subsequences
[L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6), R(12), R(12)]
and [L(8), R(6)].
Next we try to find a “covering” of the original sequence using the three subsequences. We do this by checking if any of the subsequences is a prefix of the original sequence, and if it is, remove it from the front and recursively try to find a covering for the rest of the sequence. If we manage to exhaust the sequence by these recursive calls, that means we covered the whole sequence, and we collect a list of the subsequence indices we used to build the covering. For example, with the above sequence and subsequences, it would proceed like this:
subsequences = [
[R(12), L(8), R(6), R(12)],
[L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6), R(12), R(12)],
[L(8), R(6)],
]
sequence = [
R(12), L(8), R(6), R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6),
L(8), R(8), R(6), R(12), R(12), L(8), R(6), L(8), R(8), R(6), R(12),
R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6),
R(12), R(12), L(6), R(6), R(8), R(6)
]
covering = []
Try subsequence 0: success!
covering = [0]
sequence = [
L(8), R(6), R(12), L(6), R(6), R(8), R(6),
L(8), R(8), R(6), R(12), R(12), L(8), R(6), L(8), R(8), R(6), R(12),
R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6),
R(12), R(12), L(6), R(6), R(8), R(6)
]
Try subsequence 0: failure
Try subsequence 1: success!
covering = [0, 1]
sequence = [
L(8), R(6), L(8), R(8), R(6), R(12),
R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6),
R(12), R(12), L(6), R(6), R(8), R(6)
]
Try subsequence 0: failure
Try subsequence 1: failure
Try subsequence 2: success!
covering = [0, 1, 2]
sequence = [
L(8), R(8), R(6), R(12),
R(12), L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6),
R(12), R(12), L(6), R(6), R(8), R(6)
]
Try subsequence 0: failure
Try subsequence 1: failure
Try subsequence 2: failure
So these three subsequences were not able to cover the original sequence.
We now proceed by removing one element from the back of the last subsequence,
changing [L(8), R(6)] to [L(8)], and try finding a covering again.
This also fails, so we again remove one element from the back.
The third subsequence is now empty, so we remove it
and remove one element from the new last subsequence,
changing [L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6), R(12), R(12)]
to [L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6), R(12)].
Now we go back to the start and find a new longest repeated prefix,
and add that as the third subsequence.
We now have the subsequences:
[R(12), L(8), R(6), R(12)]
[L(8), R(6), R(12), L(6), R(6), R(8), R(6), L(8), R(8), R(6), R(12)]
[R(12), L(8), R(6)]
and we continue trying to find a covering until we’ve reduced
also the second sequence to just [L(8)].
After that fails, we similarly remove the last element from the first subsequence,
replenish the last two subsequences with new longest prefixes, and continue the search.
Eventually we end up with the subsequences
[R(12), L(8), R(6)]
[R(12), L(6), R(6), R(8), R(6)]
[L(8), R(8), R(6), R(12), R(12), L(8), R(6)]
with which we do manage to find a covering: [0, 0, 1, 2, 0, 2, 0, 1, 2, 1],
meaning subsequence 0 twice, subsequence 1 and 2 once each, and so on.
And, well, that turned out to work just fine for my puzzle input. I don’t know if other people’s puzzle inputs require you to break the sequence into smaller segments, but by the “you’re probably not special” principle, I’m guessing not. Either way, my solution also works for the uncompressed path but takes significantly more attempts to find a set of covering subsequences - 1990 attempts on my puzzle input, compared to 19 attempts with the compressed path, although it only takes about 10 times longer time to run.
I don’t know if there’s a better way to do this, but since my runtime is already less than 2 ms, I haven’t really tried to find one since there was more room for improvement in other solutions.