Quesiti da colloquio (2)
Runaround
Questo è un quesito posto a un mio collega durante un colloquio.
Una stringa runaround ha le seguenti caratteristiche
- E’ composta da N<10 elementi nell’alfabeto [1-9]
- Ogni elemento dell’alfabeto può comparire una sola volta
- Ogni elemento della lista può essere usato una sola volta
- Il primo elemento della sequenza è detto testa.
- Gli elementi successivi alla testa rappresentano la posizione del prossimo elemento nella lista di output ( la lista viene considerata come un anello)
- Percorrendo tutta la stringa secondo i salti contenuti nella stringa stessa si ritorna alla posizione iniziale
Analizziamo per esempio il runaround 81362
Cifra | Posizione |
---|---|
Testa | 8 1362 |
8 | 813 6 2 |
6 | 8136 2 |
2 | 8 1 362 |
1 | 81 3 62 |
3 | 8 1362 |
Si richiede un algoritmo per verificare se una data stringa rappresenta un runaround.
Allego dati per il test
Validi | Non Validi |
---|---|
13 | 12 |
147 | 123 |
1263 | 1234 |
81236 | 81111 |
83491 | 82222 |
913425 | 7654321 |
8124956 | 911111 |
Soluzione
Per verificare che una stringa sia un runaround semplicemente proviamo a percorrerla
def check_runaround(runaround)
disponibili=("1".."9").to_set
k=0
runaround.size.times{
return false if not disponibili.include?(runaround[k])
salto=(k+runaround[k].to_i) % runaround.size
disponibili.delete(runaround[k])
k=salto
}
return true if k==0
false
end