Zählen Sie die gängigen Game of Life-Muster

Die Aufgabe hierbei ist, aus einer Golly- .rleoder Klartextdatei (Ihrer Wahl), deren Dateiname (in STDIN oder als Befehlszeilenargument) angegeben ist, zu lesen und die gemeinsamen Muster in dem darin codierten Raster zu identifizieren und zu zählen.

Alternativ können Sie den Inhalt der Datei auch direkt über STDIN bereitstellen lassen.

Ihr Programm sollte in der Lage sein, mindestens die fünfzehn häufigsten strengen Stillleben und die fünf häufigsten Oszillatoren sowie Segelflugzeuge zu identifizieren und zu unterscheiden .

Alle Phasen dieser Oszillatoren sollten ebenso wie alle vier Phasen des Segelflugzeugs erkannt werden.

Es sollte eine Liste ausgegeben werden, die die endgültige Anzahl jedes Musters enthält, wobei der Name und die Anzahl jedes Musters in einer separaten Zeile stehen. Ihr Programm kann entweder alle diese Muster oder nur diejenigen, von denen mindestens eines gefunden wurde, in die Ausgabeliste aufnehmen.

Muster, die Teil anderer zu zählender Muster sind, sollten nicht gezählt werden. (Beispielsweise sollte die 8-Zellen-Phase eines Beacons nicht als zwei Blöcke gezählt werden, und ein Schiffsbinder sollte nicht als zwei Schiffe gezählt werden.)

Sie können davon ausgehen, dass sich die Eingabe bereits stabilisiert hat und keine Muster enthält, die nicht im oben genannten Satz enthalten sind. Sie können auch davon ausgehen, dass das Eingaberaster in eine 1024x1024-Box passt.

Das ist Code-Golf , also gewinnt das kürzeste Programm.

Beschreibung des RLE-Dateiformats

Eine RLE-Datei enthält ein lauflängencodiertes Lebensraster. Alle Zeilen, die mit beginnen, #sind Kommentare und sollten ignoriert werden.

Die erste nicht leere, nicht kommentierte Zeile ist von der Form x=<width>,y=<height>,rule=<rule>. Für die Zwecke dieser Aufgabe gilt immer die Regel B3/S23. Es kann Leerzeichen enthalten, die vor der Verarbeitung dieser Zeile entfernt werden sollten (natürlich ist es nicht erforderlich, diese Zeile überhaupt zu verarbeiten.)

Nichtkommentarische Zeilen nach der ersten sollten als einzelne Zeichenfolge behandelt werden. Dies sollte nur aus Dezimalstellen, den Zeichen $, bund ound Zeilenumbrüchen bestehen und endet nicht mit einer Ziffer. Zeilenumbrüche sind zu ignorieren, Sie können jedoch davon ausgehen, dass Zeilenumbrüche Ziffernfolgen nicht unterbrechen.

Dies kann durch eine einzelne beendet werden !.

brepräsentiert eine tote Zelle, orepräsentiert eine lebende Zelle und $repräsentiert das Ende einer Reihe. Jede Dezimalzahl gibt an, dass das folgende Symbol so oft wiederholt wird.

Klartextmuster-Codierung

Die andere Möglichkeit besteht darin, das Muster in einem anderen hier beschriebenen Klartextformat zu lesen . In dieser Codierung werden off-Zellen mit Bindestrichen und on-Zellen mit Großbuchstaben dargestellt, wobei Zeilen durch Zeilenumbrüche getrennt werden.

Sie können davon ausgehen, dass alle nicht kommentierten Zeilen mit Bindestrichen auf die gleiche Länge aufgefüllt werden.

Zeilen, die mit beginnen, !sind Kommentare und müssen ignoriert werden.

Einige Testfälle

RLE:

#This is a comment
x = 35, y = 16, rule = B3/S23
bo$2o$obo5$22bo$22bo$22bo2$18b3o3b3o2$22bo$22bo10b2o$22bo10b2o!

Klartext:

!This is a comment
-O---------------------------------
OO---------------------------------
O-O--------------------------------
-----------------------------------
-----------------------------------
-----------------------------------
-----------------------------------
----------------------O------------
----------------------O------------
----------------------O------------
-----------------------------------
------------------OOO---OOO--------
-----------------------------------
----------------------O------------
----------------------O----------OO
----------------------O----------OO

Ergebnisse:

Glider 1
Blinker 4
Block 1

RLE:

x = 27, y = 15, rule = B3/S23
5b2o$5b2o9$11bo$o9bobo$o9bobo$o10bo12b3o!
#Here's a comment at the end

