Reptes
Repte 12 — El laberint ★★★ Avançat
En Karel és a l'entrada d'un laberint. Alguna part del laberint conté
una perla que marca la sortida. El laberint té sempre
solució: sempre existeix un camí que porta en Karel fins a la perla.
La teva feina: escriu un programa que funcioni per a qualsevol laberint, sigui quina sigui la seva forma o mida. El teu codi no pot assumir res sobre la geometria concreta del laberint.
Restricció important: no pots codificar el camí pas a pas. Has de descobrir un algorisme genèric que segueixi les parets fins trobar la sortida.
La teva feina: escriu un programa que funcioni per a qualsevol laberint, sigui quina sigui la seva forma o mida. El teu codi no pot assumir res sobre la geometria concreta del laberint.
Restricció important: no pots codificar el camí pas a pas. Has de descobrir un algorisme genèric que segueixi les parets fins trobar la sortida.
💡 Pista — la regla de la mà dreta
Imagina que poses la mà dreta a la paret del laberint i camines sempre
mantenint el contacte amb ella. Quan la paret acaba (la dreta és lliure),
gires a la dreta i avances. Si la paret continua però el davant és lliure,
avances recte. Si tens paret tant a la dreta com al davant, gires a
l'esquerra (però no avances: potser ara el davant és lliure i
caldrà tornar a comprovar). Aquesta regla garanteix que trobaràs la
sortida en qualsevol laberint simplement connexe.
💡 Pista — un sol pas, repetit moltes vegades
La clau és definir una funció
Dins de
pas() que implementi
exactament un pas de la regla de la mà dreta, i repetir-la mentre
en Karel no sigui a la sortida:
while not pearl_here(): pas()Dins de
pas() tens tres casos: dreta lliure, dreta ocupada
però davant lliure, i dreta i davant ocupats. Cada cas fa una acció
diferent. Pots usar right_is_clear(),
front_is_clear() i turn_right() juntament
amb les funcions que ja coneixes.