Einführung
Nachdem Sie einen Tag lang getrunken und die Weltmeisterschaft beobachtet haben, setzen Sie sich, um ein Freundschaftsspiel zu spielen. Die Stimmung steigt, weil Sie beschuldigt werden, Zeit mit unsinnigen Worten zu verschwenden, die nicht einmal auf dem Brett stehen! Möglicherweise sehen Sie doppelt, aber Sie denken sicherlich klar genug, um ein Programm zu schreiben, das überprüft, ob Ihre Worte auf der Tafel stehen.
Deine Aufgabe
Schreiben Sie ein Programm, ein Skript oder eine Funktion, die eine Boggle-Tafel und ein Wort als Eingabe verwendet und True zurückgibt, wenn sich das Wort auf der Tafel befindet, und False, wenn das Wort nicht auf der Tafel steht.
Die Eingabe erfolgt in Form von sechs getrennten \n
Zeilen. Die ersten fünf Zeilen bestehen aus dem 5x5-Block und enthalten jeweils fünf Großbuchstaben. Die sechste Zeile enthält das betreffende Wort, auch in Großbuchstaben.
Beispieleingabe:
AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER
Die Ausgabe kann alles sein, was in der Programmiersprache Ihrer Wahl eindeutig "Wahr" oder "Falsch" bedeutet und die Standardkonventionen "Null", "Null" und "Leer" für "Falsch" einhält.
Beispielausgabe für obige Eingabe:
1
I / O-Richtlinien
- Die Eingabe kann von stdin gelesen und die Ausgabe auf stdout beantwortet werden.
Oder
- Die Eingabe kann ein einzelnes Zeichenfolgenargument für eine Funktion sein und answer der Rückgabewert dieser Funktion.
Boggle-Regeln
- Ein Wort ist 'auf dem Brett', wenn Sie das Wort über einen Pfad aufeinanderfolgender, benachbarter, sich nicht wiederholender Kacheln auf dem Brett konstruieren können.
- Eine Kachel wird neben den acht Kacheln betrachtet, die sie umgeben (diagonale Pfade sind zulässig). Die Kacheln am Rand der Tafel grenzen an nur fünf Kacheln. Fliesen in der Ecke grenzen an nur drei.
- Aufeinanderfolgende Buchstaben im Wort müssen nebeneinander stehen, der
i
th Buchstabe im Wort muss neben demi-1
th undi+1
th stehen. - Ein Buchstabe kann in einem Wort mehr als einmal vorkommen, Sie können jedoch nicht mehr als einmal pro Wort dasselbe Quadrat auf der Schalttafel verwenden.
- Die online boggle Seite wordsplay.net kann nützlich sein, wenn Sie noch nie boggle gespielt haben, aber ein Gefühl für diese Regeln bekommen möchten.
Im Gegensatz zu normalen Boggle:
- Sie müssen sich NICHT darum sorgen, dass das Wort ein gültiges englisches Wort ist.
- Es wird KEINE
Qu
einzelne Fliese geben. - Das fragliche Wort kann eine beliebige Länge> 0 haben
Beispiel
Im Vorstand von
AJNES
TNFTR
LSAIL
UDNEX
EQGMM
Diese Wörter sollten True zurückgeben: FATE, DATING, STANDS, LIFTS.
Diese Wörter sollten False zurückgeben: SADDEN, SULTANS, EXIST, SUEDE, QUEST
Dies ist eine Code-Golf-Herausforderung, also gewinnt der kürzeste Code!
Antworten:
GolfScript, 74 Zeichen
Die Eingabe muss auf STDIN erfolgen. Gibt die Anzahl der gültigen Pfade auf der Karte aus, dh
0
für keine und für eine positive Zahl (true).Sie können das Beispiel online testen .
Code mit einigen Kommentaren:
quelle
Javascript (E6) 137
160 175 190Weniger als 2 * Golfscript. Moralischer Sieg ...
Neuorganisation des Golf-Codes bearbeiten . Wieder und wieder
Ungolfed Letzte Version, etwas schwierig zu folgen
Ungolfed Erste Version, sollte klarer sein
Verwendung
Prüfung
Ausgabe:
quelle
F=a=>(b=a.split('\n'),w=b.pop(Q=(p,n)=>((R|=!w[n])||(b[p]=0)||[1,5,6,7,-1,-5,-6,-7].map(q=>b[q+=p]==w[n]&&Q(q,n+1,b[q]=w[n])))),[Q(~~p,1)for(p in b=[...b.join(R=0)])if(b[p]==w[0])],R)
w = a.pop()
(Golf) oderw = b.pop()
(ungolf, Linie 2) sein? (wahrscheinlich das letztere, denke ich)a=a.pop()
anstattb=a.pop()
...Python,
207 204203Durch Ersetzen
... (b[i]==w[0])*any ...
durch wird... b[i]==w[0]and any ...
die Leistung auf Kosten von 2 Zeichen erheblich verbessert.quelle
0<=i<25and
J - 75 Zeichen
Eugh, dieser sieht böse aus. Und nicht einmal mit Golfscript zu binden! Dies ist eine Funktion, deren einziges Argument ein String ist. Sie können ein beliebiges Trennzeichen mit einem Zeichen verwenden, solange es am Ende jeder Zeile steht, einschließlich des letzten.
Eine Erklärung folgt. Beachten Sie, dass die Funktion in fünf verschiedene Teile der obersten Ebene unterteilt werden kann, die jeweils durch ein
@
Trennzeichen voneinander getrennt sind. Daher werden diese Teile von rechts nach links getrennt behandelt.(<;._2)
- Dies teilt die Zeilen in Zeilenumbrüche / Trennzeichen auf. Dabei wird das Zeichen am Ende der Zeichenfolge als das Zeichen verwendet, auf das aufgeteilt werden soll. Wir packen alles in Kästchen (<
), da wir sonst einige Auffüllprobleme bekommen, wenn J uns das Ergebnis zurückgibt.(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)
- Erstellen Sie für jeden Buchstaben im zu überprüfenden Wort eine Liste von Indizes in der Boggle-Tafel, in der sich dieser Buchstabe befindet.{:
ist das letzte geteilte Stück (das zu überprüfende Wort) und}:
ist alles andere als das letzte (das Boggle-Brett).&:>
öffnet die Kästchen, die wir zuvor erstellt haben, mit dem nützlichen Nebenprodukt der Umwandlung}:
in ein 2D-Array von Zeichen.=/
Dann wird für jeden Buchstaben im Wort eine Kopie dieses Boggle-Boards erstellt und die Positionen in boolesche Werte umgewandelt, je nachdem, ob der Buchstabe im Board mit dem Buchstaben im Wort übereinstimmt.((<@#:i.)5 5)
ist eine kurze Möglichkeit, ein 5x5-Array von Indizes auszudrücken.x#:y
is konvertierty
in ein Array der Basisdarstellungx
. (Na ja, fast. Die Wahrheit ist komplexer, aber das funktioniert für unsere Zwecke.)<@#~&,"2
- Sammeln Sie für die resultierende boolesche Matrix jedes Buchstabens alle entsprechend wahren Indizes zusammen."2
Lässt alles an den richtigen Ergebnissen arbeiten,#~&,
führt die Auswahl durch und<@
sammelt jedes Ergebnis in einer Box, um sich auf den nächsten Schritt vorzubereiten.{
- Dieses Verb, das monadisch verwendet wird, heißt Catalog und verwendet eine Liste von Feldern als Argument. Es kombiniert die Innenseiten jeder Box auf jede mögliche Weise. So würde zB ein Katalog auf einigen Feldern mit den Zeichenfolgen "AB" und "abc" die Ergebnisse "Aa", "Ab", "Ac", "Ba", "Bb", "Bc" ergeben.Wenn Sie dies in unserer Liste mit Indexlisten in der Box ausführen, können Sie alle möglichen Indexkombinationen erstellen. Dies kann eine große Menge sein, wenn das Wort lang ist und es viele wiederholte Buchstaben gibt, aber auch leer, wenn sich kein Buchstabe auf der Tafel befindet. Wir bemerken auch, dass wir Kacheln in einigen dieser Pfade wiederverwenden: Wir werden das später erklären.
([:*/"1^:2(2(=*)@-/\>@~.)S:1)
- Hier überprüfen wir jeden Pfad, um festzustellen, ob er gültig ist.(...)S:1
Wendet das(...)
auf jeden Pfad an und sammelt die Ergebnisse in einer flachen Liste. Dies ist von entscheidender Bedeutung, da das Ergebnis{
ein mehrdimensionales Array ist und wir uns nicht um die Struktur dieses Arrays kümmern, sondern nur um dessen Inhalt in jeder Box.2(=*)@-/\>
Gibt eine 1, wenn jede Koordinate jedes Index höchstens eine von der darauf folgenden entfernt ist, und ansonsten eine 0. Die2
und die/\
sind dafür paarweise verantwortlich.*/"1^:2
logische UNDs diese alle zusammen am Ende. Das[:
Teil ist eine strukturelle Sache in J, mach dir keine Sorgen.Das Hinzufügen
@~.
zu>
ist eine clevere Möglichkeit, Pfade mit wiederholten Eingaben auszuschließen.~.
Nimmt die eindeutigen Elemente einer Liste, so dass die Liste gekürzt wird, wenn sie sich selbst überschneidet, und kürzere Listen werden automatisch mit Nullen aufgefüllt, wenn sie zusammengesetzt werden, wie die Art und Weise, wie die Ergebnisse kombiniert werden, wenn sie herauskommenS:
. Dies ist letztendlich kürzer als das explizite Ausschließen von sich überschneidenden Pfaden.+/
- Zum Schluss addieren wir einfach alles zusammen. Das Ergebnis ist die Anzahl der gültigen Pfade, die das Wort auf der Tafel ergeben, wobei 0 keine Pfade bedeutet, dh dieses Wort befindet sich nicht auf der Tafel. Für die Kosten eines Zeichens können wir+./
stattdessen schreiben (alles logisch ODER-verknüpft), was explizit eine boolesche 1 oder 0 ergibt.Hier sind einige Beispielläufe. Sie können den J-Interpreter unter jsoftware.com oder online unter tryj.tk herunterladen .
quelle
Prolog - 315
Ich dachte, dass Prolog eine gute Sprache für diese ist, mit der eingebauten Rückverfolgungsunterstützung, aber ich denke, es ist mehr behindert, wenn für fast jeden berechneten Wert eine Variable benötigt wird.
Getestet mit GNU Prolog; sollte mit ISO Prolog kompatibel sein.
Ungolfed:
quelle