Eine reguläre Zeichenfolge sieht folgendermaßen aus:
Hello,IAmAStringSnake!
Und eine String-Schlange sieht ungefähr so aus:
Hel
l rin
o,IAmASt g
S
!ekan
Deine Aufgabe
String-Schlangen sind gefährlich, daher müssen Sie ein Programm erstellen, das eine String-Schlange als Eingabe verwendet und als regulären String ausgibt.
Spezifikationen
- Die Eingabe kann eine mehrzeilige Zeichenfolge oder ein Array von Zeichenfolgen sein.
- Jede Zeile der Eingabe wird mit Leerzeichen aufgefüllt, um ein rechteckiges Gitter zu bilden.
- Charaktere in der Schlange können sich nur mit benachbarten Charakteren verbinden, die sich über, unter, links oder rechts von ihnen befinden (genau wie im Spiel Schlange). Sie können nicht diagonal gehen.
- Die Schlangencharaktere werden niemals an einen anderen Teil der Schlange angrenzen, sondern nur an die verbundenen Charaktere.
- Das erste Zeichen der Zeichenfolge ist das Endzeichen mit dem kürzesten Manhattan-Abstand von der linken oberen Ecke des Eingaberasters (dh der minimalen Anzahl von Zügen, die eine Schlange benötigen würde, um direkt vom Endzeichen nach links oben zu gelangen) Ecke). Beide Enden werden niemals den gleichen Abstand haben.
- Die Zeichenfolge kann ein beliebiges ASCII-Zeichen zwischen den Codepunkten 33 und 126 enthalten (keine Leerzeichen oder Zeilenumbrüche).
- Die Zeichenfolge ist zwischen 2 und 100 Zeichen lang.
- Kürzester Code in Bytes gewinnt.
Testfälle
(Eingaberaster, gefolgt von der Ausgabezeichenfolge)
Hel
l rin
o,IAmASt g
S
!ekan
Hello,IAmAStringSnake!
----------
Python
Python
----------
P ngPu Code
r i z d G
o m z n o
gram lesA lf
ProgrammingPuzzlesAndCodeGolf
----------
~ zyx tsr XWVUTSR
}|{ wvu q Y Q
! p Z `ab P
"#$ 6789:; o [ _ c O
% 5 < n \]^ d N
('& 432 = m e M
) 1 > lkjihgf L
*+,-./0 ? K
@ABCDEFGHIJ
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
----------
tSyrep
r p
in Sli
g Sile
Snakes n
Ser ylt
a eh ilS
fe w t
emo h
Sre
SlipperyStringSnakesSilentlySlitherSomewhereSafe
Antworten:
APL, 55 Bytes
Diese Funktion nimmt eine Zeichenmatrix mit der Zeichenfolge snake auf.
Beispiel:
Erläuterung:
(,⍵≠' ')/,⍳⍴⍵
: Ermittelt die Koordinaten aller Nicht-Leerzeichen(⊂0 0)
: beginne bei (0,0) (das ist eine ungültige Koordinate){
...}
: folge der Schlange, gegebene Position und Schlange:1<⍴⍵:
: wenn mehr als ein Element übrig ist:∆←⍵~⍺
: Entfernen Sie die aktuelle Position von der Schlange und speichern Sie sie in∆
.+/¨|⍺-∆
: Finde den Abstand zwischen der aktuellen Position und jedem Punkt im Rest der Schlange∆[⊃⍋...
] `: Finde den nächsten Punkt auf der Schlange∇
: Führen Sie die Funktion erneut aus, wobei der nächstgelegene Punkt der neue aktuelle Punkt und die verkürzte Schlange die neue Schlange ist.⍺,
: füge die aktuelle Position zum Ergebnis hinzu⋄⍺
: Andernfalls geben Sie einfach die aktuelle Position zurück1↓
: lösche den ersten Eintrag aus dem Ergebnis (das ist die (0,0) Position)⍵[
...]
: Holen Sie sich diese Elemente von ⍵, in dieser Reihenfolgequelle
JavaScript (ES6) + SnakeEx , 176 Byte
Erinnerst du dich an SnakeEx? Gut, denn ich auch nicht! Golfvorschläge sind willkommen.
quelle
MATL , 80 Bytes
Vielen Dank an @LevelRiverSt für eine Korrektur
Die Eingabe erfolgt als 2D-Zeichenfeld mit durch getrennten Zeilen
;
. Die Testfälle in diesem Format sindProbieren Sie es online!
Erläuterung
Die Koordinaten jedes Nicht-Leerzeichens werden durch eine komplexe Zahl dargestellt. Für jedes aktuelle Zeichen wird das nächste als dasjenige erhalten, das am nächsten ist (minimale absolute Differenz ihrer komplexen Koordinaten).
Um den Anfangsbuchstaben zu bestimmen, müssen die beiden Endpunkte gefunden werden. Dies geschieht wie folgt. Ein Endpunkt ist ein Nicht-Leerzeichen, das genau einen Nicht-Leerzeichen-Nachbarn hat. Die Anzahl der Nachbarn wird durch 2D-Faltung mit einer geeigneten Maske erhalten. Der Anfangspunkt ist der Endpunkt, dessen komplexe Koordinate die geringste Summe von Real- und Imaginärteilen aufweist. dh ist in Manhattan am nächsten an der komplexen Zahl 0 oder äquivalent zu 1 + 1j, der komplexen Koordinate der oberen linken Ecke.
quelle
The initial point is the endpoint whose complex coordinate has the least absolute value
Achtung: Euklidische Distanz! = Manhattan Distanz. Zum Beispiel hat der Punkt 7 + 7j eine euklidische Entfernung 9,8994 und eine Manhattan-Entfernung 14. 10j ist weiter von der euklidischen Entfernung entfernt, aber wesentlich näher von der Manhattan-Entfernung. Ansonsten tolles Konzept!C
198190179180181 BytesBearbeiten: Benutzte den Tipp von user81655 und entfernte die Klammer im ternären Operator, danke! Ich habe auch den umständlichen (S & 1) Test auf Gleichmäßigkeit geändert, um den angemesseneren (und kürzeren!) S% 2 zu erhalten.
Edit2: Die Verwendung des Adressierungsstils * a hat mich blind gemacht für die offensichtlichen Optimierungen in der Definition von S, dh das Ersetzen von * (a + m) durch [m] usw. Ich habe dann S selbst durch T ersetzt, was im Wesentlichen zutrifft die Hälfte von dem, was S macht. Der Code nutzt jetzt auch den Rückgabewert von putchar.
Edit3: Behobener Fehler, der von Anfang an auftrat. Das Manhattan-Suchstoppkriterium a <b + m ist nur dann korrekt, wenn a bereits dekrementiert wurde. Dies fügt 2 Bytes hinzu, aber eines wird wiederhergestellt, indem die Definition von m global gemacht wird.
Edit4: Mein Golfen hat das Minimum überschritten und geht jetzt in die falsche Richtung. Ein weiterer Bugfix im Zusammenhang mit der Manhattan-Suche. Ich hatte ursprünglich eingehende Prüfungen eingerichtet, und ohne diese wurde die Suche nach großen Eingabearrays (etwa 50 x 50) über das Array hinaus fortgesetzt. B. Daher muss dieses Array auf mindestens das Doppelte der vorherigen Größe erweitert werden, wodurch ein weiteres Byte hinzugefügt wird.
Ungolfed und erklärte:
quelle
a[1]
,a[-m]
etc, und machenm
global -m=103;main()
.C 272 Bytes
Schauen Sie sich die Quelle von @ Zunga an. Nun sieh dir meine an. Möchten Sie wissen, wie ich die zusätzlichen 91 Bytes erhalten habe?
Ungolfed:
quelle
Python (2 und 3),
640 624 604 583 575 561 546538 BytesIch bin immer noch ein Golf-N00B, das ist also ein bisschen groß.
Edit: Danke an @porglezomp für die Vorschläge! Ich habe nicht alle 'und' Operatoren entfernt, da dies Python 3 beschädigen würde.
Edit2: Danke an @Aleksi Torhamo für den Kommentar zu isspace (). Die daraus resultierende Reduzierung gleicht den von mir eingebrachten Bugfix aus. Auch dank anonymous für die Syntaxhervorhebung!
Edit3: Danke an @ mbomb007 für ein paar zusätzliche Bytes.
Und hier ist meine Pre-Golf-Version
quelle
S=lambda s:s.isspace()
und dann getan habe,S(s)
anstatts.isspace()
.and
zu<
, daf() < g() < h()
die gleichen wieg = g(); f() < g and g < h()
in Bezug auf Nebenwirkungen (Vergleichsketten Kurzschluss), und Sie sind das Ergebnis der Vergleiche ohnehin ignorieren.m[(x,y)]=
ist das gleiche wie die kürzerem[x,y]=
S=str.isspace
S
und Verwenden kann<'!'
bei jedem Auftreten gleich lang sein, was möglicherweise die Möglichkeit eröffnet, mehr zu sparen. Zum Beispiel wechselnif 1-S(v[x]):
zuif(v[x]<'!')<1:
. Und vielleicht könnten Sie auf diese Weise einige Klammern in den späteren Vergleichen entfernen.JavaScript (ES6), 195
Siehe Erklärung im Test-Snippet
Prüfung
quelle
););}
benötigt?for
Kopfzeile, in der 2 Doppelpunkte erforderlich sind. Der zweite ist der Delimeter für denfor
KörperLua,
562535529513507504466458 BytesMein derzeit mit Abstand massivstes Golfspiel,
ich denke, ich kann immer noch 100 Bytes abschneiden, worauf ich hinarbeiten werde, aber es als Antwort posten, da es schon einige Zeit gedauert hat :).Ich hatte recht, ich habe mehr als 100 Bytes gekürzt! Ich denke nicht, dass es viel Raum für Verbesserungen gibt.Diese Funktion muss mit einem 2D-Array aufgerufen werden, das ein Zeichen pro Zelle enthält.
40 Bytes bei der Arbeit mit @KennyLau gespart , dank ihm!
Woohoo! Unter 500!
Ungolfed
Sobald ich mit dem Golfen fertig bin, werden Erklärungen folgen. Im Moment leihe ich Ihnen eine lesbare Version dieses Quellcodes: DHier kommen die Erklärungen!Bearbeiten: nicht mit der neuesten Änderung aktualisiert, noch vor dem Aktualisieren golfen. Gleiches gilt für die Erklärungen
Hier finden Sie einige detaillierte Erklärungen zur Funktionsweise dieses Programms.
Betrachten wir zunächst die Schleife mit der Bezeichnung
a
, damit wir das nächste Ende in der oberen linken Ecke finden können. Es wird für immer wiederholt, wenn es kein Ende gibt, aber das ist kein Problem: D.Auf einem 4x4-Gitter sind hier die Schlangenabstände (links) und die Reihenfolge, in der sie betrachtet werden (rechts).
Damit jedes dieser Zeichen das Ende ist, müssen zwei Bedingungen überprüft werden: - Kein Leerzeichen - Umgeben von genau 3 Leerzeichen (oder genau 1 Nicht-Leerzeichen)
Diese Bedingungen werden im folgenden Code überprüft
Durch den Ausdruck wird überprüft, ob das Zeichen kein Leerzeichen ist
m[i][j]~=s
.Wenn Sie überprüfen, ob nur 1 Nicht-Leerzeichen vorhanden ist, indem Sie die obigen Bedingungen für unsere Umgebung angeben, kann dies folgendermaßen geschrieben werden
Und schließlich, wenn alle oben genannten Werte als wahr ausgewertet werden, gibt der Ternär das zurück, was in der letzten
and
-> stehtm[i][j]
. Sonst lassen wir losr
:)Jetzt, wo wir den Schlangenkopf haben, gehen wir zum anderen Ende! Das Iterieren der Schlange wird hauptsächlich durch die folgenden geschachtelten Ternaries erreicht:
Wir werden zurückgesetzt
i
undj
zur gleichen Zeit, um zu vermeiden, dass Dummies zum Speichern der alten Werte benötigt werden. Beide haben die exakt gleiche Struktur und verwenden einfache Bedingungen. Deshalb werde ich sie in Form von verschachtelten präsentierenif
, damit Sie sie lesen können noch einfacher. :)Kann übersetzt werden in:
Probier es aus!
Hier ist der Code, den ich verwende, um dies auszuführen. Sie können ihn online testen, indem Sie ihn kopieren und einfügen.
quelle
Lua, 267 Bytes
Lua 5.3 ist erforderlich.
Verwendungszweck:
quelle
Python 3,
245243241236 Bytess
ist die Eingabezeichenfolge,n
wird die Ausgabe auf stdout gedruckt:Edit: Danke an @Cees Timmerman für das Speichern von 5 Bytes!
quelle
c>' 'and
undprint n
in Python 2.if
stattelif
?s
Variable ist eine mehrzeilige Zeichenfolge. Das letzte Zeichen der Zeichenfolge muss ein Zeilenumbruch sein (dies ist erforderlich, um denPython
Testfall zu bestehen)Python, 537
Meine anfängliche Lösung:
Ein bisschen komprimiert, aber als Methode belassen:
quelle
Java 7,
927924923 BytesOk, das hat eine Weile gedauert. In einigen Programmiersprachen spielt es keine Rolle, ob Ihr Array x und y außerhalb der Grenzen eines 2D-Arrays liegt, aber mit Java wird es geworfen
ArrayIndexOutOfBoundsExceptions
, also muss alles überprüft werden.Ich bestimme zuerst den Startpunkt und benutze dann eine rekursive Methode, um die Zeichenfolge von dort zu erstellen. Außerdem verwende ich eine Liste, um die bereits aufgetretenen Koordinierungen zu protokollieren, damit sie nicht in einer Schleife vor und zurück ablaufen (was zu einer StackOverflowException führt).
Dies ist wahrscheinlich die längste Antwort, die ich bisher gepostet habe, aber obwohl einige Teile golfen können, glaube ich nicht, dass diese Herausforderung in Java so viel kürzer sein kann. Java ist einfach nicht geeignet, um einem Pfad in einem Raster zu folgen. Trotzdem war es eine lustige Herausforderung, dies herauszufinden. :)
Ungolfed & Testfälle:
Probieren Sie es hier aus.
Ausgabe:
quelle
PHP,
199184182 Byteshat vielleicht noch ein wenig golfpotential
Nimmt die Eingabe als mehrzeilige Zeichenfolge von der Befehlszeile und erwartet Zeilenumbrüche im Linux-Stil.
Run
php -r '<code>' '<string>'
; Entkomme Zeilenumbrüchen.Nervenzusammenbruch
quelle
C #, 310
(Edit: Bugfix)
Eine Funktion mit einem mehrzeiligen Zeichenfolgenparameter, der eine Zeichenfolge zurückgibt.
Einbeziehen der angeforderten
using
in die Byteanzahl.Dies ist eine Portierung meiner Javascript-Antwort.
Test auf Ideone
Mit Leerzeichen
quelle
Python 2, 251 Bytes
Oder, wenn Sie führende Zeilen in Ihren Testfällen haben möchten, 257 Bytes:
Besteht alle Testfälle.
Ergebnisse in:
quelle
b.append(...)
mitb+=[...]
unddef n(x,y):return ...
mit ersetzenn=lambda x,y:...
' '
.~-x
stattx-1
, müssen Sie keine Klammern verwenden.Japt
-P
, 106 BytesProbieren Sie es online!
Es ist ... ähm ... ein Gräuel.
Ausgepackt und wie es funktioniert
Ein bemerkenswerter Punkt ist, dass ich in JS die Operator-Rangfolge zwischen Zuweisungs- und Komma-Operatoren verwendet habe, um einige Zeilen zu packen und die shortcut
@
(XYZ{
) verwendbar zu halten.quelle