The Historians use their fancy device again, this time to whisk you all away to the North Pole prototype suit manufacturing lab... in the year 1518! It turns out that having direct access to history is very convenient for a group of historians.
You still have to be careful of time paradoxes, and so it will be important to avoid anyone from 1518 while The Historians search for the Chief. Unfortunately, a single guard is patrolling this part of the lab.
Maybe you can work out where the guard will go ahead of time so that The Historians can search safely?
You start by making a map (your puzzle input) of the situation. For example:
12345678910....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...The map shows the current position of the guard with ^ (to indicate the guard is currently facing up from the perspective of the map). Any obstructions - crates, desks, alchemical reactors, etc. - are shown as #.
Lab guards in 1518 follow a very strict patrol protocol which involves repeatedly following these steps:
- If there is something directly in front of you, turn right 90 degrees.
- Otherwise, take a step forward.
Following the above protocol, the guard moves up several times until she reaches an obstacle (in this case, a pile of failed suit prototypes):
12345678910....#.....
....^....#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...Because there is now an obstacle in front of the guard, she turns right before continuing straight in her new facing direction:
12345678910....#.....
........>#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...Reaching another obstacle (a spool of several very long polymers), she turns right again and continues downward:
12345678910....#.....
.........#
..........
..#.......
.......#..
..........
.#......v.
........#.
#.........
......#...This process continues for a while, but the guard eventually leaves the mapped area (after walking past a tank of universal solvent):
12345678910....#.....
.........#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#v..By predicting the guard's route, you can determine which specific positions in the lab will be in the patrol path. Including the guard's starting position, the positions visited by the guard before leaving the area are marked with an X:
12345678910....#.....
....XXXXX#
....X...X.
..#.X...X.
..XXXXX#X.
..X.X.X.X.
.#XXXXXXX.
.XXXXXXX#.
#XXXXXXX..
......#X..In this example, the guard will visit 41 distinct positions on your map.
Predict the path of the guard. How many distinct positions will the guard visit before leaving the mapped area?
Total steps: 0
Unique steps: 0
Guard:
{
"x": 60,
"y": 70,
"direction": "^"
}Map:
........#...#..................#.#............#....#....##.........#.............................................#.................#...............#...........................#..........#..........#....#........................................#............#...............#...........................................##.................#.......#............................................#....#.......................##.........................................#..............................................#....#..............#....#......#...................................#............#............#.......#.......#.................#..............#......#........#..................................#..##........#...........#.....................#......#..................#...........................#........#.....#.....................#.......##........#............#.#....#..#.......#.....................#.........................#.................#.............................................................#............................#....#.................................#........#..#.........................#............#...#.........#...#..............##......................................................................................#...#......................#...#...#..#......................#........#.............................#........................#.....#..................#..........................#.........................#.#..........#.....#..............................#..#...#...#.........#..............................#............#.................#.....#..............#................#...........................................#..........................#...#......#.........##................#...................................................#....#.#.....................................................#..................................................#..............................#...#...........#...............#............#....................................#.....................#............#....................#.....#.#....#.....................#.....#.......................#......#......#...................................#.....#.........#...#..............#...#...............................#...#...........#...............#....#....#..............................#..........#......................................................................#.........................................#................#..................................#........#........#...................#.............#.............................................................................................................................................................#........#........................#.....................................#.....#.................#.........#..............#............#.................................#...................#....................................................................#........#................#.....................................................#............#.....................#....................#......................................#.....#......................................#..........#...#........#........................#............................................#..................#.........#..#....................................................#..#..........................................................................#.................##..#...................................................#.#.....................#.......#..#..................#.........#.........................................................#......#......................#.........#..........................................#..........#....#..##....#.......#...........................................#..........#...........................#..................................#......#............##...#..#......................#............................#...................#........#.............................................#........#............#..................#....#...##...........................................................................#......................#......#.............#................................#...#........#.........#.....................#..#......................#...#.........................#..................................###..............................#........#.....................................................................................#.....#...............#.......#..........................#.................................#..................#..........................................#.................#.............#...................................#.............................#..........#................................#.....................................#..........................................................................#....#.............#......................#..#.........#.................................................................##........................#.......#..............#..........................................................................#.................................................................................#...#...#....................#...........#...........#................................................................#................#..............#............................#.......#..#.............................................#...#.........#.............#.........#.......#...........................................#..#.....#.....................#......#.#.............................................#.....#...#...........#..............................................#....#...............#.........................#....................#........#..................................................#..........................................................#.................#.................................#...........##..........#.....................................#..........................#........#.....#........................#.......................##................................#........................................#..............#.....................#...#..#....#................#.......#..................................#..................#.....................#....#.....................#...........................#......................................##..........#......#..............#.............................#.......#....................#............#.........................................................................................#...........#..#.......#.....................#................#.#.....#.....#...........................#..................................................#..#.#.............................................#......#..........#................................................#.........................................................................#..............#..............#..........................................................................#........................................................................................#....#..#..............#...........................................................#.......#.#...............................#...#.#....#......#...........................................................................................#....#....................#.................................................................................#..#...#...........................#...#...................#.............................................#..............###..........#...........................................................#................#.........................................................................#.................#.......................#...................................#................................#.................................................##........................#...............................#.........#......................................................................................#..........##.......................................................#.................................#................................##.................##.#...........................#.....................#..............................................................................................................#................................................#........#..........................#..........................................................................#..........#...............................................#...#................#......................................#................#...........#...............................................................................#................#.........................#.............................................................................#..#................#.....#....#.................#....#.......................................#..........................#...###.......#..#.....#.#..#..........#............................................................^.............................#.#............................##....#...#............#.................#......#..................................#....................##.......................................................................................................#.......#...............#..................#..........#..............................................#............................................#.....#.#.#..#..........................#.......................#.........................................................#.......#...#..#.....#........................................#......................................................##......#................#.....................#...........................#.............................#..........................#...........#..#................................................................................#......#.............##...............................................................#..................................................................................#.....#.....................##...##...........#.............#..#.................................#......................#.........#.................#.......................##...................................................#..........................................................#....................................................#...........#..........#............................#.........#................................................................#.........................................................................................................................................................#.....................##.......#........#................#....#................#...........................#.............#........................#..................................#............................................#............................#.......................................................#.....#........#.....#..............#............#..................................#.......................#...............................................................#..................................................#...........#....#....#.......................#.........................#...............................................#..#............................#..................#......#........#...........#..#...#........................#........................................................#....................................................#.#.#................................................##.#...................................#.....................#.#............#................#..............#.....................................................#........#................#.......................#........#...................................................#...........................#..................................................#..#.........................#....#.......#....##.............#................................................................#...........................#...........#................................#...........................#.................#...#....................................................................................................................#........#.......#......................................#.........#.................#.#..........#.................................#........#........................###.........................#...................#................#.................#...............##.........#.........#..............................................#...........................................#..#.#.........#...........#..................#..........................................................#.....#..................#...............#......................#..............#.....................##................#..#.....#..........................#.#..................#.#..#..............................#........#........................................................................#................................#.....................#....#.....................#..........................................#..............#..#........#........................#................................#..................................#.#..................#.........#...#.....................##.........#.............................................................................#..........#...........#............................#.............................#...........#........#..............#..#.....................#...................#................#..................................................##.......#....................#..............#.##.............................................................................................................................................................#......................#................#....#......................#...........#..........#......#.#......#................#....#...#..............#...........#........................................#..................#...#......................................##.................................................................................#....................#.........#...............................#......#.................#.......................................#...#....#..#......#.........#...........#..............#...................................................................#.........#............#.#........................................#..............#.......................................................................................#.................................................................................#............#....................#......................................................#.................#..#..............#....................................#.....................................................#...............................#................#....#....................#....#........................#...........................................................................#....................................................................#..........................................#...................#.........................#...........................................#.............................#..................#.......................................#....................................................#.....................................#...............#............................................#........................#.........#................#........#............##.....#.............#...#..............#........................#....................#........#...................................#.....................##.#......................................................................#.............#.......................................#.......................#..........#..#..............#..............#.#..........................#...............#....#................................#......................#...........................#...............#......#.............#.......................#.........................#.......................................................................#...............................................#........................................#...............##...........#...................#.....##...#..........#........................#.............#.........#.....#................#..............#..........................#...........................#...................#....#...........#....#........................##.....#...#..................................While The Historians begin working around the guard's patrol route, you borrow their fancy device and step outside the lab. From the safety of a supply closet, you time travel through the last few months and record the nightly status of the lab's guard post on the walls of the closet.
Returning after what seems like only a few seconds to The Historians, they explain that the guard's patrol area is simply too large for them to safely search the lab without getting caught.
Fortunately, they are pretty sure that adding a single new obstruction won't cause a time paradox. They'd like to place the new obstruction in such a way that the guard will get stuck in a loop, making the rest of the lab safe to search.
To have the lowest chance of creating a time paradox, The Historians would like to know all of the possible positions for such an obstruction. The new obstruction can't be placed at the guard's starting position - the guard is there right now and would notice.
In the above example, there are only 6 different positions where a new obstruction would cause the guard to get stuck in a loop. The diagrams of these six situations use O to mark the new obstruction, | to show a position where the guard moves up/down, - to show a position where the guard moves left/right, and + to show a position where the guard moves both up/down and left/right.
Option one, put a printing press next to the guard's starting position:
12345678910....#.....
....+---+#
....|...|.
..#.|...|.
....|..#|.
....|...|.
.#.O^---+.
........#.
#.........
......#...Option two, put a stack of failed suit prototypes in the bottom right quadrant of the mapped area:
12345678910....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
......O.#.
#.........
......#...Option three, put a crate of chimney-squeeze prototype fabric next to the standing desk in the bottom right quadrant:
12345678910....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
.+----+O#.
#+----+...
......#...Option four, put an alchemical retroencabulator near the bottom left corner:
12345678910....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
..|...|.#.
#O+---+...
......#...Option five, put the alchemical retroencabulator a bit to the right instead:
12345678910....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
....|.|.#.
#..O+-+...
......#...Option six, put a tank of sovereign glue right next to the tank of universal solvent:
12345678910....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
.+----++#.
#+----++..
......#O..It doesn't really matter what you choose to use as an obstacle so long as you and The Historians can put it into position without the guard noticing. The important thing is having enough options that you can find one that minimizes time paradoxes, and in this example, there are 6 different positions you could choose.
You need to get the guard stuck in a loop by adding a single new obstruction. How many different positions could you choose for this obstruction?
Total steps: 0
Exploratory Map
Unique steps: 0
Guard:
{
"x": 60,
"y": 70,
"direction": "^"
}Map:
........#...#..................#.#............#....#....##.........#.............................................#.................#...............#...........................#..........#..........#....#........................................#............#...............#...........................................##.................#.......#............................................#....#.......................##.........................................#..............................................#....#..............#....#......#...................................#............#............#.......#.......#.................#..............#......#........#..................................#..##........#...........#.....................#......#..................#...........................#........#.....#.....................#.......##........#............#.#....#..#.......#.....................#.........................#.................#.............................................................#............................#....#.................................#........#..#.........................#............#...#.........#...#..............##......................................................................................#...#......................#...#...#..#......................#........#.............................#........................#.....#..................#..........................#.........................#.#..........#.....#..............................#..#...#...#.........#..............................#............#.................#.....#..............#................#...........................................#..........................#...#......#.........##................#...................................................#....#.#.....................................................#..................................................#..............................#...#...........#...............#............#....................................#.....................#............#....................#.....#.#....#.....................#.....#.......................#......#......#...................................#.....#.........#...#..............#...#...............................#...#...........#...............#....#....#..............................#..........#......................................................................#.........................................#................#..................................#........#........#...................#.............#.............................................................................................................................................................#........#........................#.....................................#.....#.................#.........#..............#............#.................................#...................#....................................................................#........#................#.....................................................#............#.....................#....................#......................................#.....#......................................#..........#...#........#........................#............................................#..................#.........#..#....................................................#..#..........................................................................#.................##..#...................................................#.#.....................#.......#..#..................#.........#.........................................................#......#......................#.........#..........................................#..........#....#..##....#.......#...........................................#..........#...........................#..................................#......#............##...#..#......................#............................#...................#........#.............................................#........#............#..................#....#...##...........................................................................#......................#......#.............#................................#...#........#.........#.....................#..#......................#...#.........................#..................................###..............................#........#.....................................................................................#.....#...............#.......#..........................#.................................#..................#..........................................#.................#.............#...................................#.............................#..........#................................#.....................................#..........................................................................#....#.............#......................#..#.........#.................................................................##........................#.......#..............#..........................................................................#.................................................................................#...#...#....................#...........#...........#................................................................#................#..............#............................#.......#..#.............................................#...#.........#.............#.........#.......#...........................................#..#.....#.....................#......#.#.............................................#.....#...#...........#..............................................#....#...............#.........................#....................#........#..................................................#..........................................................#.................#.................................#...........##..........#.....................................#..........................#........#.....#........................#.......................##................................#........................................#..............#.....................#...#..#....#................#.......#..................................#..................#.....................#....#.....................#...........................#......................................##..........#......#..............#.............................#.......#....................#............#.........................................................................................#...........#..#.......#.....................#................#.#.....#.....#...........................#..................................................#..#.#.............................................#......#..........#................................................#.........................................................................#..............#..............#..........................................................................#........................................................................................#....#..#..............#...........................................................#.......#.#...............................#...#.#....#......#...........................................................................................#....#....................#.................................................................................#..#...#...........................#...#...................#.............................................#..............###..........#...........................................................#................#.........................................................................#.................#.......................#...................................#................................#.................................................##........................#...............................#.........#......................................................................................#..........##.......................................................#.................................#................................##.................##.#...........................#.....................#..............................................................................................................#................................................#........#..........................#..........................................................................#..........#...............................................#...#................#......................................#................#...........#...............................................................................#................#.........................#.............................................................................#..#................#.....#....#.................#....#.......................................#..........................#...###.......#..#.....#.#..#..........#............................................................^.............................#.#............................##....#...#............#.................#......#..................................#....................##.......................................................................................................#.......#...............#..................#..........#..............................................#............................................#.....#.#.#..#..........................#.......................#.........................................................#.......#...#..#.....#........................................#......................................................##......#................#.....................#...........................#.............................#..........................#...........#..#................................................................................#......#.............##...............................................................#..................................................................................#.....#.....................##...##...........#.............#..#.................................#......................#.........#.................#.......................##...................................................#..........................................................#....................................................#...........#..........#............................#.........#................................................................#.........................................................................................................................................................#.....................##.......#........#................#....#................#...........................#.............#........................#..................................#............................................#............................#.......................................................#.....#........#.....#..............#............#..................................#.......................#...............................................................#..................................................#...........#....#....#.......................#.........................#...............................................#..#............................#..................#......#........#...........#..#...#........................#........................................................#....................................................#.#.#................................................##.#...................................#.....................#.#............#................#..............#.....................................................#........#................#.......................#........#...................................................#...........................#..................................................#..#.........................#....#.......#....##.............#................................................................#...........................#...........#................................#...........................#.................#...#....................................................................................................................#........#.......#......................................#.........#.................#.#..........#.................................#........#........................###.........................#...................#................#.................#...............##.........#.........#..............................................#...........................................#..#.#.........#...........#..................#..........................................................#.....#..................#...............#......................#..............#.....................##................#..#.....#..........................#.#..................#.#..#..............................#........#........................................................................#................................#.....................#....#.....................#..........................................#..............#..#........#........................#................................#..................................#.#..................#.........#...#.....................##.........#.............................................................................#..........#...........#............................#.............................#...........#........#..............#..#.....................#...................#................#..................................................##.......#....................#..............#.##.............................................................................................................................................................#......................#................#....#......................#...........#..........#......#.#......#................#....#...#..............#...........#........................................#..................#...#......................................##.................................................................................#....................#.........#...............................#......#.................#.......................................#...#....#..#......#.........#...........#..............#...................................................................#.........#............#.#........................................#..............#.......................................................................................#.................................................................................#............#....................#......................................................#.................#..#..............#....................................#.....................................................#...............................#................#....#....................#....#........................#...........................................................................#....................................................................#..........................................#...................#.........................#...........................................#.............................#..................#.......................................#....................................................#.....................................#...............#............................................#........................#.........#................#........#............##.....#.............#...#..............#........................#....................#........#...................................#.....................##.#......................................................................#.............#.......................................#.......................#..........#..#..............#..............#.#..........................#...............#....#................................#......................#...........................#...............#......#.............#.......................#.........................#.......................................................................#...............................................#........................................#...............##...........#...................#.....##...#..........#........................#.............#.........#.....#................#..............#..........................#...........................#...................#....#...........#....#........................##.....#...#..................................Blocking Map
Loops found: 0
Map:
........#...#..................#.#............#....#....##.........#.............................................#.................#...............#...........................#..........#..........#....#........................................#............#...............#...........................................##.................#.......#............................................#....#.......................##.........................................#..............................................#....#..............#....#......#...................................#............#............#.......#.......#.................#..............#......#........#..................................#..##........#...........#.....................#......#..................#...........................#........#.....#.....................#.......##........#............#.#....#..#.......#.....................#.........................#.................#.............................................................#............................#....#.................................#........#..#.........................#............#...#.........#...#..............##......................................................................................#...#......................#...#...#..#......................#........#.............................#........................#.....#..................#..........................#.........................#.#..........#.....#..............................#..#...#...#.........#..............................#............#.................#.....#..............#................#...........................................#..........................#...#......#.........##................#...................................................#....#.#.....................................................#..................................................#..............................#...#...........#...............#............#....................................#.....................#............#....................#.....#.#....#.....................#.....#.......................#......#......#...................................#.....#.........#...#..............#...#...............................#...#...........#...............#....#....#..............................#..........#......................................................................#.........................................#................#..................................#........#........#...................#.............#.............................................................................................................................................................#........#........................#.....................................#.....#.................#.........#..............#............#.................................#...................#....................................................................#........#................#.....................................................#............#.....................#....................#......................................#.....#......................................#..........#...#........#........................#............................................#..................#.........#..#....................................................#..#..........................................................................#.................##..#...................................................#.#.....................#.......#..#..................#.........#.........................................................#......#......................#.........#..........................................#..........#....#..##....#.......#...........................................#..........#...........................#..................................#......#............##...#..#......................#............................#...................#........#.............................................#........#............#..................#....#...##...........................................................................#......................#......#.............#................................#...#........#.........#.....................#..#......................#...#.........................#..................................###..............................#........#.....................................................................................#.....#...............#.......#..........................#.................................#..................#..........................................#.................#.............#...................................#.............................#..........#................................#.....................................#..........................................................................#....#.............#......................#..#.........#.................................................................##........................#.......#..............#..........................................................................#.................................................................................#...#...#....................#...........#...........#................................................................#................#..............#............................#.......#..#.............................................#...#.........#.............#.........#.......#...........................................#..#.....#.....................#......#.#.............................................#.....#...#...........#..............................................#....#...............#.........................#....................#........#..................................................#..........................................................#.................#.................................#...........##..........#.....................................#..........................#........#.....#........................#.......................##................................#........................................#..............#.....................#...#..#....#................#.......#..................................#..................#.....................#....#.....................#...........................#......................................##..........#......#..............#.............................#.......#....................#............#.........................................................................................#...........#..#.......#.....................#................#.#.....#.....#...........................#..................................................#..#.#.............................................#......#..........#................................................#.........................................................................#..............#..............#..........................................................................#........................................................................................#....#..#..............#...........................................................#.......#.#...............................#...#.#....#......#...........................................................................................#....#....................#.................................................................................#..#...#...........................#...#...................#.............................................#..............###..........#...........................................................#................#.........................................................................#.................#.......................#...................................#................................#.................................................##........................#...............................#.........#......................................................................................#..........##.......................................................#.................................#................................##.................##.#...........................#.....................#..............................................................................................................#................................................#........#..........................#..........................................................................#..........#...............................................#...#................#......................................#................#...........#...............................................................................#................#.........................#.............................................................................#..#................#.....#....#.................#....#.......................................#..........................#...###.......#..#.....#.#..#..........#............................................................^.............................#.#............................##....#...#............#.................#......#..................................#....................##.......................................................................................................#.......#...............#..................#..........#..............................................#............................................#.....#.#.#..#..........................#.......................#.........................................................#.......#...#..#.....#........................................#......................................................##......#................#.....................#...........................#.............................#..........................#...........#..#................................................................................#......#.............##...............................................................#..................................................................................#.....#.....................##...##...........#.............#..#.................................#......................#.........#.................#.......................##...................................................#..........................................................#....................................................#...........#..........#............................#.........#................................................................#.........................................................................................................................................................#.....................##.......#........#................#....#................#...........................#.............#........................#..................................#............................................#............................#.......................................................#.....#........#.....#..............#............#..................................#.......................#...............................................................#..................................................#...........#....#....#.......................#.........................#...............................................#..#............................#..................#......#........#...........#..#...#........................#........................................................#....................................................#.#.#................................................##.#...................................#.....................#.#............#................#..............#.....................................................#........#................#.......................#........#...................................................#...........................#..................................................#..#.........................#....#.......#....##.............#................................................................#...........................#...........#................................#...........................#.................#...#....................................................................................................................#........#.......#......................................#.........#.................#.#..........#.................................#........#........................###.........................#...................#................#.................#...............##.........#.........#..............................................#...........................................#..#.#.........#...........#..................#..........................................................#.....#..................#...............#......................#..............#.....................##................#..#.....#..........................#.#..................#.#..#..............................#........#........................................................................#................................#.....................#....#.....................#..........................................#..............#..#........#........................#................................#..................................#.#..................#.........#...#.....................##.........#.............................................................................#..........#...........#............................#.............................#...........#........#..............#..#.....................#...................#................#..................................................##.......#....................#..............#.##.............................................................................................................................................................#......................#................#....#......................#...........#..........#......#.#......#................#....#...#..............#...........#........................................#..................#...#......................................##.................................................................................#....................#.........#...............................#......#.................#.......................................#...#....#..#......#.........#...........#..............#...................................................................#.........#............#.#........................................#..............#.......................................................................................#.................................................................................#............#....................#......................................................#.................#..#..............#....................................#.....................................................#...............................#................#....#....................#....#........................#...........................................................................#....................................................................#..........................................#...................#.........................#...........................................#.............................#..................#.......................................#....................................................#.....................................#...............#............................................#........................#.........#................#........#............##.....#.............#...#..............#........................#....................#........#...................................#.....................##.#......................................................................#.............#.......................................#.......................#..........#..#..............#..............#.#..........................#...............#....#................................#......................#...........................#...............#......#.............#.......................#.........................#.......................................................................#...............................................#........................................#...............##...........#...................#.....##...#..........#........................#.............#.........#.....#................#..............#..........................#...........................#...................#....#...........#....#........................##.....#...#..................................| Part 1 Time | Part 1 Rank | Part 2 Time | Part 2 Rank |
|---|---|---|---|
| 00:51:50 (~00:23:XX) | 9,125 | >24h (~02:39:22) | 51,336 |
I finished Part 1 while flying home from RSNA. I had a connecting flight in San Francisco, which didn't reach laptop-available altitude until nearly 20 minutes into the flight. By then, I still had to purchase internet, get set up, etc.
This probably makes me the highest person in the world to finish Part 1 😜.
Finished Part 1 at 29,790ft
I didn't really work on Part 2 until Saturday, December 7th (after Day 7), as I was still recovering from RSNA.
Part 2 took a bit more time than I would've liked, I had some bugs in my initial solution. I ended up reworking my code entirely to first get all of the possible blocking locations, then iterate through the differnet maps checking for loops. The code takes awhile to run, but does complete in a reasonable time (<2 minutes on my laptop with the animation delay set to minimal).