Klartext:

-----OO--------------------
-----OO--------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
-----------O---------------
O---------O-O--------------
O---------O-O--------------
O----------O------------OOO
!Here's a comment at the end

Ergebnisse:

Block 1
Blinker 2
Beehive 1

RLE:

#You may have multiple comments
#As shown here
x = 13, y = 11, rule = B3/S23
2o$2o2$12bo$12bo$12bo$2b2o$2b2o4b2o$7bo2bo$7bobo$8bo!

Klartext:

!You may have multiple comments
!As shown here
OO-----------
OO-----------
-------------
------------O
------------O
------------O
--OO---------
--OO----OO---
-------O--O--
-------O-O---
--------O----

Ergebnisse:

Block 2
Blinker 1
Loaf 1

RLE:

# Pentadecathlon
# Discovered by John Conway
# www.conwaylife.com/wiki/index.php?title=Pentadecathlon
x = 10, y = 3, rule = B3/S23
2bo4bo2b$2ob4ob2o$2bo4bo!

Klartext:

! Pentadecathlon
! Discovered by John Conway
! www.conwaylife.com/wiki/index.php?title=Pentadecathlon
--O----O--
OO-OOOO-OO
--O----O--

Ergebnisse:

Pentadecathlon 1

Bonus

Wenn Sie beide Eingabeformate unterstützen (unter Verwendung der Dateierweiterung [ .rlefür RLE-Dateien und .cellsfür Klartext - wie andere Erweiterungen gelesen werden sollen, ist nicht definiert] oder eines Befehlszeilenflags zur Unterscheidung), können Sie 5% von Ihrer Punktzahl abziehen.

Haskell, 2417 Bytes

Das hat eine Weile gedauert und es gibt immer noch ein paar Fehler, aber ich habe mehrere Tricks durchgearbeitet, sodass es sich gelohnt hat.

Anmerkungen:

• Es wird nur das an STDIN übergebene Klartextformat akzeptiert
• Es dauert so etwas wie O (n ^ 20) Zeit
• Ich habe angenommen, dass die Anzahl der Zeichen in Nicht-Kommentarzeilen (innerhalb einer bestimmten Eingabe) konstant ist, wie es in den Beispielen der Fall ist
• Der verrückteste Trick war, wie die Muster entpackt werden, indem die Elemente an Positionen (Spaltennummer) modulo (die Länge der Ausgabe) extrahiert werden, um das Array zu erstellen.

Es vereint einige Schlüsselideen:

• Muster und Symmetrien können vorberechnet werden
• Ein einzelnes Muster kann mit bekannten Abmessungen in eine ganze Zahl gepackt werden
• Alle Submatrizen zu finden ist einfach
• Gleichheitszählung ist einfach

Hier ist der Code:

r=[1..20]
a!0=a!!0
a!x=tail a!(x-1)
u[_,x,y,l]=[[odd$div l$2^i|i<-[0..y],mod i x==j]|j<-[0..x-1]]
main=interact(\s->let q=[map(=='O')l|l<-lines s,l!0/='!']in let g=[i|i<-[[[0,3,11,3339,0,4,11,924,0,4,11,3219,0,3,11,1638,1,4,15,19026,1,4,15,9636,2,3,11,1386,2,4,11,1686,3,7,48,143505703994502,3,7,48,26700311308320,3,7,48,213590917399170,3,7,48,8970354435120,4,2,3,15,5,3,8,171,5,3,8,174,5,3,8,426,5,3,8,234,6,4,15,36371,6,4,15,12972,6,4,15,51313,6,4,15,13644,6,4,15,50259,6,4,15,12776,6,4,15,51747,6,4,15,6028,7,4,15,26962,7,4,15,9622,7,4,15,19094,7,4,15,27044,8,5,24,9054370,8,5,24,2271880,9,4,15,51794,9,4,15,13732,9,4,15,19027,9,4,15,9644,10,4,19,305490,10,5,19,206412,10,5,19,411942,10,4,19,154020,11,3,8,427,11,3,8,238,12,6,35,52217012547,12,6,35,3306785328,13,3,8,170,14,3,8,428,14,3,8,458,14,3,8,107,14,3,8,167,14,3,8,482,14,3,8,302,14,3,8,143,14,3,8,233,14,3,8,241,14,3,8,157,14,3,8,286,14,3,8,370,14,3,8,181,14,3,8,115,14,3,8,346,14,3,8,412,15,4,15,51219,15,4,15,12684,15,4,15,52275,15,4,15,13260,16,1,2,7,16,3,2,7,17,3,29,313075026,17,10,29,139324548,17,3,23,16252911,17,8,23,16760319,17,5,49,152335562622276,17,10,49,277354493774076,17,7,69,75835515713922895368,17,10,69,138634868908666122360,17,9,89,135722011765098439128942648,17,10,89,58184575467336340020006960,17,5,59,160968502306438596,17,12,59,145347113669124612,17,5,59,524156984170595886,17,12,59,434193401052698118,17,5,69,164495599269019571652,17,14,69,222245969722444385292,17,5,69,517140479305239282702,17,14,69,222262922122170485772,17,3,47,83020951028178,17,16,47,39740928107556,17,3,35,62664969879,17,12,35,40432499049,17,3,41,1581499314234,17,14,41,1293532058322,17,3,41,4349006881983,17,14,41,3376910168355,17,3,47,92426891685930,17,16,47,83780021865522,17,3,47,79346167206930,17,16,47,11342241794640,18,13,168,166245817041425752669390138490014048702557312780060,18,15,224,1711376967527965679922107419525530922835414769336784993839766570000,18,13,168,141409121010242927634239017227763246261766273041932,19,2,7,126,19,4,7,231,19,4,7,126,19,2,7,189,19,4,15,24966,19,4,15,18834,19,4,15,10644,19,4,15,26646]!p|p<-[h..h+3]]|h<-[0,4..424]],j<-[[[q!y!x|x<-[a..a+c]]|y<-[b..b+d]]|c<-r,d<-r,a<-[0..(length$q!0)-c-1],b<-[0..length q-d-1]],u i==j]in show[(words"aircraftcarrier barge beehive biloaf1 block boat eater1 loaf longbarge longboat mango ship shiptie tub glider beacon blinker pentadecathlon pulsar toad"!(e!0),sum[1|f<-g,e!0==f!0])|e<-g])

