Anzeigetafel
Hier sind die Rohwerte (dh Domino-Werte) für die Einreichung von VisualMelon. Ich werde diese Werte in die unten beschriebenen normalisierten Werte umwandeln, wenn weitere Antworten eingehen. Die vorhandene Lösung kann jetzt alle Schaltkreise im Benchmark lösen:
Author Circuit: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
VisualMelon 39 45 75 61 307 337 56 106 76 62 64 62 182 64 141 277 115 141 92 164 223 78 148 371 1482 232 107 782 4789 5035 1314 3213 200 172 1303 3732 97596 156889 857
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Legend:
I - invalid circuit
B - circuit too big
W - circuit computes wrong function
T - exceeded time limit
Die Herausforderung
Es ist möglich , einfache Logikgatter aus Dominosteinen zu bauen. Durch Kombinieren dieser oder anderer Funktionen können daher beliebige Binärfunktionen mit Dominosteinen berechnet werden.
Aber natürlich hat jeder, der mit Dominosteinen gespielt hat (mit Ausnahme von Robin Paul Weijers), die Enttäuschung erlebt, wenn er davonläuft. Daher möchten wir unsere Dominosteine so effizient wie möglich einsetzen, damit wir mit dem vorhandenen Material einige wirklich interessante Berechnungen durchführen können.
Beachten Sie, dass Sie keine Nicht-Null-Ausgabe aus der Null-Eingabe per se erzeugen können. Daher müssen wir eine "Stromleitung" hinzufügen, die entlang Ihres Setups verläuft und von der Sie jederzeit 1
s abrufen können.
Deine Aufgabe
Erstellen Sie bei einer Booleschen Funktion mit M
Eingängen und N
Ausgängen ( f: {0,1}^M --> {0,1}^N
für die mathematisch geneigten) eine Domino-Schaltung mit möglichst wenigen Dominosteinen, die diese Funktion berechnet. Hier finden Sie die Symbole verwenden |
, -
, /
,\
Dominosteine in verschiedenen Orientierungen zu vertreten.
Eingang
Sie erhalten Eingaben über Befehlszeilenargumente:
[command for your solver] M N f
wo M
und N
sind positive ganze Zahlen und f
ist das Komma getrennt Wahrheitstabelle in kanonischer Reihenfolge. Das heißt, f
enthält 2^M
Werte der Länge N
. ZB wenn M = N = 2
und das erste Bit in der Ausgabe die UND-Funktion war, während das zweite Bit die ODER-Funktion war, f
würde gelesen
00,01,01,11
Ausgabe
Schreiben Sie in STDOUT ein ASCII-Raster, das das Domino-Setup darstellt. Ihr Setup muss in das folgende Framework passen
/////.../////
????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
- Die oberste Reihe besteht ganz aus
/
und der Domino ganz links wird garantiert zu Beginn umgestürzt - das ist Ihre Stromleitung. - Die äußerste linke Spalte enthält Ihre Eingaben. Jedes
I
kann entweder ein Leerzeichen oder ein sein|
, so dass es genauM
|
s gibt. - Die Spalte ganz rechts enthält Ihre Ausgaben. Jedes
O
kann entweder ein Leerzeichen oder ein sein|
, so dass es genauN
|
s gibt. - Beachten Sie, dass
|
in der Eingabe oder Ausgabe mindestens ein Leerzeichen vor dem ersten vorhanden ist . - Die
.
anzeigen , dass das Raster beliebig groß sein kann. - Sie können die Felder
?
nach Belieben ausfüllen .
Beachten Sie, dass sich die Eingabe unten am schnellsten ändert, während Sie die Wahrheitstabelle durchlaufen, während sich die Eingabe oben 0
auf die erste Hälfte der Ausgaben und bezieht1
für die zweite Hälfte gilt.
Regeln
Dominosteine vermehren sich wie in " Golfen am Domino-Tag" angegeben . Kurz gesagt, wenn wir die fallenden Richtungen als Buchstaben darstellen
Q W E
A D
Z X C
Dann sind dies alles einzigartige Kombinationen, die sich ausbreiten können (sowie ihre Rotationen und Reflexionen):
D| -> DD D\ -> DE D/ -> DC
C| -> CD C/ -> CC
C -> C C -> C C -> C
| D - X / C
Alle oben genannten Regeln werden bei jedem Zeitschritt gleichzeitig angewendet. Wenn zwei dieser Regeln in Konflikt stehen (dh ein Plättchen wird gleichzeitig in zwei gültige entgegengesetzte Richtungen verschoben), fällt das betroffene Plättchen nicht herunter und wird für den Rest der Simulation effektiv in seiner Position verriegelt.
Beschränkungen
M
undN
wird nie mehr als 6.- Ihr Solver muss innerhalb von N * 2 M Sekunden einen Stromkreis erzeugen .
- Ihr Solver darf nicht mehr als 1 GB Arbeitsspeicher verwenden . Dies ist eine weiche Grenze, da ich dies manuell überwachen und Ihren Prozess beenden werde, wenn er diese Grenze signifikant / kontinuierlich überschreitet.
- Kein Stromkreis darf mehr als 8.000.000 Zellen oder 1.000.000 Dominosteine enthalten .
- Ihre Vorlage muss deterministisch sein . Sie dürfen Pseudozufallszahlengeneratoren verwenden, diese müssen jedoch einen fest codierten Startwert verwenden (den Sie nach Belieben optimieren können).
Wertung
D
Geben Sie für jede Runde die Gesamtzahl der Dominosteine in Ihrer Runde und B
die niedrigste Anzahl der Dominosteine an, mit denen diese Runde gelöst wurde (von Ihnen oder einem anderen Teilnehmer). Dann ist Ihre Punktzahl für diese Strecke gegeben durch10,000 * B / D
Abrunden angegeben. Wenn Sie die Schaltung nicht gelöst haben, ist Ihre Punktzahl 0. Ihre Gesamtpunktzahl ist die Summe über einem Benchmark-Satz von Testfällen. Schaltungen, die noch von niemandem gelöst wurden, werden nicht in die Gesamtpunktzahl einbezogen.
Jeder Teilnehmer kann einen Testfall zum Benchmark hinzufügen (und alle anderen Einsendungen werden neu bewertet, einschließlich des neuen Testfalls).
Die Benchmark-Datei finden Sie auf GitHub .
Beispiele
Hier einige nicht optimal gelöste Beispiele.
Konstante 1
1 1
1,1
///////
/
| |||
Domino-Anzahl: 12
ODER Tor
2 1
0,1,1,1
///////////
|||||/
|||||
|||||\
Domino-Anzahl: 28
UND Tor
2 1
0,0,0,1
///////////////////
\-/
- -
|||||/|\ /|||/
/ -
- \-
\- \ -
|||||\ / \ /
|\ |||||
Domino-Anzahl: 62
Fahrspuren tauschen
2 2
00,10,01,11
////////////
||||/ \||||
/\
\/
||||\ /||||
Domino-Anzahl: 36
Zusätzliche Bemerkungen
Die Ausbreitungsregeln sind so, dass sich diagonale Bahnen mit einer Rautenform kreuzen können (siehe letztes Beispiel), auch wenn eine vor der anderen fällt (im Gegensatz zu echten Dominosteinen).
Als Ausgangspunkt können Sie die (nicht minimierten) logischen Gatter in dieser Übersicht verwenden und versuchen, so wenig wie möglich davon zu kombinieren. Für eine einfache (nicht optimale) Möglichkeit, beliebige Boolesche Funktionen aus UND-, ODER- und NICHT-Gattern zu erstellen, werfen Sie einen Blick auf Konjunktive und disjunktive Normalformen.
Es gibt einen Prüfer für dieses GitHub-Repository , um Ihren Code zu testen, der auch zum Bewerten aller Einsendungen verwendet wird. Dadurch werden die Rohwerte (Domino-Werte) ausgegeben und in einer Datei gespeichert, die von einem separaten Scorer (ebenfalls in diesem Repository) verarbeitet wird, um die Endwerte zu erhalten.
Allgemeine Dokumentation finden Sie in den beiden Ruby-Dateien, die jedoch controller.rb
zwei Befehlszeilenoptionen vor der Benchmark-Datei benötigt:
-v
Sie erhalten mehr Ausgabe, einschließlich der von Ihrem Solver tatsächlich erzeugten Schaltungen.-c
Mit dieser Option können Sie eine Teilmenge des Benchmarks auswählen, den Sie testen möchten. Geben Sie die gewünschten Schaltkreise als durch Kommas getrennte Liste von 1-basierten Indizes an. Sie können auch Ruby-Bereiche verwenden, sodass Sie beispielsweise Folgendes tun können-c 1..5,10,15..20
.
Bitte geben Sie in Ihrer Antwort an:
- Dein Code
- Ein Befehl zum (Kompilieren und) Ausführen Ihres Codes. Ich frage Sie, wo Sie die erforderlichen Übersetzer / Dolmetscher bekommen, wenn ich sie nicht habe.
- Eine zusätzliche Wahrheitstabelle mit einem Namen, die als Testfall zum Benchmark hinzugefügt werden soll. (Dies ist optional, wird jedoch dringend empfohlen.)
Ich werde alle Einsendungen unter Windows 8 testen.
quelle
Antworten:
Massive, langsame und ineffiziente Lösung
Geständnis: schrieb diese Lösung vor einiger Zeit, als die Frage noch im Sandkasten war, aber es ist nicht sehr gut: Sie können es besser machen!
Bearbeiten: Die langweilige Lösung wurde durch eine weniger langweilige, flexiblere und allgemein bessere Methode ersetzt
Sie führen das Programm aus, indem Sie beispielsweise mit
csc dominoPrinter.cs
der ausführbaren Datei (dem 4-Bit-Prime-Checker) kompilieren und dann Argumente übergeben:Erläuterung:
Der "Domino-Drucker" ist ein dreistufiges Programm:
Stufe 1 : Der "Löser" generiert einen Ausdrucksbaum aus "ifnot" und "oder" binären Operationen mit den angegebenen Eingaben und einer "1" von der Stromleitung. Dies erfolgt auf zwei Arten, abhängig von der Anzahl der Eingaben:
Wenn weniger als 4 Eingaben vorhanden sind, bietet das Programm eine Lösung mit der geringsten Anzahl von Operationen
Wenn es 4 oder mehr Eingänge gibt, brutet das Programm jeden 8-Bit-Ausgang und kombiniert dann die Ergebnisse, um den gewünschten Ausgang zu erhalten. Die brutalen Bits sind flexibel: Je mehr brutale Bits vorhanden sind, desto kleiner ist die Lösung, desto länger ist jedoch die Laufzeit.
Der "Solver" ist das, was die ganze Zeit (oder zumindest früher) dauert und auch den größten Teil des Codes ausmacht. Ich glaube, es gibt eine gut dokumentierte, schnelle, nicht so speicherhungrige und wahrscheinlich optimale Lösung für dieses Problem, aber wo würde es Spaß machen, danach zu suchen?
Der (brutale) Ausdrucksbaum für den 4-Bit-Prim Checker lautet
Dabei sind die Zahlen die Indizes der Eingaben.
Stufe 2 : Der "Organisator" nimmt den Ausdrucksbaum als Eingabe und setzt ein "Gerüst" -Layout zusammen, das genau ein Domino-Layout beschreibt, das aus einem Satz von 4 × 5 überlappenden Zellen besteht. Unten sehen Sie das Grundgerüst für den brachialen 4-Bit-Prim-Checker (Sie müssen die
bruteBase
Ganzzahlvariable in Zeile 473 auf 4 (oder größer) ändern , um dieses Ergebnis zu erhalten).Diese Ausgabe besteht effektiv aus zwei Teilen, dem "Evaluator" auf der rechten Seite, der aus dem Ausdrucksbaum von Stufe 1 erstellt wird, und der "Schalttafel" auf der linken Seite, die die Eingaben so vertauscht und aufteilt, dass sie in der Tabelle eintreffen Die richtigen Stellen für den "Evaluator".
Es gibt an dieser Stelle einen erheblichen Spielraum für die Komprimierung des Layouts, aber das Programm erledigt derzeit nur sehr wenige derartige Arbeiten. Der Code für diese Stufe ist schrecklich, aber darunter ziemlich einfach (siehe "orifnot" -Methode). Die Ausgabe wird an Stufe 3 übergeben.
Stufe 3 : Der "Drucker" nimmt die Ausgabe vom "Organizer" und druckt die entsprechenden 4x5 überlappenden "Zellen" zusammen mit der Stromleitung. Unten sehen Sie eine Animation des brachialen 4-Bit-Prime-Checkers, der prüft, ob 5 ein Prime ist.
Code der Mangel an Einrücken ist über die SE 30k Zeichenbegrenzung zu vermeiden , gehen die es sonst der Fall wäre :
Ein zusätzlicher Testfall:
Dies prüft, ob zwei benachbarte (nicht umschließende) Bits beide 1s sind (z. B. wahr für 0110, aber falsch für 0101 und 1001)
quelle
I
und dessen Ausgaben ein neues Domino-Layout