Ach nein! Nemo, unser kleiner Clownfisch ist in diesem ASCII-Ozean verloren und sein Vater Marlin versucht ihn zu finden.
Ihre Aufgabe ist es, Marlin sicher nach Nemo zu bringen. Aber Vorsicht, wir haben einen Fütterungsrausch Bruce auf freiem Fuß, also meide ihn besser um jeden Preis!
Einzelheiten
Sie erhalten ein rechteckiges ASCII-Ozeangitter, das nur Kleinbuchstaben enthält a-z
. Dieser Ozean wird nemo
, marlin
und im bruce
Innern in Form eines kontinuierlichen polyomino, beginnend immer von der obersten Zelle in der ersten Spalte der polyomino. So sind beispielsweise von allen möglichen Tetrominos die gültigen im folgenden Snippet aufgeführt
Formulare wie diese sind jedoch ungültig und in der Eingabe nicht vorhanden:
omen
ne
mo
nem
o
o
m
en
nem
o
n
eo
m
Schließlich besteht Ihre Aufgabe darin, einen Pfad von der marlin
Polyomino-Kachel zur nemo
Polyomino-Kachel zu finden, um sicherzustellen, dass sich keine Zelle in Ihrem Pfad neben der bruce
Polyomino-Kachel befindet. Ihre Ausgabe sollte alle Alphabete ersetzen, die nicht Teil der marlin
Kachel, der nemo
Kachel und des Pfads sind, die beide durch ein Zeichen aus dem druckbaren ASCII-Bereich (einschließlich Leerzeichen) mit Ausnahme des Kleinbuchstabens verbinden a-z
.
Beispiel
Wenn der Eingangsozean wie folgt ist:
oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvtbsalyfrlyn
cicjrucejhiaeb
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv
(mit den 3 Polyominos sind:
...n..........
.mli..........
.ar...........
..............
....b.........
....ruce......
..............
.....n........
.....emo......
..............
..............
..............
)
Dann könnte eine gültige Lösung folgendermaßen aussehen:
...n..........
.mli..........
.ar...........
.u............
.n............
.i............
.z............
.wvjan........
.....emo......
..............
..............
..............
Das folgende Snippet enthält einige weitere Beispiele:
Anmerkungen
- Das Gitter wird immer ein perfektes Rechteck sein und nur eine polyomino Kachel enthält
nemo
,marlin
undbruce
. - Ihr Pfad sollte nicht durch
bruce
oder eine der 4 benachbarten (nach oben, unten, links und rechts) Zellen einer Zelle in derbruce
Kachel verlaufen. - Es ist immer garantiert, dass es mindestens einen gültigen Pfad von
marlin
bis gibtnemo
. - Hier ist kein kürzester Weg erforderlich, also verrückt!
- Auch wenn Sie nicht den kürzesten Pfad finden müssen, kann eine Zelle im Pfad (Pfad ohne Marlin oder Nemo) nicht an mehr als zwei andere Zellen im Pfad angrenzen.
- Der Weg sollte nicht durch die
marlin
odernemo
Kacheln führen, da dies die kleinen Fische bei der Wahl der Richtung verwirren würde. - Wie üblich können Sie ein Programm oder eine Funktion schreiben, indem Sie Eingaben über STDIN (oder das nächstgelegene Äquivalent), ein Befehlszeilenargument oder einen Funktionsparameter vornehmen und die Ausgabe über STDOUT (oder das nächstgelegene Äquivalent), den Rückgabewert oder den Funktionsparameter (out) erzeugen.
- Wenn eine mehrzeilige Eingabe nicht möglich ist, können Sie davon ausgehen, dass das Raster durch das
|
Zeichen anstelle von verbunden wird\n
. Sie können die Eingabe auch als Array von Rasterzeilen verwenden.
Dies ist Code Golf, so dass der kürzeste Eintrag in Bytes gewinnt.
quelle
k
oben genanntel
in Marlin sichtbar wäre? (macht den Weg vom n in Marlin nach Nemo)Antworten:
Matlab 560
560 Bytes beim Entfernen aller unnötigen Leerzeichen, aller Semikolons und aller Kommentare. Könnte viel mehr Golf spielen, aber ich bin jetzt zu müde (vielleicht morgen ...) Gute Nacht allerseits.
PS: Ich habe angenommen, dass der Pfad eine 4-Nachbarschafts-Verbindung ('+') haben muss.
Aufruffunktion: (Zeilenumbrüche nicht erforderlich)
Ausgabe:
Wie es funktioniert
Namen extrahieren
Der erste Teil ist das Extrahieren der Namen, z. B.
nemo
von der Funktionq()
. Die Funktion markiert zuerst alles als 0, dann den ersten Buchstaben des Namens als1
, dann den zweiten Buchstaben, als2
ob sich ein1
in der Nachbarschaft befindet, dann den dritten und so weiter. Danach solltenemo
es nur noch einen geben4
. Von da an gehen wir rückwärts, bis wir das1
wieder gefunden haben, und löschen dann alle anderen Zahlen, die größer waren, so dass wir eine schöne Maske zurückbekommen, in der die Buchstabennemo
maskiert sind. Wir tun dies für alle drei Namen und können dann einen Pfad finden.Den Weg finden
Wir beginnen an Marlins Positionen und senden Schritt für Schritt eine Schockwelle durch das Loch 'Bild'. In jedem Schritt erhöhen wir den Abstandszähler und markieren die 'Pixel' unter der Wellenfront mit der aktuellen Entfernung. (Wie es normalerweise mit Algorithmen für kürzeste Wege gemacht wird.) Diese Wellenfront wird offensichtlich durch den Bereich von Bruce blockiert, daher fließt sie um ihn herum. Dieser Schritt wird wiederholt, bis eine Obergrenze erreicht ist. Diese (zugegebenermaßen sehr lockere) Obergrenze ist nun der Umfang des 'Bildes' (die kürzesten Wege sind auf jeden Fall viel kürzer). Im Testfall sieht es ungefähr so aus:
Beginnen Sie nun bei
nemo
Pixeln und verringern Sie den Entfernungszähler in jedem Schritt und fügen Sie unserem Pfad einen Nachbarn mit der nächst niedrigeren Entfernung (gemäß der zuvor berechneten Entfernungskarte) hinzu.quelle
Python 2 - 658
Sehr sehr ineffizient in Zeit und Gedächtnis. Die Funktion zum Identifizieren der Muster ist die rekursive Funktion S, und die Funktion zum Finden der Pfade ist das C, was im Grunde eine schrecklich ineffiziente A * -Implementierung ist.
Verwenden Sie zum Testen dieses (sehr geringfügig) weniger Golfspiel (das den Pfad stattdessen einmal für jedes Plättchen berechnet).
quelle