Ich verspreche, dies wird meine letzte Herausforderung in Bezug auf Diamantkacheln sein (zumindest für eine Weile). Positiv zu vermerken ist, dass diese Herausforderung nichts mit ASCII-Kunst zu tun hat und auch kein Code-Golf ist.
Zur Erinnerung, jedes Sechseck kann mit drei verschiedenen Diamanten versehen werden:
Eine interessante Frage ist, wie viele dieser Kacheln für eine bestimmte Sechseckgröße existieren. Es scheint, dass diese Zahlen ziemlich gründlich untersucht wurden und in OEIS A008793 zu finden sind .
Das Problem wird jedoch schwieriger, wenn wir uns fragen, wie viele Kacheln bis zur Drehung und Reflexion vorhanden sind . Beispielsweise existieren für die Seitenlänge N = 2 die folgenden 20 Kacheln:
____ ____ ____ ____ ____ ____ ____ ____ ____ ____
/\_\_\ /\_\_\ /\_\_\ /\_\_\ /_/\_\ /_/\_\ /\_\_\ /_/\_\ /_/\_\ /_/\_\
/\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
\/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
\/_/_/ \/_/_/ \/_/_/ \_\/_/ \/_/_/ \/_/_/ \_\/_/ \_\/_/ \_\/_/ \_\/_/
____ ____ ____ ____ ____ ____ ____ ____ ____ ____
/_/_/\ /\_\_\ /_/\_\ /_/_/\ /_/\_\ /_/\_\ /_/_/\ /_/_/\ /_/_/\ /_/_/\
/\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
\/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
\/_/_/ \_\_\/ \_\/_/ \_\/_/ \_\_\/ \_\_\/ \_\/_/ \_\_\/ \_\_\/ \_\_\/
Viele davon sind jedoch in Bezug auf Rotation und Reflexion identisch. Wenn wir diese Symmetrien berücksichtigen, bleiben nur 6 verschiedene Kacheln übrig:
____ ____ ____ ____ ____ ____
/\_\_\ /\_\_\ /\_\_\ /_/\_\ /_/\_\ /_/\_\
/\/\_\_\ /\/_/\_\ /\/_/_/\ /\_\/_/\ /\_\/_/\ /_/\/\_\
\/\/_/_/ \/\_\/_/ \/\_\_\/ \/\_\_\/ \/_/\_\/ \_\/\/_/
\/_/_/ \/_/_/ \/_/_/ \/_/_/ \_\/_/ \_\/_/
2 2 6 6 1 3
Dabei geben die Zahlen die Vielzahl der Kacheln an. Beachten Sie, dass es für größere Sechsecke auch Fliesen mit den Multiplikationen 4 und 12 gibt.
Es scheint, dass die Anzahl der Kacheln bis zur Symmetrie weniger gründlich untersucht wurde. Der OEIS-Eintrag A066931 listet nur die fünf Begriffe auf:
1, 1, 6, 113, 20174
wobei der erste Term für die Seitenlänge N = 0
und der letzte Term für die Seitenlänge steht N = 4
.
Ich bin sicher, wir können es besser machen!
Ihre Aufgabe ist es, die Anzahl der Kacheln für eine bestimmte Seitenlänge zu berechnen.
Dies ist der schnellste Code . Ihre Punktzahl ist die höchste Seitenlänge, N
für die Ihr Code innerhalb von 30 Minuten auf meinem Computer das richtige Ergebnis liefert . Im Falle eines Unentschieden akzeptiere ich die Einsendung, die das Ergebnis für das N
schnellste ergibt .
Wie üblich dürfen Sie keine bereits bekannten Ergebnisse fest codieren, um den Tie-Breaker zu gewinnen. Der zu lösende Algorithmus N = 3
sollte mit dem zu lösenden identisch sein N = 5
.
Ihr Beitrag darf nicht mehr als 4 GB Arbeitsspeicher belegen. Ich werde etwas Spielraum geben, wenn Sie nahe an diesem Limit operieren, aber wenn Sie durchweg über diesem Limit sind oder wenn Sie deutlich darüber hinausgehen, werde ich das N
für Ihre Einreichung nicht berücksichtigen.
Ich werde alle Einsendungen auf meinem Windows 8-Computer testen. Stellen Sie daher sicher, dass Ihre bevorzugte Sprache unter Windows frei verfügbar ist. Die einzige Ausnahme ist Mathematica (weil ich eine Lizenz dafür habe). Bitte fügen Sie Anweisungen zum Kompilieren / Ausführen Ihres Codes bei.
Natürlich können Sie in Ihrer Freizeit mehr Begriffe berechnen (für die Wissenschaft und für andere, um ihre Zahlen zu überprüfen), aber die Punktzahl Ihrer Antwort wird in diesen 30 Minuten ermittelt.
quelle
N = 6
einer Ausgabe von mehr als 10 ^ 12 mit ziemlicher Sicherheit eine nicht konstruktive Lösung erforderlich ist, um dieses Ziel zu erreichen.Antworten:
Algebra, Graphentheorie, Möbius-Inversion, Forschung und Java
Die Symmetriegruppe des Sechsecks ist die Diedergruppe der Ordnung 12 und wird durch eine Drehung um 60 Grad und einen Spiegelschlag über einen Durchmesser erzeugt. Es hat 16 Untergruppen, aber einige von ihnen sind in nicht-trivialen Konjugationsgruppen (diejenigen, die nur Reflexionen haben, haben 3 Wahlmöglichkeiten der Achse), so dass es 10 grundlegend verschiedene Symmetrien gibt, die eine Kachelung des Sechsecks haben kann:
Die Anzahl der Diamantkacheln einer Teilmenge eines Dreiecksgitters kann als Determinante berechnet werden. Mein ursprünglicher Ansatz bestand darin, für jede der Symmetrien des Sechsecks eine Determinante zu erstellen, um die Anzahl der Kacheln zu berechnen, die mindestens diese Symmetrien aufweisen ; und verwenden Sie dann die Möbius-Inversion in der Inzidenzalgebra ihres Posets (im Grunde genommen eine Verallgemeinerung des Einschluss-Ausschluss-Prinzips), um die Anzahl der Kacheln zu berechnen, deren Symmetriegruppe genau jeder der 10 Fälle ist. Einige der Symmetrien haben jedoch schlechte Randbedingungen, so dass ich gezwungen war, über exponentiell viele Determinanten zu summieren. Zum Glück sind die Werte für erhalten
n < 10
gab mir genug Daten, um relevante Sequenzen in OEIS zu identifizieren und eine geschlossene Form zusammenzusetzen (für einen Wert von "closed", der endliche Produkte erlaubt). In der formalen Beschreibung, die ich vorbereitet habe, um die OEIS-Sequenzaktualisierungen zu rechtfertigen, werden die Sequenzen ein wenig besprochen und auf Beweise verwiesen .Sobald die Doppelzählung erledigt ist, stellt sich heraus, dass sich vier der zehn Werte ordentlich aufheben, sodass wir nur die verbleibenden sechs berechnen und dann eine gewichtete Summe erstellen müssen.
Dieser Code dauert
N=1000
auf meinem Computer weniger als 30 Sekunden .quelle
C
Einführung
Wie David Carraher bemerkte, schien die einfachste Möglichkeit, die Sechseckkacheln zu analysieren, darin zu bestehen, ihren Isomorphismus mit dem dreidimensionalen jungen Diagramm auszunutzen, das im Wesentlichen ein XY-Quadrat ist, das mit ganzzahligen Höhenbalken gefüllt ist, deren Z-Höhen gleich bleiben oder zunehmen müssen wenn die z-Achse angefahren wird.
Ich habe mit einem Algorithmus zum Ermitteln der Summen begonnen, der sich besser für die Symmetriezählung eignet als der veröffentlichte Algorithmus, der auf einer Abweichung von einer der drei kartesischen Achsen basiert.
Algorithmus
Ich beginne damit, die Zellen der x-, y- und z-Ebene mit Einsen zu füllen, während der Rest des Bereichs Nullen enthält. Sobald dies erledigt ist, baue ich das Muster Schicht für Schicht auf, wobei jede Schicht die Zellen enthält, die einen gemeinsamen 3D-Manhattan-Abstand vom Ursprung haben. Eine Zelle kann nur eine 1 enthalten, wenn die drei darunter liegenden Zellen auch eine 1 enthalten. Wenn eine davon eine 0 enthält, muss die Zelle eine 0 sein.
Der Vorteil des Aufbaus des Musters auf diese Weise besteht darin, dass jede Schicht symmetrisch zur x = y = z-Linie ist. Dies bedeutet, dass jede Schicht unabhängig auf Symmetrie überprüft werden kann.
Symmetrieprüfung
Die Symmetrien des Festkörpers sind wie folgt: Dreifache Drehung um die x = y = z-Linie -> Dreifache Drehung um das Sechseckzentrum; und 3 x Reflexionen über die 3 Ebenen, die die Linie x = y = z enthalten, und jede der Achsen x, y, z -> Reflexion über die Linien durch die Sechseckecken.
Dies ergibt nur eine 6-fache Symmetrie. Um die volle Symmetrie des Sechsecks zu erhalten, muss eine andere Art von Symmetrie berücksichtigt werden. Jeder Körper (aufgebaut aus Einsen) hat einen komplementären Körper (aufgebaut aus Nullen). Wenn N ungerade ist, muss sich der komplementäre Festkörper vom ursprünglichen Festkörper unterscheiden (da nicht die gleiche Anzahl von Würfeln möglich ist). Wenn der komplementäre Volumenkörper jedoch gedreht wird, wird festgestellt, dass seine 2D-Darstellung als Diamantkachel (mit Ausnahme einer zweifachen Symmetrieoperation) mit dem ursprünglichen Volumenkörper identisch ist. Wenn N gerade ist, ist es möglich, dass der Festkörper selbstinvers ist.
Dies geht aus den Beispielen für N = 2 in der Frage hervor. Von links betrachtet sieht das erste Sechseck wie ein fester Würfel mit 8 kleinen Würfeln aus, während das letzte Sechseck wie eine leere Hülle mit 0 kleinen Würfeln aussieht. Von rechts gesehen ist das Gegenteil der Fall. Das 3., 4. und 5. Sechseck sowie das 16., 17. und 18. Sechseck scheinen entweder 2 oder 6 Würfel zu enthalten und ergänzen sich daher in 3 Dimensionen. Sie sind in 2 Dimensionen durch eine 2-fache Symmetrieoperation (2-fache Drehung oder Reflexion um eine Achse durch die Sechskantkanten) miteinander verbunden. Andererseits zeigen das 9., 10., 11. und 12. Sechseck 3D-Muster, die sind ihre eigenen Komplemente und haben daher eine höhere Symmetrie (dies sind daher die einzigen Muster mit ungerader Multiplizität).
Es ist zu beachten, dass (N ^ 3) / 2 Würfel eine notwendige Bedingung sind, um sich selbst zu ergänzen, aber im Allgemeinen ist es keine ausreichende Bedingung, wenn N> 2 ist. All dies hat zur Folge, dass bei ungeraden N die Kacheln immer paarweise auftreten (N ^ 3) / 2 Würfel müssen sorgfältig geprüft werden.
Aktueller Code (generiert die richtige Summe für N = 1,2,3,5. Fehler wie für N = 4 beschrieben.)
Ausgabe
Das Programm generiert eine Ausgabetabelle mit 8 Einträgen entsprechend den 8 Symmetrien des Volumenkörpers. Der Körper kann eine der folgenden 4 Symmetrien haben (Schönflies-Notation)
Wenn der Körper genau die Hälfte der Zellen mit Einsen und die Hälfte mit Nullen hat, besteht außerdem die Möglichkeit, alle Einsen und Nullen zu spiegeln und dann die Koordinaten durch die Mitte des Würfelraums zu invertieren. Das nenne ich Selbstkomplement, aber ein mathematischerer Begriff wäre "antisymmetrisch in Bezug auf ein Inversionszentrum".
Diese Symmetrieoperation ergibt eine zweifache Rotationsachse in der Sechskantfliese.
Muster mit dieser Symmetrie werden in einer separaten Spalte aufgelistet. Sie treten nur dort auf, wo N gerade ist.
Meine Zählung scheint für N = 4 leicht abzulaufen. In der Diskussion mit Peter Taylor scheint es, als würde ich keine Fliesen erkennen, die nur eine Symmetrie einer Linie durch die Sechskantkanten haben. Dies liegt vermutlich daran, dass ich nicht auf Selbstkomplement (Antisymmetrie) für andere Operationen als (Inversion) x (Identität) getestet habe ) kann die fehlenden Symmetrien aufdecken. Ich würde dann erwarten, dass die erste Zeile der Daten für N = 4 so aussieht (16 weniger in c1 und 32 mehr in C1):
Dies würde die Gesamtsummen mit Peters Antwort und https://oeis.org/A066931/a066931.txt in Einklang bringen
Stromausgang ist wie folgt.
Aufgabenliste (aktualisiert)
Fertig, mehr oder weniger
Fertig, Ergebnisse für ungerade N stimmen mit veröffentlichten Daten überein
Dies kann erreicht werden, indem dem Rekursionsaufruf eine weitere Bedingung hinzugefügt wird:
if(s1 && m<n*3-2)f(m + 1,e+d,s1)
Die Laufzeit für N = 5 wird von 5 Minuten auf etwa eine Sekunde verringert. Infolgedessen wird die erste Zeile der Ausgabe zu Gesamtmüll (wie auch die Gesamtsummen), aber wenn die Gesamtsumme bereits aus OEIS bekannt ist, kann die Anzahl der asymmetrischen Kacheln zumindest für ungerade N wiederhergestellt werden.Aber für gerade N würde die Anzahl der asymmetrischen (gemäß c3v-Symmetrien) Festkörper, die sich selbst ergänzen, verloren gehen. In diesem Fall kann ein separates Programm für Volumenkörper mit genau (N ** 3) / 2 Zellen mit einer 1 nützlich sein. Wenn dies verfügbar ist (und korrekt gezählt wird), kann möglicherweise N = 6 ausprobiert werden, die Ausführung dauert jedoch sehr lange.
Nicht erledigt, Einsparungen werden marginal erwartet
Fertig, scheint aber Auslassungen zu haben, siehe N = 4.
Es wird nicht erwartet, dass die Einsparungen so groß sind. Das Unterdrücken von asymmetrischen Figuren beseitigt das meiste davon. Die einzige überprüfte Reflexion ist die Ebene durch die y-Achse (x und z werden später durch Multiplikation mit 3 berechnet.) Figuren mit nur Rotationssymmetrie werden in ihren beiden enantiomeren Formen gezählt. Vielleicht würde es fast doppelt so schnell laufen, wenn nur einer gezählt würde.
Interessant, aber wahrscheinlich gibt es noch andere Fragen auf der Website zu erkunden.
quelle