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

part1 (3163B)

      1--- Day 18: Many-Worlds Interpretation ---
      2
      3As you approach Neptune, a planetary security system detects you and activates a giant tractor beam
      4on Triton!  You have no choice but to land.
      5
      6A scan of the local area reveals only one interesting feature: a massive underground vault.  You
      7generate a map of the tunnels (your puzzle input).  The tunnels are too narrow to move diagonally.
      8
      9Only one entrance (marked @) is present among the open passages (marked .) and stone walls (#), but
     10you also detect an assortment of keys (shown as lowercase letters) and doors (shown as uppercase
     11letters). Keys of a given letter open the door of the same letter: a opens A, b opens B, and so on. 
     12You aren't sure which key you need to disable the tractor beam, so you'll need to collect all of
     13them.
     14
     15For example, suppose you have the following map:
     16
     17#########
     18#b.A.@.a#
     19#########
     20
     21Starting from the entrance (@), you can only access a large door (A) and a key (a). Moving toward
     22the door doesn't help you, but you can move 2 steps to collect the key, unlocking A in the process:
     23
     24#########
     25#b.....@#
     26#########
     27
     28Then, you can move 6 steps to collect the only other key, b:
     29
     30#########
     31#@......#
     32#########
     33
     34So, collecting every key took a total of 8 steps.
     35
     36Here is a larger example:
     37
     38########################
     39#f.D.E.e.C.b.A.@.a.B.c.#
     40######################.#
     41#d.....................#
     42########################
     43
     44The only reasonable move is to take key a and unlock door A:
     45
     46########################
     47#f.D.E.e.C.b.....@.B.c.#
     48######################.#
     49#d.....................#
     50########################
     51
     52Then, do the same with key b:
     53
     54########################
     55#f.D.E.e.C.@.........c.#
     56######################.#
     57#d.....................#
     58########################
     59
     60...and the same with key c:
     61
     62########################
     63#f.D.E.e.............@.#
     64######################.#
     65#d.....................#
     66########################
     67
     68Now, you have a choice between keys d and e.  While key e is closer, collecting it now would be
     69slower in the long run than collecting key d first, so that's the best choice:
     70
     71########################
     72#f...E.e...............#
     73######################.#
     74#@.....................#
     75########################
     76
     77Finally, collect key e to unlock door E, then collect key f, taking a grand total of 86 steps.
     78
     79Here are a few more examples:
     80
     81
     82 - ########################
     83#...............b.C.D.f#
     84#.######################
     85#.....@.a.B.c.d.A.e.F.g#
     86########################
     87
     88Shortest path is 132 steps: b, a, c, d, f, e, g
     89
     90
     91 - #################
     92#i.G..c...e..H.p#
     93########.########
     94#j.A..b...f..D.o#
     95########@########
     96#k.E..a...g..B.n#
     97########.########
     98#l.F..d...h..C.m#
     99#################
    100
    101Shortest paths are 136 steps;one is: a, f, b, j, g, n, h, d, l, o, e, p, c, i, k, m
    102
    103
    104 - ########################
    105#@..............ac.GI.b#
    106###d#e#f################
    107###A#B#C################
    108###g#h#i################
    109########################
    110
    111Shortest paths are 81 steps; one is: a, c, f, i, d, g, b, e, h
    112
    113
    114
    115How many steps is the shortest path that collects all of the keys?
    116
    117