Il labirinto di Kangouria

di

Kangourou dell’Informatica

Nel famigerato labirinto di Kangouria si perdono tutti, tranne coloro che conoscono il segreto: se siete nella stanza col numero n, imboccando la porta a sinistra vi ritroverete nella stanza col numero 2n (il doppio di n), imboccando la porta a destra finirete invece nella stanza col numero 1+2n (uno più il doppio di n).
Il guardiano vi rivela che nella stanza 69 si trova il tesoro.
Qual è il percorso per raggiungerlo partendo dalla stanza numero 1?
Fate attenzione: se sbagliate percorso sarete catturati da un mostro famelico e dovrete ripartire dall’inizio, perdendo una delle vostre 3 vite.

Vedi la discussione

1

Il codice

  1. Genera tutti i percorsi
  2. Se il percorso porta all’obiettivo verrà stampato: ['S','S','S','D','S','D']
  3. Sostituendo l’istruzione print(path) con print(str().join(path)) visualizzerà la soluzione come stringa: SSSDSD
START =1
FINISH=69
path  =[]
pos   =START

def trial(): 
    global pos 
    if(pos == FINISH): 
        print(path)      # print(str().join(path))
    elif(pos < FINISH): 
        pos=2*pos 
        path.append('S') 
        trial() 
        path.pop() 
        pos=pos+1 
        path.append('D') 
        trial() 
        path.pop() 
        pos=pos-1 
        pos=pos//2 

trial()

2

Lavorare direttamente con le stringhe semplifica il codice

  • utilizza una stringa per la soluzione: path=""
  • si ottiene come risultato la stringa SSSDSD

ma

  • è necessario cambiare le operazioni
  • il codice sarà più lento (perché la stringa è una struttura dati immutabile)
START =1 
FINISH=69 
path  ="" 
pos   =START 

def trial(): 
    global path,pos 
    if(pos == FINISH): 
        print(path) 
    elif(pos < FINISH): 
        pos=2*pos 
        path+='S' 
        trial() 
        path=path[:len(path)-1] 
        pos=pos+1 
        path+='D' 
        trial() 
        path=path[:len(path)-1] 
        pos=pos-1 
        pos=pos//2 

trial()

3

Dopo attenta analisi del problema…

START =1
FINISH=69
path  =[]
pos   =FINISH

while(pos != START):
    q=pos//2 
    r=pos%2

    pos=q

    if(r == 0): path = ['S'] + path
    else:       path = ['D'] + path

print(path)