Считайте общие шаблоны игры жизни

Задача здесь состоит в том, чтобы прочитать из .rleфайла Golly или открытого текста (на ваш выбор), имя файла которого предоставлено (в STDIN или в качестве аргумента командной строки), и идентифицировать и подсчитать общие шаблоны в сетке, закодированной в них.

В качестве альтернативы вы можете выбрать, чтобы содержимое файла предоставлялось непосредственно через STDIN.

Ваша программа должна быть в состоянии идентифицировать и различать по крайней мере пятнадцать наиболее распространенных строгих натюрмортов и пять наиболее распространенных осцилляторов плюс планеры .

Все фазы этих генераторов должны быть распознаны, как и все четыре фазы планера.

Он должен вывести список, содержащий итоговое количество каждого шаблона, с именем и количеством каждого шаблона в отдельной строке. Ваша программа может включить в список выходных данных либо все эти шаблоны, либо только те, из которых хотя бы один был найден.

Шаблоны, которые являются частью других учитываемых шаблонов, не должны учитываться. (например, 8-элементная фаза маяка также не должна учитываться как два блока, а привязка корабля также не должна учитываться как два корабля)

Вы можете предположить, что вход уже стабилизировался и не содержит шаблонов, не входящих в упомянутый набор. Вы также можете предположить, что входная сетка поместится в поле 1024x1024.

Это код-гольф , поэтому выигрывает самая короткая программа.

Описание формата файла RLE

Файл RLE содержит закодированную сетку жизни с длиной цикла. Все строки, начинающиеся с, #являются комментариями и должны игнорироваться.

Первая непустая строка без комментариев имеет вид x=<width>,y=<height>,rule=<rule>. Для целей этой задачи правило всегда будет B3/S23. Он может содержать пробелы, которые должны быть удалены перед обработкой этой строки (конечно, нет необходимости обрабатывать эту строку вообще.)

Строки без комментариев после первой должны рассматриваться как одна строка. Это должно состоять только из десятичных цифр, символов $, bи o, и разрывов строк, и не будет заканчиваться цифрой. Разрывы строк следует игнорировать, но вы можете предположить, что разрывы строк не будут прерывать строки цифр.

Это может быть прекращено одним !.

bпредставляет мертвую клетку, oпредставляет живую клетку и $представляет конец строки. Любое десятичное число указывает на то, что следующий символ должен рассматриваться как повторяющийся столько раз.

Кодировка в виде простого текста

Другой вариант - прочитать шаблон в другом формате открытого текста, описанном здесь. В этом кодировании отключенные ячейки представлены дефисами, а в ячейках - прописными буквами, с символами новой строки, разделяющими строки.

Вы можете предположить, что все строки без комментариев будут дополнены до дефисов одинаковой длины.

Строки, начинающиеся с, !являются комментариями и должны игнорироваться.

Некоторые тестовые случаи

УПИ:

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

Простой текст:

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

Результаты:

Glider 1
Blinker 4
Block 1

УПИ:

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

Простой текст:

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

Результаты:

Block 1
Blinker 2
Beehive 1

УПИ:

#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!

Простой текст:

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

Результаты:

Block 2
Blinker 1
Loaf 1

УПИ:

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

Простой текст:

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

Результаты:

Pentadecathlon 1

бонус

Если вы поддерживаете оба формата ввода (используя расширение файла [ .rleдля файлов rle и .cellsдля открытого текста - как не нужно определять другие расширения) или флаг командной строки, чтобы различать их), вы можете вычесть 5% от вашей оценки.

Haskell, 2417 байт

Это заняло много времени, и все еще есть несколько ошибок, но я получил несколько трюков, так что это того стоило.

Заметки:

• Он принимает только открытый текст, переданный в STDIN
• Требуется что-то вроде O (n ^ 20) времени
• Я предположил, что количество символов в строках без комментариев является постоянным (в пределах определенного ввода), как это происходит в примерах
• Сумасшедший трюк заключался в том, как распаковывать шаблоны, извлекая элементы в позициях (номер столбца) по модулю (длина вывода) для построения массива.

Он сочетает в себе несколько ключевых идей:

• шаблоны и симметрии могут быть предварительно вычислены
• один шаблон может быть упакован в целое число с известными размерами
• найти все подматрицы легко
• считать равенства легко

Вот код:

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

Вот код Mathematica, используемый для упаковки массива 0,1 в формат, позже распакованный программой haskell:

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

Вот гораздо более полное раскрытие кода:

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