aoc-2018-python

Advent of Code 2018 Solutions in Python
git clone https://git.sinitax.com/sinitax/aoc-2018-python
Log | Files | Refs | README | sfeed.txt

part1 (6469B)


      1--- Day 20: A Regular Map ---
      2
      3While you were learning about instruction pointers, the Elves made considerable progress. When you
      4look up, you discover that the North Pole base construction project has completely surrounded you.
      5
      6The area you are in is made up entirely of rooms and doors. The rooms are arranged in a grid, and
      7rooms only connect to adjacent rooms when a door is present between them.
      8
      9For example, drawing rooms as ., walls as #, doors as | or -, your current position as X, and where
     10north is up, the area you're in might look like this:
     11
     12#####
     13#.|.#
     14#-###
     15#.|X#
     16#####
     17
     18You get the attention of a passing construction Elf and ask for a map. "I don't have time to draw
     19out a map of this place - it's huge. Instead, I can give you directions to every room in the
     20facility!" He writes down some directions on a piece of parchment and runs off. In the example
     21above, the instructions might have been ^WNE$, a regular expression or "regex" (your puzzle input).
     22
     23The regex matches routes (like WNE for "west, north, east") that will take you from your current
     24room through various doors in the facility. In aggregate, the routes will take you through
     25every door in the facility at least once; mapping out all of these routes will let you build a
     26proper map and find your way around.
     27
     28^ and $ are at the beginning and end of your regex; these just mean that the regex doesn't match
     29anything outside the routes it describes. (Specifically, ^ matches the start of the route, and $
     30matches the end of it.) These characters will not appear elsewhere in the regex.
     31
     32The rest of the regex matches various sequences of the characters N (north), S (south), E (east),
     33and W (west). In the example above, ^WNE$ matches only one route, WNE, which means you can move
     34west, then north, then east from your current position. Sequences of letters like this always match
     35that exact route in the same order.
     36
     37Sometimes, the route can branch. A branch is given by a list of options separated by pipes (|) and
     38wrapped in parentheses. So, ^N(E|W)N$ contains a branch: after going north, you must choose to go
     39either east or west before finishing your route by going north again. By tracing out the possible
     40routes after branching, you can determine where the doors are and, therefore, where the rooms are in
     41the facility.
     42
     43For example, consider this regex: ^ENWWW(NEEE|SSE(EE|N))$
     44
     45This regex begins with ENWWW, which means that from your current position, all routes must begin by
     46moving east, north, and then west three times, in that order. After this, there is a branch.  Before
     47you consider the branch, this is what you know about the map so far, with doors you aren't sure
     48about marked with a ?:
     49
     50#?#?#?#?#
     51?.|.|.|.?
     52#?#?#?#-#
     53    ?X|.?
     54    #?#?#
     55
     56After this point, there is (NEEE|SSE(EE|N)). This gives you exactly two options: NEEE and SSE(EE|N).
     57By following NEEE, the map now looks like this:
     58
     59#?#?#?#?#
     60?.|.|.|.?
     61#-#?#?#?#
     62?.|.|.|.?
     63#?#?#?#-#
     64    ?X|.?
     65    #?#?#
     66
     67Now, only SSE(EE|N) remains. Because it is in the same parenthesized group as NEEE, it starts from
     68the same room NEEE started in. It states that starting from that point, there exist doors which will
     69allow you to move south twice, then east; this ends up at another branch. After that, you can either
     70move east twice or north once. This information fills in the rest of the doors:
     71
     72#?#?#?#?#
     73?.|.|.|.?
     74#-#?#?#?#
     75?.|.|.|.?
     76#-#?#?#-#
     77?.?.?X|.?
     78#-#-#?#?#
     79?.|.|.|.?
     80#?#?#?#?#
     81
     82Once you've followed all possible routes, you know the remaining unknown parts are all walls,
     83producing a finished map of the facility:
     84
     85#########
     86#.|.|.|.#
     87#-#######
     88#.|.|.|.#
     89#-#####-#
     90#.#.#X|.#
     91#-#-#####
     92#.|.|.|.#
     93#########
     94
     95Sometimes, a list of options can have an empty option, like (NEWS|WNSE|). This means that routes at
     96this point could effectively skip the options in parentheses and move on immediately.  For example,
     97consider this regex and the corresponding map:
     98
     99^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$
    100
    101###########
    102#.|.#.|.#.#
    103#-###-#-#-#
    104#.|.|.#.#.#
    105#-#####-#-#
    106#.#.#X|.#.#
    107#-#-#####-#
    108#.#.|.|.|.#
    109#-###-###-#
    110#.|.|.#.|.#
    111###########
    112
    113This regex has one main route which, at three locations, can optionally include additional detours
    114and be valid: (NEWS|), (WNSE|), and (SWEN|). Regardless of which option is taken, the route
    115continues from the position it is left at after taking those steps. So, for example, this regex
    116matches all of the following routes (and more that aren't listed here):
    117
    118
    119 - ENNWSWWSSSEENEENNN
    120
    121 - ENNWSWWNEWSSSSEENEENNN
    122
    123 - ENNWSWWNEWSSSSEENEESWENNNN
    124
    125 - ENNWSWWSSSEENWNSEEENNN
    126
    127
    128By following the various routes the regex matches, a full map of all of the doors and rooms in the
    129facility can be assembled.
    130
    131To get a sense for the size of this facility, you'd like to determine which room is
    132furthest from you: specifically, you would like to find the room for which the shortest path to that
    133room would require passing through the most doors.
    134
    135
    136 - In the first example (^WNE$), this would be the north-east corner 3 doors away.
    137
    138 - In the second example (^ENWWW(NEEE|SSE(EE|N))$), this would be the south-east corner
    13910 doors away.
    140
    141 - In the third example (^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$), this would be the north-east
    142corner 18 doors away.
    143
    144
    145Here are a few more examples:
    146
    147Regex: ^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$
    148Furthest room requires passing 23 doors
    149
    150#############
    151#.|.|.|.|.|.#
    152#-#####-###-#
    153#.#.|.#.#.#.#
    154#-#-###-#-#-#
    155#.#.#.|.#.|.#
    156#-#-#-#####-#
    157#.#.#.#X|.#.#
    158#-#-#-###-#-#
    159#.|.#.|.#.#.#
    160###-#-###-#-#
    161#.|.#.|.|.#.#
    162#############
    163
    164Regex: ^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$
    165Furthest room requires passing 31 doors
    166
    167###############
    168#.|.|.|.#.|.|.#
    169#-###-###-#-#-#
    170#.|.#.|.|.#.#.#
    171#-#########-#-#
    172#.#.|.|.|.|.#.#
    173#-#-#########-#
    174#.#.#.|X#.|.#.#
    175###-#-###-#-#-#
    176#.|.#.#.|.#.|.#
    177#-###-#####-###
    178#.|.#.|.|.#.#.#
    179#-#-#####-#-#-#
    180#.#.|.|.|.#.|.#
    181###############
    182
    183What is the largest number of doors you would be required to pass through to reach a room? That is,
    184find the room for which the shortest path from your starting location to that room would require
    185passing through the most doors; what is the fewest doors you can pass through to reach it?
    186
    187