# Essays/Polyminoes

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

## Contents

### Symmetries and neighborhoods

```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. 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. Download script: neighborhoods

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

```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". 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. 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: Download script: generate

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

```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. 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. 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
)
```
```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

```«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) 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