Cuente los patrones comunes del juego de la vida

La tarea aquí es leer un .rlearchivo Golly o de texto sin formato (su elección) cuyo nombre de archivo se proporciona (en STDIN o como un argumento de línea de comando) e identificar y contar los patrones comunes en la cuadrícula codificada allí.

Alternativamente, puede optar por que el contenido del archivo se proporcione directamente a través de STDIN.

Su programa debe poder identificar y distinguir al menos los quince bodegones estrictos más comunes y los cinco osciladores más comunes , además de planeadores .

Deben reconocerse todas las fases de estos osciladores, al igual que las cuatro fases del planeador.

Debería generar una lista que contenga el conteo final de cada patrón, con el nombre y la cantidad de cada patrón en una línea separada. Su programa puede incluir en la lista de salida todos estos patrones o solo aquellos en los que se encontró al menos uno.

Los patrones que forman parte de otros patrones que se cuentan no deben contarse. (por ejemplo, la fase de 8 celdas de una baliza no debe contarse también como dos bloques, y un empate no debe contarse también como dos barcos)

Puede suponer que la entrada ya se ha estabilizado y no contiene patrones que no estén en el conjunto mencionado anteriormente. También puede suponer que la cuadrícula de entrada se ajustará dentro de un cuadro de 1024x1024.

Este es el código de golf , por lo que gana el programa más corto.

Descripción del formato de archivo RLE

Un archivo RLE contiene una cuadrícula de vida codificada de longitud de ejecución. Todas las líneas que comienzan con #son comentarios y deben ignorarse.

La primera línea no vacía, sin comentarios es de la forma x=<width>,y=<height>,rule=<rule>. Para los propósitos de esta tarea, la regla siempre será B3/S23. Puede contener espacios que deben eliminarse antes de procesar esta línea (por supuesto, no es necesario procesar esta línea en absoluto).

Las líneas sin comentarios después de la primera deben tratarse como una sola cadena. Esto debe consistir solo en dígitos decimales, los caracteres $, by o, y saltos de línea, y no terminará con un dígito. Se deben ignorar los saltos de línea, pero puede suponer que los saltos de línea no interrumpirán las cadenas de dígitos.

Esto puede ser terminado por un solo !.

brepresenta una celda muerta, orepresenta una celda viva y $representa el final de una fila. Cualquier número decimal indica que el siguiente símbolo debe tratarse como una repetición tantas veces.

Codificación de patrón de texto sin formato

La otra opción es leer el patrón en otro formato de texto sin formato descrito aquí. En esta codificación, las celdas apagadas se representan con guiones y las celdas encendidas se representan con letras mayúsculas, con líneas nuevas que separan las filas.

Puede suponer que todas las líneas sin comentarios se rellenarán con la misma longitud con guiones.

Las líneas que comienzan con !son comentarios y deben ignorarse.

Algunos casos de prueba

RLE:

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

Texto sin formato:

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

Resultados:

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

Texto sin formato:

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

Resultados:

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!

Texto sin formato:

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

Resultados:

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!

Texto sin formato:

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

Resultados:

Pentadecathlon 1

Prima

Si admite ambos formatos de entrada (usando la extensión de archivo [ .rlepara archivos rle y .cellspara texto sin formato, cómo no se definen otras extensiones] o un indicador de línea de comando para distinguirlos) puede restar un 5% de su puntaje.

Haskell, 2417 bytes

Esto tomó bastante tiempo y todavía hay algunos errores, pero obtuve varios trucos funcionando, así que valió la pena.

Notas:

• Solo acepta el formato de texto sin formato, pasado a STDIN
• Toma algo como el tiempo O (n ^ 20)
• Supuse que el número de caracteres en las líneas sin comentarios es constante (dentro de una entrada específica), ya que así es en los ejemplos
• El truco más loco fue cómo se descomprimen los patrones, extrayendo los elementos en el módulo de posiciones (número de columna) (la longitud de la salida) para construir la matriz.

Combina algunas ideas clave:

• los patrones y las simetrías pueden calcularse previamente
• un solo patrón puede empaquetarse en un entero, con dimensiones conocidas
• encontrar todas las submatrices es fácil
• contar las igualdades es fácil

Aquí está el código:

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])

Aquí está el código de Mathematica que se usa para empaquetar una matriz de 0,1 en el formato que el programa haskell descomprimió más tarde:

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]}

Aquí hay una versión mucho más completa del código:

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]]