Einführung
Diese Herausforderung ist inspiriert von Grime , meiner 2D-Pattern-Matching-Sprache. Grundsätzlich erhalten Sie eine "Grammatik", die zweidimensionale Gitter von Zeichen beschreibt, und Ihre Aufgabe ist es, ein Gitter gemäß der Grammatik zu generieren. Darüber hinaus sollte das Raster in einem gewissen schwachen Sinne so klein wie möglich sein.
Eingang
Ihre Eingabe ist eine Zeichenfolge, die ASCII-Kleinbuchstaben sowie die Symbole |
und enthält -
. Der Einfachheit halber enthält die Eingabe keine wiederholten Kleinbuchstaben. Die Zeichenfolge ist eine Spezifikation für eine Klasse von rechteckigen Zeichengittern und wird wie folgt mit einem Stapel von links nach rechts analysiert.
- Wenn Sie ein Zeichen in Kleinbuchstaben haben
c
, legen Sie für jedesm×n
Zeichen ein Raster des Zeichens auf den Stapel .c
m, n ≥ 1
- Bei einem Rohr
|
, Pop zwei GitterA
undB
aus dem Stapel (B
war oben) und schieben das GitterAB
erhält durch VerkettenB
rechts vonA
. Dies setzt voraus, dassA
undB
gleich hoch sind. - Bei einem Bindestrich
-
, Pop zwei GitterA
undB
aus dem Stapel (B
war oben) und schieben das GitterA/B
erhält durch VerkettenB
der an die UnterseiteA
. Dies setzt voraus, dassA
undB
gleich breit sind.
Es wird garantiert , dass für einige Entscheidungen von m
und n
bei der Analyse gemacht (die für jeden Buchstaben verschieden sein können), die Eingangsspezifikation korrekt einig Rechteck beschreibt, die auf dem Stapel am Ende übrig bleibt.
Ausgabe
Ihre Ausgabe ist ein rechteckiges Zeichenraster, das von der Eingabe angegeben wird. Das Raster muss in dem Sinne minimal sein, dass es ungültig wird, wenn Zeilen oder Spalten entfernt werden. Sie können eine durch Zeilenumbrüche getrennte Zeichenfolge (mit oder ohne abschließende Zeilenumbrüche), ein 2D-Array von Zeichen oder ein Array von Zeichenfolgen zurückgeben, je nachdem, welches Format das bequemste ist.
Beachten Sie, dass Sie die Eingabe nicht genau wie oben beschrieben verarbeiten müssen. Wichtig ist nur, dass Ihre Ausgabe korrekt ist.
Beispiel
Beachten Sie die Spezifikation
par-s||e-
Zuerst wählen wir ein 1×2
Rechteck aus p
und 1×1
Rechtecke aus a
und r
(der Grund dafür wird später klar). Dann knallen wir die a
und r
Rechtecken, und ihre vertikale Verkettung schieben
a
r
Als nächstes verschieben wir ein 1×2
Rechteck von s
, platzieren es und das obige Rechteck und verschieben ihre horizontale Verkettung
as
rs
Dann platzieren wir das Rechteck und das p
Rechteck und verschieben ihre Verkettung
pas
prs
Schließlich verschieben wir ein 3×1
Rechteck von e
, platzieren es und das obige Rechteck und verschieben die vertikale Verkettung
pas
prs
eee
Dies ist die Ausgabe des Programms oder mindestens eine der Möglichkeiten. Beachten Sie das, obwohl
ppas
ppas
pprs
eeee
Wird auch von der Spezifikation generiert, handelt es sich nicht um eine gültige Ausgabe, da viele der Zeilen und Spalten entfernt werden könnten.
Betrachten Sie als subtileres Beispiel
co|m|p|il|e|r|-
Diese Angabe erzeugt das Rechteck
comp
iler
Das ist eine gültige Ausgabe. Es erzeugt jedoch auch
commp
iiler
Dies gilt auch, da keine einzelne Zeile oder Spalte entfernt werden kann, ohne sie ungültig zu machen.
Regeln
Sie können ein vollständiges Programm oder eine Funktion angeben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.
Zusätzliche Testfälle
Mit diesen können Sie Ihr Programm testen.
Input:
a
Output:
a
Input:
co|mp|l|-ex|i|f|-y|
Example output:
cccoy
mplly
exify
Input:
ja-r|g-o|ni-|ze|d-|
Example output:
jronze
arondd
ggoidd
Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Example output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe
quelle
n
undm
werden nicht deterministisch gewählt. Es ist garantiert, dass geeignete Werte für sie existieren, aber es ist Aufgabe Ihres Programms, sie zu finden.un|co|p-|yr|i|gh--t-ab|-|le-||-
ist unmöglich, gültig zu sein. Der letzte-
hat eine Arität von 2, während sich nur 1 Element auf dem Stapel befindet.Antworten:
K,
123-110BytesIch habe einen ähnlichen Ansatz für die Lösung von cardboard_box gewählt.
Dieses Programm besteht aus einer Reihe von Hilfsdefinitionen, gefolgt von einer impliziten Funktion, die einen String als rechtes Argument verwendet. Neuformatierung zur besseren Lesbarkeit und Zuweisung der endgültigen Funktion als
f
:Anwendungsbeispiel:
Getestet mit Kona, funktioniert aber auch in OK, wenn Sie das
:
in der Definition von ersetzenf
durch a$
- k5 geänderte Syntax von "cond" .Ein wichtiger Punkt ist das Erkennen, dass ein vertikales Anhängen die Transponierung des horizontalen Anhängens der Transponierung beider Matrizen ist. (Siehe Definition
v
.) Ich denke, es gibt immer noch Raum, um hier und da ein paar Zeichen auszudrücken. Wenn jemand an einer detaillierteren Erklärung interessiert ist, kann ich eine liefern.bearbeiten:
Das Programm oben in diesem Eintrag wurde aktualisiert. Ungolfed-Version:
Zu den bemerkenswerten Längenoptimierungen gehört die Verwendung von "Punkt anwenden" in
a
, das Ersetzen von "Kond" durch das Indizieren in Listenf
(weniger effizient, aber kürzer) und das Ersetzen von Begriffen des Formularsa[b;c]
in,a[b]c
sofern dies durch Gruppierung zulässig ist. Da ich "cond" oder andere Primitive, die sich von k3 und k5 unterscheiden, nicht mehr verwende, funktioniert diese Version jetzt in OK ohne Änderungen.quelle
Prolog, 539 Bytes
Erläuterung
Wir beginnen mit einem Prädikat
g
, das eine Zeichenfolge annimmt, diese als Liste von Zeichen konvertiert und die aufruftp
Prädikat (parse) mit einem leeren Stapel als zweites Argument aufruft.Das Prädikat
p
ruft sich selbst rekursiv mit einem entsprechend geänderten Stack auf (suchen Sie nach[H|T]
Destrukturierungs- und Konstruktormustern). Beim Aufruf im Basisfall, in dem die Eingabeliste leer ist, wirdp
das eindeutige Element des Stapels gedruckt. Wenn der Stack zu diesem Zeitpunkt weniger oder mehr als ein Element enthält, bedeutet dies, dass eine leere Eingabezeichenfolge, eine ungültige Eingabezeichenfolge oder ein Fehler vorliegt (bei einer leeren Zeichenfolge schlägt das Prädikat fehl (sagt Prolog)No
), es wird jedoch nichts gedruckt). was ok ist, da wir für leere Strings nichts drucken sollten).Lösen
Der Stapel enthält eine Beschreibung der konstruierten Rechtecke, bezeichnet
S:W:H
mitS
einer symbolischen Darstellung des Rechtecks,W
seiner Breite undH
seiner Höhe (Anmerkung:A:B
Syntaxzucker für das:(A,B)
Tupel mit einem Funktor namens:
; es ist nur kürzer zu schreiben als ein Tupel) mit Präfixnotation).Mit
A
undB
unter RechteckspezifikationenS
kann Folgendes angegeben werden:h(A,B)
: Horizontalkonzentrat von A und Bv(A,B)
: vertikales Concat von A und Bf(C)
: mit C füllen, wobei C ein Zeichencode istBreiten und Höhen von Gittern sind Variablen zur Programmierung von Abhängigkeiten: Während der vertikalen (bzw. horizontalen) Verkettung wird die Breite (bzw. Höhe) der manipulierten Rechtecke vereinheitlicht, während die resultierende Höhe (bzw. Breite) auf die Summe von beschränkt wird Höhe (bzw. Breite) jedes Subgrids.
Der Beschriftungsschritt am Ende des Prozesses instanziiert Variablen unter Berücksichtigung von Einschränkungen unter Verwendung der minimal möglichen Werte (dies ist eine Eigenschaft der Reihenfolge, in der Lösungen ausprobiert werden).
Ich hätte vielleicht eine kürzere Antwort erhalten, wenn ich die gleiche Neuformulierung verwendet hätte wie bei anderen Antworten, ohne Einschränkungen, aber das ist jetzt zu spät.
Da die Standarddomäne für Variablen auf festgelegt ist
1..100
, gibt es eine Einschränkung hinsichtlich der möglichen Rastergrößen. Die Obergrenze kann bei Bedarf geändert werden. Die Auswirkungen auf die Leistung davon sind , dass es könnte eine Menge Zeit in Anspruch nehmen , um festzustellen , dass eine bestimmte Lösung keine Lösung gibt. Ich sagte " könnte ", weil Einschränkungen wahrscheinlich die exponentielle Suche drastisch beschneiden. Wenn Sie eine Eingabezeichenfolge finden, deren Zurückweisung schwierig / kostspielig ist, teilen Sie diese bitte mit.Drucken
Der Druckteil ist interessant, weil es eine Art Raycasting- Algorithmus für die Struktur gibt: Ich iteriere über jede Zelle des resultierenden Gitters von Punkt
(1,1)
zu Punkt(W,H)
und rufe dasw
Prädikat auf, um den Inhalt des Gitters im Hauptbaum zu drucken Diese Position (natürlich wird nach der Verarbeitung jeder Zeile eine neue Zeile gedruckt).In
w
sind die Positionen relativ zum aktuellen Raster (das Wurzelraster definiert absolute Koordinaten).Beim Drucken einer
h(A,B)
Struktur an einem Punkt(X,Y)
drucke ich bedingungslos in beiden Zweigen:A
am Punkt(X,Y)
undB
am Punkt(H,Y)
, woH
istX
minus der BreiteA
.Die Blattäste des Gitterbaums geben
f(C)
schließlich entweder das Zeichen ausC
, wenn sich die relative Position innerhalb des Gitters befindet, oder tun nichts. Auf diese Weise kann ich den Inhalt des Rasters von oben nach unten und von links nach rechts in den Ausgabestream drucken. Es werden keine tatsächlichen Arrays erzeugt.Tests
Lauftest:
quelle
No actual arrays are produced.
So sollte es gemacht werden. Overkill in diesem Fall, da die Grammatik so einfach ist und es Verknüpfungen gibt.Python 2.7, 259
g
ist eine Funktion, die eine Spezifikation annimmt und ein 2D-Array von Zeichen liefert. Wenn Sie eine benutzerfreundlichere Version wünschen, fügen Sie diese Zeile hinzu, um eine Spezifikation aus stdin zu übernehmen und das Raster auszudrucken:Testfälle
Erläuterung
Die Strategie ist einfach: Wenn ein Raster
G
für eine Spezifikation gültig istS
, gibt das Wiederholen der rechten Spalte vonG
auch eine gültige Spezifikation fürS
und das Gleiche gilt für das Wiederholen der unteren Zeile (der Beweis hierfür erfolgt durch strukturelle Induktion vonS
). Wenn wir also zwei Rechtecke verketten möchten, können wir einfach die letzte Spalte / Zeile der kleineren anhängen, bis sie in der Größe übereinstimmen (das ist, was die Funktion p tut).quelle
Haskell,
388367352 BytesVerwendung:
f "par-s||e-"
->["pas","prs","eee"]
Testlauf mit schönem Druck:
Funktionsweise: Die Funktion
#
analysiert die Eingabezeichenfolge in der Baumstruktur,C
die entweder ein BlattL
mit dem zu druckenden Zeichen oder einen Knoten enthältN
.N
kann a) ein Side-by-Side-Join (t==2
) sein, b) ein Top-Bottom-Join (t==1
) oder c) ein einzelnes Buchstabenquadrat (t==0
) sein. Alle Knoten haben ein Feld für Breite und Höhe sowie ein untergeordnetes Element für links und rechts. Druckt nach dem Parsenp
den verbleibenden Stammknoten, indem rekursiv die Größe (Breite x Höhe) der untergeordneten Knoten angepasst und diese verbunden werden.Bearbeiten: Ausgabe als Zeilenliste statt hübsches Drucken
quelle
JavaScript (ES6), 283
295Bearbeiten Nun ist diese (stark golfene) JS-Lösung mindestens kürzer als die Referenz (ziemlich golfene) Python-Lösung.
Ähnlich wie bei cardboard_box wiederholen Sie einfach die Spalte ganz links oder die Zeile ganz oben.
Ungolfed Dies ist meine erste ungolfed Lösung.
Test In der Firefox / FireBug-Konsole
Ausgabe
quelle
Python 3, 251 Bytes
Hier ist die Antwort, die ich versprochen habe und die ein bisschen weiter fortgeschritten ist.
Dies ist ein vollständiges Programm, das die Zeichenfolge von STDIN übernimmt und zu STDOUT druckt. Der Ansatz ist der gleiche wie bei cardboard_box: Verschieben Sie ein 1x1-Array für ein Zeichen und duplizieren Sie die Zeilen, falls dies zur Verkettung erforderlich ist.
Ausführliche Erklärung
T
transponiert eine gegebene Liste von Listen. Der Großteil der Arbeit wird durchzip(*m)
das Vertauschen von Zeilen in Spalten erledigt , der Rest konvertiert nur das Ergebnis in eine Liste von Listen, dazip
ein Tupelgenerator zurückgegeben wird.E(a,b)
Gibt zurück,a
wenn das erste Element so oft wiederholt wird, dass es der Länge von entsprichtb
. Beachten Sie, dass das Multiplizieren einer Liste mit einer negativen Zahl die leere Liste ergibt. Wenn dieseb
also kürzer als ista
, wird dies zurückgegebena
.H(a,b)
Gibt die horizontale Verkettung vona
und zurückb
, wobei die kürzereE
bei Bedarf verlängert wird .s
ist der Stapel.for
Schleife iterieren wir über die Eingabezeichenfolge und ersetzen sies
durch einen neuen Wert: Wenn es|
(größer alsz
) ist, fügen wir zwei Werte hinzu und verschieben sieH
. Wenn es-
(kleiner alsa
) ist, fügen wir zwei Werte hinzu, transponieren, fütternH
, transponieren Sie erneut und drücken Sie das Ergebnis, andernfalls drücken Sie ein 1x1-Array mit dem Buchstaben.s
.quelle