Bei dieser Herausforderung werden Sie Pseudopolyformen auf dem Snub-Square-Tiling zählen .
Ich denke, dass diese Sequenz im OEIS noch nicht vorhanden ist , daher besteht diese Herausforderung darin, so viele Begriffe wie möglich für diese Sequenz zu berechnen.
Update: Dies ist jetzt auf dem OEIS als A309159 : Anzahl der verallgemeinerten Polyformen auf dem Snub-Square-Tiling mit n Zellen.
Definitionen
Das Snub-Quadrat-Tiling ist ein halbrundes Tiling der Ebene, das aus gleichseitigen Dreiecken und Quadraten besteht.
Eine Pseudopolyform auf dem Snub-Quadrat-Tiling ist eine ebene Figur, die analog zu einem Polyomino durch Zusammenfügen dieser Dreiecke und Quadrate entlang ihrer gemeinsamen Seiten konstruiert wird. Hier ist ein Beispiel für eine Pseudopolyform mit sechs und acht Zellen:
Beispiele
Denn n = 1
es gibt zwei 1-Zellen-Pseudopolyformen, nämlich das Quadrat und das Dreieck:
Denn n = 2
es gibt zwei 2-Zellen-Pseudopolyformen, nämlich ein Quadrat mit einem Dreieck und zwei Dreiecken.
Denn n = 3
es gibt vier 3-Zellen-Pseudopolyformen.
Herausforderung
Das Ziel dieser Herausforderung ist es, so viele Terme wie möglich in dieser Sequenz zu berechnen, die beginnt 2, 2, 4, ...
und bei der der n-te Term die Anzahl der n-Zellen-Pseudopolyformen bis zur Drehung und Reflexion ist.
Führen Sie Ihren Code so lange aus, wie Sie möchten. Der Gewinner dieser Herausforderung ist der Benutzer, der zusammen mit seinem Code die meisten Begriffe der Sequenz veröffentlicht. Wenn zwei Benutzer die gleiche Anzahl von Begriffen veröffentlichen, gewinnt derjenige, der seinen letzten Begriff frühestens veröffentlicht.
(Sobald genügend bekannte Begriffe vorhanden sind, um zu beweisen, dass diese Sequenz noch nicht im OEIS vorhanden ist, erstelle ich einen Eintrag im OEIS und liste den Mitwirkenden als Mitautor auf, wenn er dies wünscht.)
quelle
Antworten:
Haskell
Nun, da nicht nur die Kommentare belegen, dass Peter Taylor als erster genügend Begriffe für die Suche in OEIS angegeben hat, kann ich meine Ergebnisse angeben.
Früher habe ich hexagonale Polyomino gezählt . Abgesehen von einigen Optimierungen ist das, was ich hier mache, sehr ähnlich.
Die Elemente der Kacheln werden wie folgt dargestellt: Sie können in einer fast geraden Linie von links nach rechts (im ersten Bild) zwischen Quadraten und Rechtecken wechseln. Es gibt fast parallel weitere Linien, die in entgegengesetzte Richtungen wackeln. Zusammen vermissen sie einige Dreiecke. Es gibt ähnliche, fast gerade parallele Linien von unten nach oben, die die fehlenden Dreiecke enthalten. Ignorieren Sie nun das Wackeln und verwenden Sie ein kartesisches Koordinatensystem, verwenden Sie jedoch nur ungerade Zahlen für die Koordinaten der Quadrate. Dann erhalten die Dreiecke natürlich Koordinatenpaare mit einer geraden und einer ungeraden Koordinate. Paare mit beiden Koordinaten repräsentieren sogar keine Elemente der Kachelung.
(Sie können auch gerade Zahlen für die Koordinaten der Quadrate verwenden. Ich glaube, ich habe mich auf diese Weise entschieden, weil ich über Reflexion vor Rotation nachgedacht habe.)
Speichern Sie das Programm in einer Datei mit einem Namen wie
cgp.hs
und kompilieren Sie mitghc -O2 -o cgp cgp.hs
. Es verwendet entweder ein numerisches Befehlszeilenargument und berechnet die Anzahl der Polyominoes dieser Größe oder keines. In diesem Fall werden Werte berechnet, bis sie gestoppt werden.Probieren Sie es online!
quelle
2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146, 22927, 74137, 241461, 790838, 2603210, 8604861, 28549166, 95027832
Ich werde einen Einsatz machen, bevor Christian Sievers eine Antwort für n = 18 gibt. Dies ist so weit ich mit dem aktuellen Code und 16 GB RAM gehen kann. Ich musste bereits etwas Geschwindigkeit opfern, um die Speichernutzung zu reduzieren, und ich werde dies noch mehr tun müssen. Ich habe einige Ideen ...
Dieser Ausschnitt ist die SVG aus dem ersten Kommentar.
Code ist C #. Ich habe es mit .Net Core 2.2.6 unter Linux betrieben.
quelle