Policz typowe wzorce Game of Life

Zadanie polega na tym, aby odczytać z pliku Golly .rlelub zwykłego tekstu (do wyboru), którego nazwa pliku jest podana (na STDIN lub jako argument wiersza poleceń) oraz zidentyfikować i policzyć wspólne wzorce w zakodowanej w nim siatce.

Alternatywnie możesz zamiast tego udostępnić zawartość pliku bezpośrednio przez STDIN.

Twój program powinien być w stanie zidentyfikować i rozróżnić co najmniej piętnaście najczęstszych surowych martwych natur i pięć najczęstszych oscylatorów oraz szybowce .

Wszystkie fazy tych oscylatorów powinny zostać rozpoznane, podobnie jak wszystkie cztery fazy szybowca.

Powinien wygenerować listę zawierającą ostateczną liczbę każdego wzorca, z nazwą i ilością każdego wzorca w osobnej linii. Twój program może zawierać na liście wyjść wszystkie te wzorce lub tylko te, z których przynajmniej jeden został znaleziony.

Wzory będące częścią innych zliczanych wzorów nie powinny być liczone. (na przykład 8-komórkowa faza latarni nie powinna być również liczona jako dwa bloki, a remis statku nie powinien być również liczony jako dwa statki)

Możesz założyć, że sygnał wejściowy już się ustabilizował i nie zawiera żadnych wzorców spoza wspomnianego zestawu. Możesz również założyć, że siatka wejściowa zmieści się w polu 1024x1024.

To jest golf golfowy , więc wygrywa najkrótszy program.

Opis formatu pliku RLE

Plik RLE zawiera zakodowaną długość przebiegu siatkę życia. Wszystkie wiersze zaczynające się od #są komentarzami i powinny zostać zignorowane.

Pierwszy niepusty wiersz bez komentarza ma postać x=<width>,y=<height>,rule=<rule>. Dla celów tego zadania reguła zawsze będzie B3/S23. Może zawierać spacje, które należy usunąć przed przetworzeniem tego wiersza (oczywiście nie jest wcale konieczne przetwarzanie tego wiersza).

Wiersze bez komentarza po pierwszym powinny być traktowane jako pojedynczy ciąg. To powinno składać się tylko z cyfr, znaków $, bi o, i przerwy linii, a nie kończy się cyfrą. Podziały linii należy zignorować, ale można założyć, że podziały linii nie będą przerywać ciągów cyfr.

Może to zostać zakończone pojedynczym !.

breprezentuje martwą komórkę, oreprezentuje żywą komórkę i $reprezentuje koniec wiersza. Każda liczba dziesiętna wskazuje, że następujący symbol należy traktować jako powtarzający się tyle razy.

Kodowanie wzorca tekstu jawnego

Inną opcją jest odczytanie wzorca w innym formacie tekstu jawnego opisanym tutaj. W tym kodowaniu komórki poza są reprezentowane łącznikami, a komórki są reprezentowane wielkimi literami Os, z nowymi liniami oddzielającymi rzędy.

Możesz założyć, że wszystkie wiersze bez komentarza zostaną dopełnione do równej długości łącznikami.

Linie zaczynające się od !są komentarzami i należy je zignorować.

Niektóre przypadki testowe

RLE:

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

Zwykły tekst:

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

Wyniki:

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

Zwykły tekst:

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

Wyniki:

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!

Zwykły tekst:

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

Wyniki:

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!

Zwykły tekst:

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

Wyniki:

Pentadecathlon 1

Premia

Jeśli obsługujesz oba formaty wejściowe (użycie rozszerzenia pliku [ .rledla plików rle i .cellszwykłego tekstu - sposób odczytu innych rozszerzeń jest niezdefiniowany] lub flagi linii poleceń do rozróżnienia między nimi), możesz odjąć 5% od wyniku.

Haskell, 2417 bajtów

Zajęło to sporo czasu i wciąż jest kilka błędów, ale mam kilka sztuczek, więc było warto.

Uwagi:

• Akceptuje tylko format zwykłego tekstu, przekazany do STDIN
• Zajmuje to czas podobny do O (n ^ 20)
• Założyłem, że liczba znaków w wierszach bez komentarza jest stała (w ramach określonego wejścia), jak to jest w przykładach
• Najbardziej szaloną sztuczką było rozpakowywanie wzorów, wyodrębnianie elementów w pozycjach (numer kolumny) modulo (długość danych wyjściowych) w celu zbudowania tablicy.

Łączy kilka kluczowych pomysłów:

• wzory i symetrie mogą być wstępnie obliczone
• pojedynczy wzór można upakować w liczbę całkowitą o znanych wymiarach
• znalezienie wszystkich podmacierzy jest łatwe
• liczenie równości jest łatwe

Oto kod:

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

Oto kod Mathematica użyty do spakowania tablicy 0,1 do formatu później rozpakowanego przez program 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]}

Oto o wiele pełniejsze odkrycie kodu:

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