part1 (2854B)
1--- Day 12: Passage Pathing --- 2 3With your submarine's subterranean subsystems subsisting suboptimally, the only way you're getting 4out of this cave anytime soon is by finding a path yourself. Not just [1m[97ma[0m path - the only way to know 5if you've found the [1m[97mbest[0m path is to find [1m[97mall[0m of them. 6 7Fortunately, the sensors are still mostly working, and so you build a rough map of the remaining 8caves (your puzzle input). For example: 9 10start-A 11start-b 12A-c 13A-b 14b-d 15A-end 16b-end 17 18This is a list of how all of the caves are connected. You start in the cave named start, and your 19destination is the cave named end. An entry like b-d means that cave b is connected to cave d - that 20is, you can move between them. 21 22So, the above cave system looks roughly like this: 23 24 start 25 / \ 26c--A-----b--d 27 \ / 28 end 29 30Your goal is to find the number of distinct [1m[97mpaths[0m that start at start, end at end, and don't visit 31small caves more than once. There are two types of caves: [1m[97mbig[0m caves (written in uppercase, like A) 32and [1m[97msmall[0m caves (written in lowercase, like b). It would be a waste of time to visit any small cave 33more than once, but big caves are large enough that it might be worth visiting them multiple times. 34So, all paths you find should [1m[97mvisit small caves at most once[0m, and can [1m[97mvisit big caves any number of 35times[0m. 36 37Given these rules, there are [1m[97m10[0m paths through this example cave system: 38 39start,A,b,A,c,A,end 40start,A,b,A,end 41start,A,b,end 42start,A,c,A,b,A,end 43start,A,c,A,b,end 44start,A,c,A,end 45start,A,end 46start,b,A,c,A,end 47start,b,A,end 48start,b,end 49 50(Each line in the above list corresponds to a single path; the caves visited by that path are listed 51in the order they are visited and separated by commas.) 52 53Note that in this cave system, cave d is never visited by any path: to do so, cave b would need to 54be visited twice (once on the way to cave d and a second time when returning from cave d), and since 55cave b is small, this is not allowed. 56 57Here is a slightly larger example: 58 59dc-end 60HN-start 61start-kj 62dc-start 63dc-HN 64LN-dc 65HN-end 66kj-sa 67kj-HN 68kj-dc 69 70The 19 paths through it are as follows: 71 72start,HN,dc,HN,end 73start,HN,dc,HN,kj,HN,end 74start,HN,dc,end 75start,HN,dc,kj,HN,end 76start,HN,end 77start,HN,kj,HN,dc,HN,end 78start,HN,kj,HN,dc,end 79start,HN,kj,HN,end 80start,HN,kj,dc,HN,end 81start,HN,kj,dc,end 82start,dc,HN,end 83start,dc,HN,kj,HN,end 84start,dc,end 85start,dc,kj,HN,end 86start,kj,HN,dc,HN,end 87start,kj,HN,dc,end 88start,kj,HN,end 89start,kj,dc,HN,end 90start,kj,dc,end 91 92Finally, this even larger example has 226 paths through it: 93 94fs-end 95he-DX 96fs-he 97start-DX 98pj-DX 99end-zg 100zg-sl 101zg-pj 102pj-he 103RW-he 104fs-DX 105pj-RW 106zg-RW 107start-pj 108he-WI 109zg-he 110pj-fs 111start-RW 112 113[1m[97mHow many paths through this cave system are there that visit small caves at most once?[0m 114 115