I'll admit right now that this problem has me confused after 1 reading. It's taken me a few reads of the example inputs to try to work out what is being asked of us here.
The problem goes like this, there's a chaotic confusing cluster of caves through which we must carefully choose a course.
We can represent the caves as an n-tree, that's a tree structure where there are n possible paths away from any given node to another node.
We've got 2 special nodes, start and end, and we want to find all possible paths from start to end.
We've also got two cave types, big caves and little caves, represented by capital letters and lowercase letters.
When we are trying to build a potential path, we can only visit any given little cave once.
But, to add confusion, we aren't looking for one path, like the longest path, or the shortest path, we are looking for all possible paths.
This is going to end up using a similar kind of search algorithm that we've used in the last few days, we're going to have to start with the start node, and then were going to have to enumerate all of the connected nodes and add them to a potential path, and then we can visit each one, and keep repeating until there are no possible paths.
But we're going to have to bring some form of memoised path with us, so we don't just want to know that we can visit b, we need to know that we can visit B from start->A, because that's different from visiting from start. When we get to end, we can then say we've found a potential path, and store it in the list of paths.
Someone told me yesterday that writing out the algorithm in the text helped them understand what I was trying to do, so lets try that again
tovisit starts as a list of nodes with just Start in it
while tovisit has items
pop next node from tovisit
if node is Finish, add node.path to list of paths
otherwise
for each neighbour of node
path = node.visited + node
if neighbour is small and neighbour is not in node.visited
add neighbour and path to tovisitI think that algorithm should do it, it should at the start of our example, add (A, [start]) and (b, [start]) to the tovisit. It then gets (A, [start]) from the list, and pushes (c, [start, A]), (b, [start, A]), and (finish, [start, A]) to the tovisit list.
If we then picked the finish one, we'd add [start, A, finish] to paths, and pick another.
We could then pick c, and that would add (A, [start, A, c]), to the list.
Now at (A, [start, A, c]), when we checked the neighbours, we could add the b route, and the finish route, but when we try the c route, we'll see that c is in our path and skip it.
My biggest concern here is that if there was a network such that there's an A connected to a B, we'd have an infinite loop. Looking down the samples, there's no example where a big cave is connected to a big cave, so I'm going to trust that the network has a property such that no big cave is ever connected to another big cave directly.
Let's give it a try
## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()
Oh, some quick thoughts on data representations here.
We could use objects or namedtuples for this all, but I think in this case, we can probably build something much simpler. Our tree structure doesn't have to be an actual tree. In C++ or Java, I'd have made a Cave class that had a label, and then a list of pointers to other Caves to indicate connections.
But python has a natural built in dictionary type that works quite well in this case. What we'll have is a dictionary that is a mapping from cave to list of neighbour caves, so like this:
{
"start": ["A", "b"],
"A": ["start","finish", "b"],
"b": ["A", "finish"],
"finish": ["A", "b"]
}Note that we're tracking directions "bidirectionally", that's to say that A says it links to b and b says it links to A. We've not assumed that if A links to b that we can travel backwards, so we're being explicit about it.
Secondly, our nodes can be a simple data structure as well. We're going to store nodes as a tuple of cave name and list of caves visited, so `("A", ["start", "b", "A", "c"]).
I don't know why I call them nodes, to me they are nodes on the potential search tree, and I have no better name for them than that. Option maybe?
import collections
def parse_input(lines):
paths = collections.defaultdict(list)
for line in lines:
start,end = line.split("-")
paths[start].append(end)
paths[end].append(start)
return paths
assert parse_input(["A-b"]) == {"A":["b"], "b": ["A"]}
assert parse_input(["A-b", "b-c"]) == {"A":["b"], "b": ["A", "c"], "c": ["b"]}
Ok, we can build up our cave system, lets see if we can find a path through it then
def find_all_paths(caves):
paths = []
tovisit = [("start", [])]
while tovisit:
current_node = tovisit.pop()
if current_node[0] == "end":
paths.append(current_node[1]+[current_node[0]])
else:
for neighbour in caves[current_node[0]]:
if not neighbour.islower() or neighbour not in current_node[1]:
tovisit.append((neighbour, current_node[1]+[current_node[0]]))
return [",".join(path) for path in paths]
test_caves1 = parse_input("""start-A
start-b
A-c
A-b
b-d
A-end
b-end""".split("\n"))
test_paths1 = find_all_paths(test_caves1)
assert "start,A,b,A,c,A,end" in test_paths1
assert "start,A,b,A,end" in test_paths1
assert "start,A,end" in test_paths1
assert "start,A,c,A,end" in test_paths1
assert 10 == len(test_paths1)
Right, that seemed to work pretty much first time. I'm not happy about the current_node[1], current_node[0] syntax, but we'll come back and clean that up later on.
Let's try the other test cases we've been provided
test_caves2 = parse_input("""dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc""".split("\n"))
test_paths2 = find_all_paths(test_caves2)
assert "start,HN,dc,HN,kj,HN,end" in test_paths2
assert "start,dc,end" in test_paths2
assert "start,HN,kj,dc,HN,end" in test_paths2
assert 19 == len(test_paths2)
test_caves3 = parse_input("""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""".split("\n"))
test_paths3 = find_all_paths(test_caves3)
assert 226 == len(test_paths3)
Ok, lets try that on production data
caves = parse_input([line.strip() for line in open("day12.txt").readlines()])
paths = find_all_paths(caves)
print(len(paths))
5457
Ok, this is going to be a pain to refactor. We are now allowed to pick a single small cave that we can visit twice, with every other small cave only being allowed to visit once.
The best, nastiest way I can think to do this is to do our find paths algorithm, but iterate through each possible small cave and run the algorithm with that small cave as the "visit twice" option. But then we're going to have to merge the possible paths, so we need to find a way to do that.
First, on the merging, if we make the algorithm return a set of paths, then we can union them together. A set is simply an unordered list that can only contain any given item once. So having a set set(a, b, c) and getting the union of that with set(b,c,d) should result in set(a,b,c,d). Sets have other operations, but in this case that's all we want.
The main algorithm we've got wont change much. We'll pass in a "special cave", and when we check for whether we can add the cave, we'll check whether the cave is lower and has been visited, as well as if the cave is the special case and has been visited 0 or 1 times. I'm going to refactor out that logic into a function that can return True or False depending on whether we should be allowed to visit. I was considering this before since I thought we'd have something involving changing the visiting rules, but decided it was a premature optimisation.
First of all, lets prove we can do that refactor without breaking anything, we'll do both the set and the check_visit function.
def can_visit(caves, neighbour, path):
if neighbour.isupper(): # We can always visit big caves
return True
if neighbour not in path: # We've not been to this small cave before
return True
return False
def find_all_paths(caves):
paths = []
tovisit = [("start", [])]
while tovisit:
node, path = tovisit.pop()
path = path+[node]
if node == "end":
paths.append(path)
else:
for neighbour in caves[node]:
if can_visit(caves, neighbour, path):
tovisit.append((neighbour, path))
return set([",".join(path) for path in paths])
test_caves1 = parse_input("""start-A
start-b
A-c
A-b
b-d
A-end
b-end""".split("\n"))
test_paths1 = find_all_paths(test_caves1)
assert 10 == len(test_paths1)
test_paths2 = find_all_paths(test_caves2)
assert 19 == len(test_paths2)
test_paths3 = find_all_paths(test_caves3)
assert 226 == len(test_paths3)
Ok, so we've refactored that out, and we've turned out paths into a set. We can now add a parameter to find_all_paths that is a doublevisitnode, and then we can pass that into everything. Finally we'll need a find_paths_with_double_visits that iterates through all the valid double visit nodes, and merges the paths together.
def can_visit(caves, neighbour, path, doublevisit):
if neighbour.isupper(): # We can always visit big caves
return True
if neighbour == doublevisit and path.count(doublevisit) < 2:
return True
if neighbour not in path: # We've not been to this small cave before
return True
return False
def find_all_paths(caves, doublevisit):
paths = []
tovisit = [("start", [])]
while tovisit:
node, path = tovisit.pop()
path = path+[node]
if node == "end":
paths.append(path)
else:
for neighbour in caves[node]:
if can_visit(caves, neighbour, path, doublevisit):
tovisit.append((neighbour, path))
return set([",".join(path) for path in paths])
def find_paths_with_double_visits(caves):
paths = set()
for doublevisit in caves:
if doublevisit not in ["start", "end"]:
paths |= find_all_paths(caves, doublevisit)
return paths
test_caves1 = parse_input("""start-A
start-b
A-c
A-b
b-d
A-end
b-end""".split("\n"))
test_paths1 = find_paths_with_double_visits(test_caves1)
assert 36 == len(test_paths1)
test_paths2 = find_paths_with_double_visits(test_caves2)
assert 103 == len(test_paths2)
test_paths3 = find_paths_with_double_visits(test_caves3)
assert 3509 == len(test_paths3)
Ok, lets try once more on production data
caves = parse_input([line.strip() for line in open("day12.txt").readlines()])
paths = find_paths_with_double_visits(caves)
print(len(paths))
128506