Essays/Polyminoes

We will represent polyminoes as boolean matrices with 0s denoting empty spots and 1s form connected block.

Symmetries and neighborhoods

[{{#file: "symmetries"}} Download script: symmetries ]

square=:(, |:&.>)@(, |.&.>)@(, |."1&.>)
square_ch=:(] , |.@|:&.> , |:@|.&.> , ($ $ |.@,)&.>)
allsym=:1 : '[: , (<"1 (i.@! A. i.)m) (|:)&.>/ (0&|:&.>@(, |."1&.>)^:m)'
cube=:[: , (<"1 (i.@! A. i.)3)(|:)&.>/ (, |."3&.>)@(, |."2&.>)@(, |."1&.>)
group=:square

group applies all possible transformation to a figure which leave figure essentially "the same". For example, group square consist of rotations by 0°, 90°, 180°, 270° and mirror symmetries along vertical axis, horizontal axis and both diagonals. [{{#file: "symmetries"}} Download script: symmetries ]

canonic=:{.@/:~@group

To be able to handle polyminoes that are same under transformations from symmetry group we will pick "smallest" (in the sense of /:) among all possible transformed figures as their representative. This ensures that 2 figures which are same under some transformation from group will have same canonic representative. [{{#file: "neighborhoods"}} Download script: neighborhoods ]

addmargin=:>:@$ |. ] {.~ 2+$

addmargin adds a row of 0-s to top, bottom, left, right, etc. edges of a figure [{{#file: "neighborhoods"}} Download script: neighborhoods ]

king=:< (+./@:|.~ 3&(#~ <:@#: i.@^)@#@$)
rook=:< (+./@:|.~ (, -)@(=/~)@i.   @#@$)
neib=:rook

neib marks those cells that are currently empty but touch at least one cell in y. What exactly constitutes 'touch' depends on convention. One of the popular conventions says "touch means have common face", also called "rook neighbourhood". Another says "touch means have at least one common point", also called "king neighborhood". [{{#file: "neighborhoods"}} Download script: neighborhoods ]

children=:($ $"1 (I.@,@neib) 1:`[`]}"0 _ ,)@addmargin

children gives list of possible shapes that can be obtained from a given shape by adjoining a single square. [{{#file: "neighborhoods"}} Download script: neighborhoods ]

dropmargin=:(#~ +./@,"_1)@(0&|:)^:(#@$)

Trim rows of zeroes adjacent to margins. Assumes connected figure. For disconnected figure (consisting of several islands with gaps between them) the following procedure drops only empty margin layers without dropping empty internal layers:

dropmargin=:(#~ [: (+./\ *. +./\.) +./@,"_1)@(0&|:)^:(#@$)

Generating polyminoes

Finally, combining it all together we get a verb that produces (n+1)-th degree polyminoes from n-th: [{{#file: "generate"}} Download script: generate ]

step=:([: ~.@; ([: ~. canonic@<@dropmargin"_1@children)&.>)

Now we can generate polyminoes of given order. [{{#file: "generate"}} Download script: generate ]

build_rp=:3 : 0
group=:square
neib=:rook
s=.i.0
s=.s,#RP1=:,<1 1$1
s=.s,#RP2=:step RP1
s=.s,#RP3=:step RP2
s=.s,#RP4=:step RP3
s=.s,#RP5=:step RP4
s=.s,#RP6=:step RP5
s=.s,#RP7=:step RP6
s=.s,#RP8=:step RP7
s=.s,#RP9=:step RP8
s=.s,#RP10=:step RP9
)

Running it gives the counts of distinct polyminoes of different orders:

1 1 2 5 12 35 108 369 1285 4655

We can also redefine neigbourhood to allow squares to touch with corners would give different set of figures. [{{#file: "generate"}} Download script: generate ]

build_kp=:3 : 0
group=:square
neib=:king
s=.i.0
s=.s,#KP1=:,<1 1$1
s=.s,#KP2=:step KP1
s=.s,#KP3=:step KP2
s=.s,#KP4=:step KP3
s=.s,#KP5=:step KP4
s=.s,#KP6=:step KP5
s=.s,#KP7=:step KP6
)

One of the amusing J's features is its ability to apply same verbs to data of different dimensions and obtain meaningful results. Both neib verbs, king and rook are just such dimension neutral verbs, as well as step, which generates polyfigures of next order. We assign different symmetry group and start with a cube rather then square as a starting point and get different polycubes. [{{#file: "generate"}} Download script: generate ]

build_rc=:3 : 0
group=:cube
neib=:rook
s=.i.0
s=.s,#RC1=:,<1 1 1$1
s=.s,#RC2=:step RC1
s=.s,#RC3=:step RC2
s=.s,#RC4=:step RC3
s=.s,#RC5=:step RC4
s=.s,#RC6=:step RC5
s=.s,#RC7=:step RC6
s=.s,#RC8=:step RC7
)

[{{#file: "generate"}} Download script: generate ]

build_kc=:3 : 0
group=:cube
neib=:king
s=.i.0
s=.s,#KC1=:,<1 1 1$1
s=.s,#KC2=:step KC1
s=.s,#KC3=:step KC2
s=.s,#KC4=:step KC3
s=.s,#KC5=:step KC4
)

Collected definitions

These definitions can be downloaded as single file from [{{#file: "polyminoes.ijs"}} Download script: polyminoes.ijs ]

«symmetries»
«neighborhoods»
«generate»
«visualize»

Visualize results

We will define pview verb to visualize generated polymino set. It will only work for flat (2d) figures. (Visualising polycubes is left as excersize to the reader) [{{#file: "visualize"}} Download script: visualize ]

db=:(2$,:2 1) ((u: 32 9600 9604 9608) {~ #.@|.@,);.3 ]
pview=:db@:;@:(((>.&# {. [) ,. (>.&# {. ]))&.>/"1)@(-@[ addmargin&.>\ ])

For example

   build_rp ''
1 1 2 5 12 35 108 369 1285 4655
   10 pview RP6

   build_kp ''
1 2 5 22 94 524 3031
   10 pview KP4

Use

   FILE=:<'rpws.ijs'
   '' 1!:2 FILE
   (FILE 1!:3~ CRLF ,~ ] , '=:' , [: 5!:5 <)@('RP' , ":)"0 >:i.10

to save generated figures in a file

Contributed by Andrew Nikitin

---