Nu het ondergrond-subsysteem van de onderzeeër suboptimaal blijkt te presteren, is de enige manier om snel uit deze grot te geraken om zelf een route te vinden. Niet alleen een route - de enige manier om te weten of je de beste route gevonden hebt, is door ze allemaal te vinden.

Gelukkig werken de meeste sensoren nog, en dus bouw je een ruwe kaart van de overblijvende grotten (de invoer van deze opgave). Bijvoorbeeld:

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

Dit is een lijst van hoe alle grotten met elkaar verbonden zijn. Je begint in de grot die aangeduid wordt met start, en de uitgang bevindt zich in de grot die aangeduid wordt met end. Een regel zoals b-d betekent dat grot b verbonden is met grot d - wat wil zeggen dat je van de ene naar de andere grot kan gaan.

Het voorgaande grottenstelsel ziet er dus ongeveer zo uit:

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

Je opdracht bestaat erin om het aantal verschillende routes te vinden die beginnen bij start, eindigen bij end, en kleine grotten niet meer dan één keer bezoeken. Er zijn immers twee soorten grotten: grote grotten (geschreven in hoofdletters, zoals A) en kleine grotten (geschreven in kleine letters, zoals b). Het zou tijdverspilling zijn om een kleine grot meer dan één keer te bezoeken, maar grote grotten zijn groot genoeg om ze meerdere keren te bezoeken. Alle routes die je moet vinden mogen dus maximaal één keer kleine grotten bezoeken, en kunnen grote grotten een willekeurig aantal keren bezoeken.

Op basis van deze regels zijn er 10 routes door dit voorbeeld van een grottenstelsel:

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

(Elke regel in bovenstaande lijst correspondeert met één enkele route. De grotten waarlangs de route loopt worden weergegeven in de volgorde waarin ze bezocht worden, en van elkaar gescheiden door komma’s.)

Met op dat geen enkele route doorheen dit grottenstelsel langs grot d passeert: om dit te doen zou de route twee keer langs grot b moeten passeren (één keer op weg naar grot d en een tweede keer bij terugkeer uit grot d), en omdat grot b een kleine grot is, is dit niet toegestaan.

Dit is een iets groter voorbeeld:

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

Dit zijn de 19 routes doorheen dit grottenstelsel:

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

Ten slotte zijn er 226 routes doorheen dit nog grotere voorbeeld:

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

Opgave

Hoeveel routes zijn er doorheen een grottenstelsel, die de kleine grotten hoogstens één keer bezoeken? Bepaal dit op de volgende manier:

• Schrijf een functie paths waaraan de padnaam (str) moet doorgegeven worden van een tekstbestand met een ruwe kaart van een grottenstelsel. De functie moet het aantal routes (int) doorheen dit grottenstelsel teruggeven.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden caves01.txt¹, caves02.txt² en caves03.txt³ zich in de huidige directory bevinden.

>>> paths('caves01.txt')
10
>>> paths('caves02.txt')
19
>>> paths('caves03.txt')
226