Count common Game of Life patterns

Question

The task here is to read from a Golly .rle or plaintext file (your choice) whose filename is provided (on STDIN or as a command line argument) and identify and count the common patterns in the grid encoded therein.

Alternatively, you may choose to have the contents of the file provided directly over STDIN instead.

Your program should be able to identify and distinguish at least the fifteen most common strict still lifes and the five most common oscillators, plus gliders.

All phases of these oscillators should be recognized, as should all four phases of the glider.

It should output a list containing the final count of each pattern, with the name and quantity of each pattern on a separate line. Your program may include in the ouput list either all of these patterns or only the ones of which at least one was found.

Patterns which are part of other patterns being counted should not be counted. (for example, the 8-cell phase of a beacon should not also be counted as two blocks, and a ship-tie should not also be counted as two ships)

You may assume that the input has already stabilized and contains no patterns not in the aformentioned set. You may also assume that the input grid will fit within a 1024x1024 box.

This is code-golf, so the shortest program wins.

RLE file format description

An RLE file contains a run-length encoded life grid. All lines starting with # are comments and should be ignored.

The first non-empty, non-comment line is of the form x=<width>,y=<height>,rule=<rule>. For the purposes of this task, the rule will always be B3/S23. It may contain spaces which should be stripped before processing this line (of course, it is not necessary to process this line at all.)

Non-comment lines after the first should be treated as a single string. This should consist only of decimal digits, the characters $, b, and o, and line breaks, and will not end with a digit. Line breaks are to be ignored, but you may assume that line breaks will not interrupt strings of digits.

This may be terminated by a single !.

b represents a dead cell, o represents a live cell, and $ represents the end of a row. Any decimal number indicates that the following symbol is to be treated as repeating that many times.

Plaintext pattern encoding

The other option is to read the pattern in another plaintext format described here. In this encoding, off cells are represented with hyphens and on cells are represented with uppercase Os, with newlines separating rows.

You may assume that all non-comment lines will be padded to equal length with hyphens.

Lines starting with ! are comments and are to be ignored.

Some test cases

RLE:

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

Plaintext:

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

Results:

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

Plaintext:

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

Results:

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!

Plaintext:

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

Results:

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!

Plaintext:

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

Results:

Pentadecathlon 1

Bonus

If you support both input formats (using the file extension [.rle for rle files and .cells for plaintext- how other extensions are to be read is undefined] or a command line flag to distinguish between them) you may subtract 5% from your score.

Answer 1

Haskell, 2417 bytes

This took quite a while and there are still a few bugs, but I got several tricks working so it was worth it.

Notes:

• It only accepts the plaintext format, passed to STDIN
• It takes something like O(n^20) time
• I assumed that the number of characters in non-comment lines is constant (within a specific input), as that's how it is in the examples
• Craziest trick was how the patterns are unpacked, extracting the elements at positions (column number) modulo (the length of the output) to build the array.

It combines a few key ideas:

• patterns and symmetries can be pre-computed
• a single pattern can be packed into an integer, with dimensions known
• finding all submatrices is easy
• counting equalities is easy

Here's the 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])

Here's the Mathematica code used to pack an array of 0,1's into the format later unpacked by the haskell program:

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

Here's a much more complete ungolfing of the code:

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