Nadat je alle mogelijke routes bekeken hebt, realiseer je je dat je misschien tijd hebt om één enkele kleine grot tweemaal te bezoeken. Meer specifiek: grote grotten kan je nog steeds zoveel bezoeken als je wil, je kunt één kleine grot tweemaal bezoeken en alle andere kleine grotten mag je hoogstens één keer bezoeken. De grotten met de naam start en end moeten echter elk juist één keer bezocht worden: nadat je de start-grot hebt verlaten, mag je er niet meer naar terugkeren, en als je eenmaal de end-grot bereikt hebt, dan eindigt de route daar onmiddellijk.
Er zijn nu 36 mogelijke routes door het eerste voorbeeld dat we hiervoor gebruikt hebben:
start,A,b,A,b,A,c,A,end
start,A,b,A,b,A,end
start,A,b,A,b,end
start,A,b,A,c,A,b,A,end
start,A,b,A,c,A,b,end
start,A,b,A,c,A,c,A,end
start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,d,b,A,c,A,end
start,A,b,d,b,A,end
start,A,b,d,b,end
start,A,b,end
start,A,c,A,b,A,b,A,end
start,A,c,A,b,A,b,end
start,A,c,A,b,A,c,A,end
start,A,c,A,b,A,end
start,A,c,A,b,d,b,A,end
start,A,c,A,b,d,b,end
start,A,c,A,b,end
start,A,c,A,c,A,b,A,end
start,A,c,A,c,A,b,end
start,A,c,A,c,A,end
start,A,c,A,end
start,A,end
start,b,A,b,A,c,A,end
start,b,A,b,A,end
start,b,A,b,end
start,b,A,c,A,b,A,end
start,b,A,c,A,b,end
start,b,A,c,A,c,A,end
start,b,A,c,A,end
start,b,A,end
start,b,d,b,A,c,A,end
start,b,d,b,A,end
start,b,d,b,end
start,b,end
Er lopen nu 103 routes door het iets grotere voorbeeld, en er lopen 3509 routes door het nog grotere voorbeeld.
Hoeveel routes lopen er door een grottenstelsel op basis van deze nieuwe regels? Bepaal dit op de volgende manier:
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.In deze interactieve sessie gaan we ervan uit dat de tekstbestanden caves01.txt1, caves02.txt2 en caves03.txt3 zich in de huidige directory bevinden.
>>> paths('caves01.txt')
36
>>> paths('caves02.txt')
103
>>> paths('caves03.txt')
3509