Hier ist der Mathematica-Code, der verwendet wird, um ein Array von 0,1 in das Format zu packen, das später vom haskell-Programm entpackt wurde:

rotate[m_]:=Transpose[Map[Reverse,m]]
findInversePermutation[m_]:=Block[{y=Length[First[m]], x=Length[m]}, InversePermutation[FindPermutation[Flatten[m], Flatten[Table[Table[Flatten[m][[i+1]], {i, Select[Range[0, x * y - 1], Mod[#, x]==j&]}], {j, 0, x - 1}]]]]]
enumShape[m_]:=Partition[Range[1, Length[Flatten[m]]], Length[m[[1]]]]
pack[m_]:={Length[rotate[rotate[m]]], Length[Flatten[rotate[rotate[m]]]], FromDigits[Permute[Flatten[rotate[rotate[m]]], findInversePermutation[enumShape[rotate[rotate[m]]]]], 2]}

Hier ist ein viel vollständigeres Auflösen des Codes:

range = [1..16]          -- all of the patterns fall within this range

list ! 0        = list !! 0           -- this is a simple generic (!!)
list ! position = (tail list) ! (position - 1)

unpack [_, unpackedLength, unpackedSize, packed] = [ [odd $ div packed (2^i) | i <- [0..unpackedSize], (mod i unpackedLength) == j] | j <- [0..unpackedLength - 1]]

main=interact doer

doer input = show $ tallyByFirst (words nameString) foundPatterns -- this counts equalities between the list of patterns and the submatrices of the input
  where
    parsed = parse input -- this selects the non-comment lines and converts to an array of Bool's
    foundPatterns = countOccurrences partitioned subArrays
    subArrays     = allSubArrays parsed
    partitioned   = modPartition compressed 428 4 -- this partitions the compressed patterns into the form [name number, x length, x length * y length, packed integer]

countOccurrences patterns subArrays = [pattern | pattern <- patterns, subArray <- allSubArrays q, unpack pattern == subArray]

subArray m offsetX subSizeX offsetY subSizeY = [[m ! y ! x | x <- [offsetX..offsetX + subSizeX]] | y <- [offsetY..offsetY + subSizeY]]

allSubArrays m = [subArray m offsetX subSizeX offsetY subSizeY | subSizeX <- range, subSizeY <- range, offsetX <- [0.. (length $ head m) - subSizeX - 1], offsetY <- [0..(length m) - subSizeY - 1]]

tallyByFirst names list = [ (names ! (a ! 0), sum [1 | a <- list, (head a) == (head b)]) | b <- list]

parse string = [map (=='O') line | line <- lines string, head line /= '!']

modPartition list chunksize = [ [list ! position | position <- [offset..offset + chunksize - 1]] | offset <- [0, chunksize..(length list) - chunksize]]