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)