n x k rectangular pattern lister

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

n x k rectangular pattern lister

Post by Naszvadi » February 22nd, 2017, 2:42 pm

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

# NASZVADI P, 2017-02-*
# 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 :D

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

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

Re: n x k rectangular pattern lister

Post by Naszvadi » June 27th, 2017, 1:37 pm

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
(21.37 KiB) Downloaded 310 times

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

Re: n x k rectangular pattern lister

Post by Naszvadi » July 10th, 2017, 9:16 am

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.

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

Re: n x k rectangular pattern lister

Post by Naszvadi » July 14th, 2017, 9:44 am

Updated and refactored the code:

Code: Select all

#!/usr/bin/env python

# NASZVADI P, 2017-07-*
# 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):
    mask = 1
    if maxx != maxy:
        retval = [0, 0, 0]
        for i in range(maxx):
            for j in range(maxy):
                if number & mask:
                    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)
                mask <<= 1
    else:
        retval = [0, 0, 0, 0, 0, 0, 0]
        for i in range(maxx):
            for j in range(maxy):
                if number & mask:
                    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))
                mask <<= 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 & rowmasks[1] and \
            space & rowmasks[2] and \
            space & rowmasks[3] and \
            space <= binflip(space, maxx, maxy):
            print torle(space, maxx)

def torle(a, maxx):
    retval = ''
    mask = 1
    i = 1
    while a >= mask:
        if a & mask:
            retval += 'o'
        else:
            retval += 'b'
        if (i % maxx) == 0:
            retval += '$'
        mask <<= 1
        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
(16.7 KiB) Downloaded 316 times

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

Re: n x k rectangular pattern lister

Post by Naszvadi » August 5th, 2017, 6:48 pm

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.

Post Reply