## n x k rectangular pattern lister

For scripts to aid with computation or simulation in cellular automata.
Posts: 571
Joined: May 7th, 2016, 8:53 am
Contact:

### n x k rectangular pattern lister

Howdy!

Created a fast and dirty python script that lists all distinct patterns in an n x k bounding box, which is minimal rectangular container for the listed patterns. Slow and unoptimized, reviews, opinions are welcome!
• Independent from golly
• Self-explanatory the usage
• Run without arguments to see brief intructions!
The patterns are listed to the standard output, so saving it to a file is easy like this:

Code: Select all

``C:\TEMP\WINDOWS>python rectanglefiller.py 3 2 > savedrle.txt``
The code itself:

Code: Select all

``````#!/usr/bin/env python

# Some right reversed
# Do NOT violate the laws of the authot's country!
# No commercial use!

import re
import sys

def torle(a):
b = str(a)[:-1].replace('1','o').replace('0','b').replace(']','\$')+'!'
b = re.sub(r'[^bo\$!]','',b)
b = re.sub(r'b+\\$','\$',b)
b = re.sub(r'\\$+!','!',b)
e = d = ''
f = 0
for c in b:
if d == c:
f = f + 1
else:
e = e + (str(f) if f > 1 else '')
e = e + d
d = c
f = 1
if c == '!':
e = e + '!'
return e

def main(argv):
maxx, maxy = 0, 0
try:
maxx, maxy = map(lambda x: int(x), argv[:2])
assert len(argv) == 2
assert maxx >= maxy
assert maxy > 0
except:
print '''
ERROR!

Usage:

rectanglefiller <X> <Y>
- X and Y are positive integers
- X >= Y

Output: rle list of all X*Y cell patterns
'''
sys.exit(1)
upperlimit = 1<<(maxx*maxy)
maxxhalf = maxx//2
maxyhalf = maxy//2
for space in range(upperlimit):
basematrix = map(lambda x:int(x), list(str(bin(upperlimit+space))[3:]))
idemp = [basematrix[j*maxx:j*maxx+maxx] for j in range(maxy)]
flipp = [basematrix[j*maxx-maxx:j*maxx] for j in range(maxy,0,-1)]
idemptr = [basematrix[i::maxx] for i in range(maxx)]
flipptr = [basematrix[i-1::maxx] for i in range(maxx,0,-1)]
diag1 = [idemp[i][i:] for i in range(maxx)] if maxx == maxy else 2
diag2 = [idemptr[i][i:] for i in range(maxx)] if maxx == maxy else 2
if \
1 in idemp[0] \
and 1 in flipp[0] \
and 1 in idemptr[0] \
and 1 in flipptr[0] \
and ((idemp[:maxyhalf] >= flipp[:maxyhalf]) and (idemptr[:maxxhalf] >= flipptr[:maxxhalf])) \
and (diag1 >= diag2) \
:
print torle(idemp)

if __name__ == "__main__":
main(sys.argv[1:])``````
Goals? No goals, this is rather messY

Well, there is at least one - classifying small patterns here ../forums/viewtopic.php?f=11&t=2233#p38503

Posts: 571
Joined: May 7th, 2016, 8:53 am
Contact:

### Re: n x k rectangular pattern lister

Generated all distinct patterns that fit in 4x4 bounding box. rle textfile is in the attached bzip2 archive. Extract it before loading it with golly!

Created in *nix command line with this oneliner (and the script I published in this OP):

Code: Select all

``echo 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 | xargs -n2 ./rectanglefiller.py | sed '\$q;s/!/100\$/' > 1x1to4x4.rle``
I found the \$topic utility handy when inspected small patterns' properties. Please let me inform if you found these useful and/or improvement ideas/forks are kindly welcome!
Attachments
1x1to4x4.rle.bz2
all patterns in rle format in bounding box 4x4

Posts: 571
Joined: May 7th, 2016, 8:53 am
Contact:

### Re: n x k rectangular pattern lister

Naszvadi wrote:Generated all distinct patterns that fit in 4x4 bounding box. rle textfile is in the attached bzip2 archive. Extract it before loading it with golly!

Created in *nix command line with this oneliner (and the script I published in this OP):

Code: Select all

``echo 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 | xargs -n2 ./rectanglefiller.py | sed '\$q;s/!/100\$/' > 1x1to4x4.rle``
I found the \$topic utility handy when inspected small patterns' properties. Please let me inform if you found these useful and/or improvement ideas/forks are kindly welcome!
Oops! Still has many redundancies. For example in lines 9 and 13:

