Herausforderung
Bestimmen Sie anhand einer Binärmatrix und einer Binärzeichenfolge, ob diese Binärzeichenfolge an einem beliebigen Punkt in der Matrix gefunden werden kann und sich an einem beliebigen nachfolgenden Punkt in eine beliebige Richtung bewegt, um die Binärzeichenfolge zu bilden. Das heißt, kann die Zeichenfolge jedoch innerhalb der Matrix zusammengefaltet gefunden werden?
Die Saite kann nur um 90 Grad oder 180 Grad gefaltet werden (Kantenverbindungen; Manhattan Distance 1) und darf sich an keiner Stelle überlappen.
Beispiel
Nehmen wir das folgende Beispiel:
Matrix:
010101
111011
011010
011011
Snake: 0111111100101
Dies ist ein wahrer Testfall. Wir können die gefaltete Schlange in der folgenden Position sehen:
0-1 0 1 0 1
|
1 1 1-0 1 1
| | | |
0 1 1 0-1-0
| |
0 1-1 0 1 1
Regeln
- Es gelten Standardlücken
- Sie können die Länge der Zeichenfolge und die Breite und Höhe der Matrix als Eingabe verwenden, wenn Sie möchten
- Sie können die Binärmatrix und die Binärzeichenfolge als eine mehrzeilige Zeichenfolge / ein Array von Zeichenfolgen / eine durch Zeilenumbruch verbundene Zeichenfolge / eine beliebige andere verbundene Zeichenfolge und eine Zeichenfolge annehmen
- Sie können die Dimensionen als flaches Array anstelle mehrerer Argumente verwenden
- Ihr Programm muss für jede 5 x 5-Matrix mit einer Zeichenfolge von bis zu 10 in weniger als einer Minute abgeschlossen sein
Einschränkungen
- Die Matrix ist nicht unbedingt quadratisch
- Die Zeichenfolge ist nicht leer
- Die Zeichenfolge kann die Länge 1 haben
- Die Zeichenfolge enthält nicht mehr Quadrate als verfügbar (d. H.
len(string) <= width(matrix) * height(matrix)
Testfälle
Wahrheit
01010
10101
01010
10101
01010
0101010101010101010101010
01110
01100
10010
10110
01101
011111000110100
0
0
10
01
1010
100
010
001
100010001
Falsch
00000
00000
00000
00000
00000
1
10101
01010
10101
01010
10101
11
100
010
001
111
10001
01010
00100
01010
10001
1000100010001000101010100
code-golf
decision-problem
binary-matrix
HyperNeutrino
quelle
quelle
Antworten:
Python 2 ,
275271264249 Bytes-1
durchH
und Entfernen eines Slicing-Vorgangs ([:]
) wurden vier Bytes gespart .[:]
), Zuweisen mehrerer Ziele, um einem besuchten Eintrag einen Wert zuzuweisenv not in "01"
(S=S[1:];M[y][x]=H;
->S=M[y][x]=S[1:];
) und von einem ternären if / else zu einem einfachen logischen oder (any(...)if S else 1
->not S or any(...)
) zu wechseln .ZeroDivisionError
) ausgelöst, wenn die Schlange gefunden wird, und eine leere Liste ([]
) zurückgegeben, wenn keine Schlange gefunden werden kann, die zwei unterschiedliche Verhaltensweisen aufweist.not S or
zuS<[1]or
~S==[]or
.Probieren Sie es online!
Erläuterung
Lambda-Funktion, die die Matrix als zweidimensionale Liste von Zeichenfolgen (entweder
"0"
oder"1"
), die Schlange als eindimensionale Liste und die Matrixdimensionen als zwei ganze Zahlen aufnimmt.Die Lambda-Funktion durchsucht die Matrix nach Einträgen, die mit dem ersten Element der Schlange übereinstimmen. Für jede gefundene Übereinstimmung wird
H
eine tiefe Kopie der Matrix, keine Kopie der Schlange, die Matrixdimensionen und die Position der Übereinstimmung abgerufen.Wenn
H
aufgerufen wird, wirdS
der erste Eintrag entfernt und der Matrixeintrag der angegebenen Position auf etwas anderes als gesetzt"0", "1"
. WennS
'length gleich Null ist, wird zurückgegebenTrue
. wie es sich rekursiv nennt, wurde die Schlange irgendwo in der Matrix gefunden.Wenn
S
'length ungleich Null ist, durchläuft es die vier Himmelsrichtungen, prüft, ob diese Position in der Matrix enthalten ist, vergleicht das Matrixelement an dieser Position mit dem ersten Element vonS
und ruft sich - falls es übereinstimmt - rekursiv auf.H
Die Rückgabewerte von werden über die Stapelrahmen übertragen, wobei immer geprüft wird, ob mindestens eine Funktion eine mögliche Schlange gefunden hat.Formatierte Ausgabe
Ich habe mein Programm erweitert, um auch den Pfad auszugeben, den die Schlange schlängelt (falls es einen gibt). Es wird das gleiche ASCII-Ausgabedesign wie für die Frage verwendet. TIO-Link .
quelle
m[:]for
~>m*1for
? Könnte funktionieren.JavaScript (ES6),
138134Nicht so verschieden von @ Neil's, aber was könnte es sonst sein?
Eingabe: Matrix als mehrzeilige Zeichenfolge, binäre Zeichenfolge, Breite (ohne Zeilenvorschub)
Anmerkung: Die Logik in der rekursiven Funktion
r
ist etwas invertiert, um ein paar Bytes zu sparenWeniger golfen
Prüfung
quelle
JavaScript (ES6), 149 Byte
Nimmt die Matrix als durch Zeilenumbrüche getrennte Zeichenfolge, die Schlange als Zeichenfolge und die Breite (als Ganzzahl). Lose basierend auf @ JonathanFrechs Antwort.
quelle
Mathematica,
180156141153138136104 BytesBeispiel Eingabe
Erläuterung
GridGraph@{##4}
ist einGraph
Objekt für ein Gitter von Scheitelpunkten mit benachbarten Scheitelpunkten, die durch Kanten verbunden sind, mit Dimensionen{##4}
- das heißt,{#4,#5}
oder{width,height}
.x
(nummeriert1
bis1##4 = width*height
), alle Endscheitelpunktey
undp
höchstens alle Längenpfade#3
vonx
bisy
.""<>Part[Join@@#,p]
die entsprechenden Zeichen der Matrix und fügt sie in eine Zeichenfolge ein.s
und suchen auf allen Ebenen, da dies eine sehr mehrdimensionale Liste ist, die wir erstellt haben.Hinweis: Das Ersetzen
#3
durch{#3-1}
inFindPath
, damit wir nur Pfade mit genau der richtigen Länge finden, ist eine enorme Geschwindigkeitsverbesserung - kostet aber 4 weitere Bytes.-24 Bytes: Dimensionen von Dingen als Eingabe nehmen
-15 Bytes: Verwenden
StringPart
undStringJoin
richtig+12 Bytes: Behebung des Länge-1-Falls
-15 Bytes: ...
-2 Bytes: Die Größe der Matrix wird als Eingabe für ein Array verwendet
-32 Bytes:
Table
Wenn Sie verwenden , um über den Pfad zu iterieren, vermeiden Sie die VerwendungFunction
, undMemberQ[...,s,All]
wenn Sie verwenden, haften Sie die Matrix beim Umgang mit Schlangen der Länge 1 auf der Tabelle.quelle
C # (.NET Core) ,
346341336302297 BytesProbieren Sie es online!
5 Bytes gespart durch Golfen des
p
Inkrements5 Bytes werden eingespart, indem die Schlangenlänge aufgenommen und am Ende begonnen wird und unnötiger Speicherplatz entfernt wird
34 Bytes wurden gespart, indem die Herausforderung richtig gelesen wurde und ich die Höhe und Breite der Matrix einschätzen konnte
5 Bytes gespart, der Einzelelement-Testfall fehlgeschlagen und die Korrektur von Vorteil
Ungolfed
quelle
if(...)return true;
->return ...;
.b[y,x]
muss irgendwann zurückgesetzt werden. (Tut mir auch leid, dass du deinen Namen in meiner Antwort falsch geschrieben hast.)if(N(x,y,0)>0)return 0<1;
; der erste Auftritt vonreturn
.Kotlin , 413 Bytes
Verschönert
Prüfung
quelle