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