user@errorlevel:0:/tmp\$ bzcat 1x1to4x4.rle.bz2 | grep -n '^o.b2o100\|^2o.2bo100'
9:o\$b2o100\$
13:2o\$2bo100\$
user@errorlevel:0:/tmp\$

Or for such nerds who likes bashing:
user@errorlevel:0:/tmp\$ bzcat 1x1to4x4.rle.bz2 | grep -m2 '^o.b2o100\|^2o.2bo100' | sed '1s/o/[c&de]o/;2s/100./![\/code/;2s/e\$/e]/'

Code: Select all

``````o\$b2o100\$
2o\$2bo!``````
user@errorlevel:0:/tmp\$

Will be fixed. Missed deduplication upon 180 degrees rotational transitions.

Posts: 571
Joined: May 7th, 2016, 8:53 am
Contact:

### Re: n x k rectangular pattern lister

Updated and refactored the code:

Code: Select all

``````#!/usr/bin/env python

# Some rights reserved
# Do NOT violate the laws of the author's country!
# No commercial use!

import sys

# returns the minima of the nonidentical transformeds of a pattern
def binflip(number, maxx, maxy):
if maxx != maxy:
retval = [0, 0, 0]
for i in range(maxx):
for j in range(maxy):
retval[0]+=1<<(i*maxy+maxy-j-1)
retval[1]+=1<<((maxx-i-1)*maxy+j)
retval[2]+=1<<((maxx-i-1)*maxy+maxx-j-1)
else:
retval = [0, 0, 0, 0, 0, 0, 0]
for i in range(maxx):
for j in range(maxy):
retval[0]+=1<<(i*maxy+maxy-j-1)
retval[1]+=1<<((maxx-i-1)*maxy+j)
retval[2]+=1<<((maxx-i-1)*maxy+maxx-j-1)
retval[3]+=1<<(j*maxy+maxy-i-1)
retval[4]+=1<<((maxx-j-1)*maxy+i)
retval[5]+=1<<(j*maxy+i)
retval[6]+=1<<((maxx-j-1)*maxy+(maxx-i-1))
return min(retval)

def rectangle(maxx, maxy):
upperlimit = 1<<(maxx*maxy)
rowmasks = [(1<<maxx)-1, ((1<<maxx)-1)<<((maxy-1)*maxx), (upperlimit-1)/((1<<maxx)-1), ((upperlimit-1)/((1<<maxx)-1))<<(maxx-1)]
for space in range(upperlimit):
if space & rowmasks[0] and \
space <= binflip(space, maxx, maxy):
print torle(space, maxx)

def torle(a, maxx):
retval = ''
i = 1
retval += 'o'
else:
retval += 'b'
if (i % maxx) == 0:
retval += '\$'
i += 1

while 'b\$' in retval:
retval = retval.replace('b\$', '\$')
retval = retval.strip('\$')
while (not '\$o' in retval) and retval[:1] == 'b':
retval = retval.replace('\$b', '\$')
retval = retval[1:]
while not retval[-1:] in 'o':
retval = retval.rstrip('\$')
retval = retval.rstrip('b')

replacelist = []
for onech in ['b', 'o', '\$']:
findmax = onech * 2
while findmax in retval:
replacelist.insert(0, findmax)
findmax += onech
for i in replacelist:
replacethis = str(len(i)) + i[0]
retval = retval.replace(i, replacethis)

retval += '!'
return retval

def main(argv):
maxx, maxy = 0, 0
try:
maxx, maxy = map(lambda x: int(x), argv[:2])
assert len(argv) == 2
assert maxx >= maxy
assert maxy > 0
except:
print '''
ERROR!

Usage:

rectanglefiller <X> <Y>
- X and Y are positive integers
- X >= Y

Output: rle list of all X*Y cell patterns
'''.replace('            ', '')
sys.exit(1)
return rectangle(maxx, maxy)

if __name__ == "__main__":
main(sys.argv[1:])
``````
Attachments
1x1to4x4.rles.bz2
all patterns in that fit in 4x4 bounding box in rle-format-per-line

Posts: 571
Joined: May 7th, 2016, 8:53 am
Contact:

### Re: n x k rectangular pattern lister

Naszvadi wrote:Updated and refactored the code:

Code: Select all

``crap``
Oops, buggy!

obo\$3o! IOR 3o\$obo! is missing from 3x2 parts. Reason known, fixing is ongoing, stay tooned! (or fix it for [y]ourselves!)

This is even worse, because instead of producing redundant lists, the last code misses some patterns.