aoc-2019-c

Advent of Code 2019 Solutions in C
git clone https://git.sinitax.com/sinitax/aoc-2019-c
Log | Files | Refs | README | sfeed.txt

part2 (3860B)

      1--- Part Two ---
      2
      3You arrive at the vault only to discover that there is not one vault, but four - each with its own
      4entrance.
      5
      6On your map, find the area in the middle that looks like this:
      7
      8...
      9.@.
     10...
     11
     12Update your map to instead use the correct data:
     13
     14@#@
     15###
     16@#@
     17
     18This change will split your map into four separate sections, each with its own entrance:
     19
     20#######       #######
     21#a.#Cd#       #a.#Cd#
     22##...##       ##@#@##
     23##.@.##  -->  #######
     24##...##       ##@#@##
     25#cB#Ab#       #cB#Ab#
     26#######       #######
     27
     28Because some of the keys are for doors in other vaults, it would take much too long to collect all
     29of the keys by yourself.  Instead, you deploy four remote-controlled robots. Each starts at one of
     30the entrances (@).
     31
     32Your goal is still to collect all of the keys in the fewest steps, but now, each robot has its own
     33position and can move independently.  You can only remotely control a single robot at a time.
     34Collecting a key instantly unlocks any corresponding doors, regardless of the vault in which the key
     35or door is found.
     36
     37For example, in the map above, the top-left robot first collects key a, unlocking door A in the
     38bottom-right vault:
     39
     40#######
     41#@.#Cd#
     42##.#@##
     43#######
     44##@#@##
     45#cB#.b#
     46#######
     47
     48Then, the bottom-right robot collects key b, unlocking door B in the bottom-left vault:
     49
     50#######
     51#@.#Cd#
     52##.#@##
     53#######
     54##@#.##
     55#c.#.@#
     56#######
     57
     58Then, the bottom-left robot collects key c:
     59
     60#######
     61#@.#.d#
     62##.#@##
     63#######
     64##.#.##
     65#@.#.@#
     66#######
     67
     68Finally, the top-right robot collects key d:
     69
     70#######
     71#@.#.@#
     72##.#.##
     73#######
     74##.#.##
     75#@.#.@#
     76#######
     77
     78In this example, it only took 8 steps to collect all of the keys.
     79
     80Sometimes, multiple robots might have keys available, or a robot might have to wait for multiple
     81keys to be collected:
     82
     83###############
     84#d.ABC.#.....a#
     85######@#@######
     86###############
     87######@#@######
     88#b.....#.....c#
     89###############
     90
     91First, the top-right, bottom-left, and bottom-right robots take turns collecting keys a, b, and c, a
     92total of 6 + 6 + 6 = 18 steps. Then, the top-left robot can access key d, spending another 6 steps;
     93collecting all of the keys here takes a minimum of 24 steps.
     94
     95Here's a more complex example:
     96
     97#############
     98#DcBa.#.GhKl#
     99#.###@#@#I###
    100#e#d#####j#k#
    101###C#@#@###J#
    102#fEbA.#.FgHi#
    103#############
    104
    105
    106 - Top-left robot collects key a.
    107
    108 - Bottom-left robot collects key b.
    109
    110 - Top-left robot collects key c.
    111
    112 - Bottom-left robot collects key d.
    113
    114 - Top-left robot collects key e.
    115
    116 - Bottom-left robot collects key f.
    117
    118 - Bottom-right robot collects key g.
    119
    120 - Top-right robot collects key h.
    121
    122 - Bottom-right robot collects key i.
    123
    124 - Top-right robot collects key j.
    125
    126 - Bottom-right robot collects key k.
    127
    128 - Top-right robot collects key l.
    129
    130
    131In the above example, the fewest steps to collect all of the keys is 32.
    132
    133Here's an example with more choices:
    134
    135#############
    136#g#f.D#..h#l#
    137#F###e#E###.#
    138#dCba@#@BcIJ#
    139#############
    140#nK.L@#@G...#
    141#M###N#H###.#
    142#o#m..#i#jk.#
    143#############
    144
    145One solution with the fewest steps is:
    146
    147
    148 - Top-left robot collects key e.
    149
    150 - Top-right robot collects key h.
    151
    152 - Bottom-right robot collects key i.
    153
    154 - Top-left robot collects key a.
    155
    156 - Top-left robot collects key b.
    157
    158 - Top-right robot collects key c.
    159
    160 - Top-left robot collects key d.
    161
    162 - Top-left robot collects key f.
    163
    164 - Top-left robot collects key g.
    165
    166 - Bottom-right robot collects key k.
    167
    168 - Bottom-right robot collects key j.
    169
    170 - Top-right robot collects key l.
    171
    172 - Bottom-left robot collects key n.
    173
    174 - Bottom-left robot collects key m.
    175
    176 - Bottom-left robot collects key o.
    177
    178
    179This example requires at least 72 steps to collect all keys.
    180
    181After updating your map and using the remote-controlled robots, what is the fewest steps necessary
    182to collect all of the keys?
    183
    184