VP 37: Paths (30 extra)

What You Need

Any computer with Python 3. You can also use an online Python environment, such as https://colab.research.google.com

All Paths

Your task is to find the best path out of a set of underground caves and tunnels. The only way to know if you've found the best path is to find all of them.

You have a list of how all of the caves are connected, like this:

start-A start-b A-c A-b b-d A-end b-end

You start in the cave named start, and your destination is the cave named end. An entry like b-d means that cave b is connected to cave d - that is, you can move between them.

So, the above cave system looks roughly like this:

start / \ c--A-----b--d \ / end

All Paths

Your first task is to find all paths originating from start without visiting any cave more than once.

For the example cave system above, there are 17 possible paths:

start start,A start,b start,A,c start,A,b start,A,end start,b,A start,b,d start,b,end start,A,b,d start,A,b,end start,A,end,b start,b,A,c start,b,A,end start,b,end,A start,A,end,b,d start,b,end,A,c

Here is a slightly larger example:

dc-end HN-start start-kj dc-start dc-HN LN-dc HN-end kj-sa kj-HN kj-dc

Here's a diagram of this cave structure:

The 46 paths through it are as follows:

start start,HN start,kj start,dc start,HN,dc start,HN,end start,HN,kj start,kj,sa start,kj,HN start,kj,dc start,dc,end start,dc,HN start,dc,LN start,dc,kj start,HN,dc,end start,HN,dc,LN start,HN,dc,kj start,HN,end,dc start,HN,kj,sa start,HN,kj,dc start,kj,HN,dc start,kj,HN,end start,kj,dc,end start,kj,dc,HN start,kj,dc,LN start,dc,end,HN start,dc,HN,end start,dc,HN,kj start,dc,kj,sa start,dc,kj,HN start,HN,dc,kj,sa start,HN,end,dc,LN start,HN,end,dc,kj start,HN,kj,dc,end start,HN,kj,dc,LN start,kj,HN,dc,end start,kj,HN,dc,LN start,kj,HN,end,dc start,kj,dc,end,HN start,kj,dc,HN,end start,dc,end,HN,kj start,dc,HN,kj,sa start,dc,kj,HN,end start,HN,end,dc,kj,sa start,kj,HN,end,dc,LN start,dc,end,HN,kj,sa

Finally, this even larger example has 610 paths through it:

fs-end he-DX fs-he start-DX pj-DX end-zg zg-sl zg-pj pj-he RW-he fs-DX pj-RW zg-RW start-pj he-WI zg-he pj-fs start-RW

VP 37.1: All Paths (10 pts)
Use this data:
end-MY MY-xc ho-NF start-ho NF-xc NF-yf end-yf xc-TP MY-qo yf-TP dc-NF dc-xc start-dc yf-MY MY-ho EM-uh xc-yf ho-dc uh-NF yf-ho end-uh start-NF
Count all the paths originating from start without visiting any cave more than once.
That's the flag.

Large Caves

Now your goal is to find the number of distinct paths that start at start, end at end, and don't visit small caves more than once. There are two types of caves: big caves (written in uppercase, like A) and small caves (written in lowercase, like b). It would be a waste of time to visit any small cave more than once, but big caves are large enough that it might be worth visiting them multiple times. So, all paths you find should visit small caves at most once, and can visit big caves any number of times.

Consider the first example above:

start / \ c--A-----b--d \ / end

Given these rules, there are 10 paths through this example cave system:

start,A,end start,b,end start,A,b,end start,b,A,end start,A,c,A,end start,A,b,A,end start,A,c,A,b,end start,b,A,c,A,end start,A,c,A,b,A,end start,A,b,A,c,A,end

Note that in this cave system, cave d is never visited by any path: to do so, cave b would need to be visited twice (once on the way to cave d and a second time when returning from cave d), and since cave b is small, this is not allowed.

Here is a slightly larger example:

dc-end HN-start start-kj dc-start dc-HN LN-dc HN-end kj-sa kj-HN kj-dc

The 19 paths through it are as follows:

start,HN,end start,dc,end start,HN,dc,end start,kj,HN,end start,kj,dc,end start,dc,HN,end start,HN,dc,HN,end start,HN,kj,HN,end start,HN,kj,dc,end start,kj,HN,dc,end start,kj,dc,HN,end start,dc,kj,HN,end start,HN,dc,kj,HN,end start,HN,kj,HN,dc,end start,HN,kj,dc,HN,end start,kj,HN,dc,HN,end start,dc,HN,kj,HN,end start,HN,dc,HN,kj,HN,end start,HN,kj,HN,dc,HN,end

Finally, this even larger example has 226 paths through it:

fs-end he-DX fs-he start-DX pj-DX end-zg zg-sl zg-pj pj-he RW-he fs-DX pj-RW zg-RW start-pj he-WI zg-he pj-fs start-RW

How many paths through this cave system are there that visit small caves at most once?

VP 37.2: Large Caves (10 pts)
Use this data:
end-MY MY-xc ho-NF start-ho NF-xc NF-yf end-yf xc-TP MY-qo yf-TP dc-NF dc-xc start-dc yf-MY MY-ho EM-uh xc-yf ho-dc uh-NF yf-ho end-uh start-NF
Count all the paths originating from start to end without visiting any lopwercase cave more than once.
That's the flag.

Visiting a Small Cave Twice

After reviewing the available paths, you realize you might have time to visit a single small cave twice. Specifically, big caves can be visited any number of times, a single small cave can be visited at most twice, and the remaining small caves can be visited at most once. However, the caves named start and end can only be visited exactly once each: once you leave the start cave, you may not return to it, and once you reach the end cave, the path must end immediately.

Now, the 36 possible paths through the first example above are:

start,A,end start,b,end start,A,b,end start,b,A,end start,A,c,A,end start,A,b,A,end start,b,A,b,end start,b,d,b,end start,A,c,A,b,end start,A,b,A,b,end start,A,b,d,b,end start,b,A,c,A,end start,b,A,b,A,end start,b,d,b,A,end start,A,c,A,c,A,end start,A,c,A,b,A,end start,A,b,A,c,A,end start,A,b,A,b,A,end start,A,b,d,b,A,end start,b,A,c,A,b,end start,A,c,A,c,A,b,end start,A,c,A,b,A,b,end start,A,c,A,b,d,b,end start,A,b,A,c,A,b,end start,b,A,c,A,c,A,end start,b,A,c,A,b,A,end start,b,A,b,A,c,A,end start,b,d,b,A,c,A,end start,A,c,A,c,A,b,A,end start,A,c,A,b,A,c,A,end start,A,c,A,b,A,b,A,end start,A,c,A,b,d,b,A,end start,A,b,A,c,A,c,A,end start,A,b,A,c,A,b,A,end start,A,b,A,b,A,c,A,end start,A,b,d,b,A,c,A,end

The slightly larger example above now has 103 paths through it, and the even larger example now has 3509 paths through it.

VP 37.3: Visiting a Small Cave Twice (10 pts)
Use this data:
end-MY MY-xc ho-NF start-ho NF-xc NF-yf end-yf xc-TP MY-qo yf-TP dc-NF dc-xc start-dc yf-MY MY-ho EM-uh xc-yf ho-dc uh-NF yf-ho end-uh start-NF
Count all the paths originating from start to end without visiting any lopwercase cave more than once.
That's the flag.

Source

Adapted from the Advent of Code.

Posted 11-1-24