aoc-2021-rust

Advent of Code 2021 Solutions in Rust
git clone https://git.sinitax.com/sinitax/aoc-2021-rust
Log | Files | Refs | README | sfeed.txt

part2 (1509B)

      1--- Part Two ---
      2
      3After reviewing the available paths, you realize you might have time to visit a single small cave
      4twice. Specifically, big caves can be visited any number of times, a single small cave can be
      5visited at most twice, and the remaining small caves can be visited at most once. However, the caves
      6named start and end can only be visited exactly once each: once you leave the start cave, you may
      7not return to it, and once you reach the end cave, the path must end immediately.
      8
      9Now, the 36 possible paths through the first example above are:
     10
     11start,A,b,A,b,A,c,A,end
     12start,A,b,A,b,A,end
     13start,A,b,A,b,end
     14start,A,b,A,c,A,b,A,end
     15start,A,b,A,c,A,b,end
     16start,A,b,A,c,A,c,A,end
     17start,A,b,A,c,A,end
     18start,A,b,A,end
     19start,A,b,d,b,A,c,A,end
     20start,A,b,d,b,A,end
     21start,A,b,d,b,end
     22start,A,b,end
     23start,A,c,A,b,A,b,A,end
     24start,A,c,A,b,A,b,end
     25start,A,c,A,b,A,c,A,end
     26start,A,c,A,b,A,end
     27start,A,c,A,b,d,b,A,end
     28start,A,c,A,b,d,b,end
     29start,A,c,A,b,end
     30start,A,c,A,c,A,b,A,end
     31start,A,c,A,c,A,b,end
     32start,A,c,A,c,A,end
     33start,A,c,A,end
     34start,A,end
     35start,b,A,b,A,c,A,end
     36start,b,A,b,A,end
     37start,b,A,b,end
     38start,b,A,c,A,b,A,end
     39start,b,A,c,A,b,end
     40start,b,A,c,A,c,A,end
     41start,b,A,c,A,end
     42start,b,A,end
     43start,b,d,b,A,c,A,end
     44start,b,d,b,A,end
     45start,b,d,b,end
     46start,b,end
     47
     48The slightly larger example above now has 103 paths through it, and the even larger example now has
     493509 paths through it.
     50
     51Given these new rules, how many paths through this cave system are there?
     52
     53