https://en.wikipedia.org/wiki/Polycube
Today, I've been playing with polycubes (which are polyhedrons formed
from adjacent cubes).
This requires both a representation -- a rank 3 bit array works
nicely, and a mechanism for working with cubic symmetry. For that, I
went with:
rotx=: |."2@(2 1&|:) NB. rotate in the yz plane about the x axis
roty=: |.@(1 0 2&|:) NB. rotate in the xz plane about the y axis
rotz=: |.@(2 1 0&|:) NB. rotate in the xy plane about the z axis
rotall=: {{
'X Y Z'=. y
rotx^:X roty^:Y rotz^:Z x
}}"3 1&(4 4 4#:(i.20),24+i.4)
Here, rotall gives all 24 rotations of cubic symmetry for a given
collection of 3d cubes represented by a bit array.
I decided to use a brute force mechanism to generate polycubes. In
other words, pad the array representation and add a single cube in
each of the locations adjacent to an existing cube:
extend=: {{
Y=. (-2+$y){.(1+$y){.y
new=. ($#:I.@,)Y < (_1&|. +. 1&|. +. 1&|."2 +. _1&|."2 +. 1&|."1 +.
_1&|."1) Y
~.new {{canon 1 (,:x)} y}}"1 3 Y
}}
Here, Y is the y argument with an extra 0 of padding in all
directions. And 'new' is the list of indices of empty locations
adjacent to cube locations.
I also need a verb (canon) to reduce these generated polycubes to
canonical form. A lot of this is removing unnecessary rows, columns
and planes of zeros. The rest of it is picking arbitrarily (but
consistently) from the 24 possible symmetric rotations:
offset=: {{ 1 i.~ +./+./"2 x |: *y }}
trim=: {{ (0 offset y)}."3 (1 offset y)}."2 (2 offset y)}."1 y }}
rtrim=: trim&.|.&.:(|."2)&.:(|."1)
canon=: {{ rtrim {. (/: +/@p:@I.@,"3) rotall trim y }}^:2
Finally, I want to work with all polycubes of a specific order, and to
get larger batch I can use;
extendall=: {{ ~.;<@extend"3 y }}
And, testing, this works:
#@> extendall&.>^:(i.8)<1 1 1 1$1
1 1 2 8 29 166 1023 6922
But, this is slow -- since I'm brute forcing all possibilities then
discarding duplicates, I need almost seven seconds on the little
laptop I'm currently using, to generate the above sequence.
(Also, for visualization of individual polycubes,
https://code.jsoftware.com/wiki/Scripts/Plot_3D works passibly well.)
Does anyone here have the geometric insight to improve on this approach?
Thanks,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
