... »Und was Euch betrifft,« fuhr Alice fort und wandte sich wütend an die Schwarze
Königin, die sie für die Ursache des ganzen Unfugs hielt – aber die Königin war
nicht mehr an ihrer Seite – sie war plötzlich auf die Größe einer kleinen Puppe
geschrumpft und befand sich jetzt auf dem Tisch, wo sie fröhlich im Kreis ihrem
Schal nachlief, der hinter ihr herschleifte.
...
Kapitel XI. Erwachen
– und es war zu guter Letzt wirklich ein Kätzchen
"Alice hinter den Spiegeln" von Lewis Carroll
Aus dem Englischen von Jörg Karau, 2008
Wortleiter ist ein Buchstabenrätsel, das von Charles Dodgson (alias Lewis Carroll)
erfunden wurde.
Bei diesem Spiel geht es darum, zwei unterschiedliche Worte gleicher Länge durch eine
Kette von Worten miteinander zu verbinden.
Dazu darf in jedem Schritt nur ein einziger Buchstabe verändert werden.
Zum Beispiel:
HALM
⇒ HALT ⇒ HART ⇒
HORT ⇒ HORN ⇒
KORN
Die Roboter bevorzugen Ziffern anstelle von Buchstaben, also haben wir die Regeln ein
wenig verändert.
Gegeben ist eine Liste von Zahlen gleicher Länge. Die erste und letzte Zahl bilden
den Start- und Endpunkt der Kette. Deine Aufgabe besteht darin, aus den übrigen Zahlen
der Liste die kürzest gültige Kette zu bilden.
Ein Beispiel:
Die Liste: [123, 991, 323, 321, 329, 121, 921, 125, 999]
Die kürzest gültige Kette von der ersten (123) bis zur letzten Zahl (999) ist:
123
⇒ 121 ⇒ 921 ⇒ 991 ⇒
999
Schreibe eine Funktion, die als Argument eine Liste von positiven, ganzen Zahlen übernimmt
und die kürzest gültige Kette zurückgibt.
Eingabe:
Zahlen als Liste von ganzen Zahlen.
Ausgabe:
Die kürzeste, gültige Kette von der ersten bis zur letzten Zahl als Liste.
Beispiele:
checkio([123, 991, 323, 321, 329, 121, 921, 125, 999]) == [123, 121, 921, 991, 999]
checkio([111, 222, 333, 444, 555, 666, 121, 727, 127, 777]) == [111, 121, 127, 727, 777]
checkio([456, 455, 454, 356, 656, 654]) == [456, 454, 654] # or [456, 656, 654]
Wozu das gut ist:
Diese Aufgabe ist eine Variante des
Pathfinding
für Zahlen.
Bedingungen:
Alle Zahlen haben die gleiche Länge
∀ x ∈ numbers : 100 ≤ x < 1000