Es gibt ein klassisches kombinatorisches Ergebnis, dass die Anzahl der Möglichkeiten, einen 2*n
Streifen mit 1*2
Dominosteinen zu kacheln, die n- te Fibonacci-Zahl ist. Ihr Ziel ist es, alle Kacheln für eine bestimmte zu drucken n
, gezeichnet mit Strichen und vertikalen Linien wie diese 8 Kacheln für n=5
:
|————
|————
——|——
——|——
|||——
|||——
————|
————|
||——|
||——|
|——||
|——||
——|||
——|||
|||||
|||||
Sie müssen ein Programm oder eine benannte Funktion bereitstellen, die n
als Eingabe verwendet und die erforderliche Ausgabe druckt. Wenig Bytes gewinnen.
Eingang
Eine Zahl n
zwischen 1
und 10
einschließlich über STDIN oder Funktionseingang.
Ausgabe
Drucken Sie alle möglichen Domino-Kacheln des 2*n
Streifens horizontal gezeichnet. Die Fliesen können in beliebiger Reihenfolge sein, aber jede sollte genau einmal erscheinen. Sie müssen durch eine Leerzeile getrennt werden.
Ein vertikaler Domino besteht aus zwei vertikalen Balken ( |
) und ein horizontaler Domino besteht aus zwei Strichen ( —
). Sie können Bindestriche ( -
) anstelle von Bindestrichen verwenden, um in ASCII zu bleiben.
Sie können mit Leerzeichen alles tun, solange die gedruckte Ausgabe gleich aussieht.
——
und|
nach Länge wie bei Dennis filtern , nicht Längenfolgenn
von—
und|
gefiltert durch—
paarweises Erscheinen. Und für letzteres würde ich erwarten, dass es über reguläre Ausdrücke oder Zeichenfolgenoperationen für die erzeugte Zeichenfolge erfolgt, wies.split('——
) `, nicht durch einen arithmetischen Ansatz wie Ihren.Antworten:
C 106
Golfversion
Originalfassung
Wie es funktioniert
Die Variable
i
läuft von1<<n-1
bis 0 und erzeugt alle möglichen Binärzahlen mitn
Ziffern. 0 codiert für|
und 1 codiert für-
. Wir sind an Zahlen interessiert, die paarweise Einsen enthalten. Offensichtlich sind solche Zahlen durch 3 teilbar.Wenn eine Zahl durch 3 geteilt wird, kann die ursprüngliche Zahl wiederhergestellt werden, indem das Ergebnis mit 2 multipliziert und zu sich selbst addiert wird (effektiv mit 3 multipliziert). Die meisten Zahlen erfordern einen Übertrag, aber wenn der Prozess mit den Zahlen von ausgeführt wird Interesse ist kein Carry erforderlich, daher kann OR nur in diesen Fällen anstelle von Addition verwendet werden. Dies wird verwendet, um die interessierenden Zahlen zu testen, da sie die einzigen sind, bei denen der Ausdruck
i/3|i/3*2
den ursprünglichen Wert von zurückgibti
. Siehe Beispiel unten.1111
= 15 --->0101
= 5 --->1111
= 15 (gültig,0101|1010
==0101+1010
)1001
= 9 --->0011
= 3 --->0111
= 7 (ungültig ,0011|0110
! =0011+0110
)Der Testwert ist immer gleich oder kleiner als der ursprüngliche Wert. Da Zahlen, die keine Vielfachen von 3 sind, auch eine Zahl zurückgeben, die kleiner als das Original ist, wenn sie durch 3 geteilt und dann mit 3 multipliziert werden, ergibt der Test auch für diese Zahlen die gewünschte FALSCH.
In der Originalversion werden einige Schleifen
j
verwendet, um die Bits von zu durchsucheni
und die Ausgabe zu erzeugen. In der Golfversion wird eine einzelnefor
Schleife verwendet, in derh
alle Zahlen von(n*2)*(1<<n)-1
bis 0 durchlaufen werden. Werte voni
werden von generierth/2/n
. Die Variablej
wird nicht mehr verwendet, da die äquivalente Menge von erhalten wirdh%n
. Durch die Verwendung vonn*2
können beide Zeilen aus derselben Schleife gedruckt werden, wobei in derputs
Anweisung ein geschicktes Multiplexen erfolgt , um entweder eine oder zwei Zeilenumbrüche am Ende der Zeile zu drucken.Beachten Sie, dass sich das Fleisch davon in der Inkrementposition der
for()
Klammer befindet und daher nach dem ausgeführt wirdi=h/2/h
.Beispielausgabe n = 6:
quelle
i/3|i/3*2
Trick ist genial! Ich habe keinen arithmetischen Ausdruck für die Grammatik erwartet.CJam,
3327 BytesVielen Dank an @ jimmy23013 für das Golfen von 6 Bytes!
Probieren Sie es online aus!
Hintergrund
Dies ist eine iterative Implementierung eines rekursiven Algorithmus:
Die möglichen Kacheln für n können erhalten werden, indem ein vertikaler Dominostein zu den möglichen Kacheln für n - 1 und zwei horizontale Dominosteine zu den möglichen Kacheln für n - 2 hinzugefügt werden .
Auf diese Weise ist die Anzahl der Kacheln für n die Summe der Anzahl der Kacheln für n - 1 und n - 2 , dh die n- te Fibonacci-Zahl.
Wie es funktioniert
Beispiellauf
quelle
LNli{_'|f\@"——"f\+2/}*\;{_N}/
.f\
war noch nicht in 0.6.2 implementiert, aber ich konnte unsere Ansätze kombinieren. Vielen Dank!Haskell, 89 Bytes
f
ist eine Funktion, die bei gegebener Zahl eine Liste mit einer Zeile aller möglichen Fibonacci-Kacheln der Länge n zurückgibt. Es spielt keine Rolle, dass eine Zeile zurückgegeben wird, da beide Zeilen aller Kacheln gleich sind.f
Werke von rekursiv auf Aufrufn-1
undn-2
und das Hinzufügen"|"
und"--"
(jeweils) zu den Saiten.g
ist die Funktion, die die Fragen beantwortet. Grundsätzlich ruft esf
die Eingabe auf, verdoppelt jede Zeichenfolge, sodass zwei Zeilen angezeigt werden, und verbindet sie alle durch Zeilenumbrüche.Beispielausgabe:
quelle
CJam,
4237 BytesIch habe die Striche jeweils als ein Byte gezählt, da die Frage es ermöglicht, sie durch ASCII-Bindestriche zu ersetzen.
Probieren Sie es online aus.
Wie es funktioniert
Um alle möglichen Kacheln von 2 × L zu erhalten , iterieren wir über alle nicht negativen ganzen Zahlen I <3 L , wobei gerade Ziffern in Basis 3 horizontalen Dominos und ungerade Ziffern vertikalen entsprechen.
Da jeder I hat L oder weniger Stellen in der Basis 3 erzeugt diese alle Möglichkeiten des Bedeckens der 2 × L - Streifen. Sie müssen lediglich die Abdeckungen herausfiltern, die größer oder kleiner als 2 × L sind, und die verbleibenden Abdeckungen drucken.
Beispiellauf
quelle
3b
. Ist das richtig?JavaScript (E6) 102
Generieren Sie Konfigurationen aus den Bitfolgen 0 -> '-' und 1 -> '|'.
Test In der Firefox / Firebug-Konsole
Ausgabe
quelle
Haskell: 109 Bytes
Dies ist eine Übersetzung des bekannten Haskell-Einzeilers zur trägen Berechnung der Folge von Fibonacci-Zahlen:
Die Hauptsequenz der Kacheln von Saiten, ungolfed:
Und der Fibonacci-Einzeiler zum Vergleich:
Anwendungsbeispiel:
quelle
Cobra - 176
Ich kann es kaum erwarten, bis ich das Cobra-Golfpaket abgeschlossen habe.
quelle
J - 54 char
Funktion
n
als Argument auf der rechten Seite.Die Hauptwurzel dieses Golfs ist die
(];'--'&,"1@[,'|',"1])&>/
. Dies führt eine Liste der Kacheln der Länge (N-2) und (N-1) und gibt eine Liste der Kacheln der Länge (N-1) und N zurück. Dies ist die Standard-Fibonacci-Wiederholung à la lineare Algebra.];
Gibt die rechte Liste als neue linke zurück (da keine Änderung erfolgt).'--'&,"1@[
Fügt--
der linken Liste Kacheln'|',"1]
hinzu , während|
der rechten Liste Kacheln hinzugefügt werden, und diese zusammen bilden die neue rechte Liste.Wir wiederholen das immer und immer wieder
n
(das ist das@[&0
) und beginnen mit der leeren Kachelung und der einzelnen Kachelung der Länge 1. Dann geben wir die erste des Paares mit zurück0{::
. Das heißt, wenn wir es null Mal ausführen, geben wir nur das erste zurück, dh die leere Kachelung. Wenn wir esn
mal ausführen , berechnen wir bis zumn
und (n
+1) Paar, verwerfen aber das letztere. Es ist zusätzliche Arbeit, aber weniger Charaktere.Das
(1 2$,:)
ist etwas, was J tun muss, um die Kacheln in den Listen leicht erweiterbar zu machen. Wir machen die linke Startliste zu einer 1-Element-Liste einer 2-Zeilen-Matrix von Zeichen, wobei jede Zeile die Länge 0 hat. Die rechte Startliste ist dieselbe, aber die Zeilen haben die Länge 1, gefüllt mit|
. Dann fügen wir jeder Zeile die neuen Kacheln hinzu und hängen die Matrizenlisten an, wenn wir die beiden Kachelsätze zusammenfügen. Es ist eine einfache Anwendung eines Konzepts, das J als Rang bezeichnet: im Wesentlichen die Dimensionalität seiner Argumente zu manipulieren und bei Bedarf implizit eine Schleife durchzuführen.Probieren Sie es selbst bei tryj.tk aus .
quelle
Python 3: 70 Bytes
Erstellt rekursiv alle möglichen Zeichenfolgen,
s
die eine Reihe von Dominosteinen darstellen, die dupliziert und gedruckt werden. Beginnends
als Newline - Zeichen macht die Leerzeile automatisch.Der
==
zwischen den beiden Aufrufenf
besteht lediglich darin, beide Funktionsaufrufe auszuführen. Diese werden normalerweise zurückgegeben,None
weil sie nur gedruckt werden und==
einer der wenigen Operatoren sind, für die sie definiert sindNone
.Die
and
s undor
s sollen das richtige Kurzschlussverhalten erzeugen, um dieif
s undelse
s des ungolfed Codes zu reproduzieren .Ungolfed:
quelle
Netzhaut , 44 Bytes
Hinweis: Die Netzhaut ist jünger als diese Herausforderung.
Übernimmt die Eingabe unary mit einem nachgestellten Zeilenumbruch.
Jede Zeile sollte in eine eigene Datei gehen und
#
in der Datei in eine neue Zeile geändert werden. Dies ist unpraktisch, aber Sie können den Code wie eine Datei mit dem-s
Flag#
ausführen , wobei die Markierungen beibehalten werden (und die neue Zeile auch#
in der Eingabe geändert wird).#
Wenn Sie möchten, können Sie die 's wieder in Zeilenumbrüche in der Ausgabe ändern, um die Lesbarkeit zu verbessern. Z.B:Methode:
1
Änderung an|
und eine mit den ersten beiden1
Änderungen an--
. Wir machen das so lange, bis wir Linien mit mindestens zwei haben1
.1
übrig sind, haben wir diese in geändert|
.quelle