Enumerating Polycubes
Author
Noelle Crawford
Title
Enumerating Polycubes
Description
Enumerating Polycubes
Category
Essays, Posts & Presentations
Keywords
URL
http://www.notebookarchive.org/2019-08-0gjg5e0/
DOI
https://notebookarchive.org/2019-08-0gjg5e0
Date Added
2019-08-01
Date Last Modified
2019-08-01
File Size
9.14 megabytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
WOLFRAM SUMMER SCHOOL 2019
Enumerating Polycubes
Enumerating Polycubes
Noelle Crawford
Jeremy Stratton-Smith
What are Polycubes?
What are Polycubes?
Polyomino tiles are 2-D tiles formed from a set of n square tiles. In this project I worked with polycubes, their 3 -D cousins, which are composed of cubes as opposed to squares. My goal was to write a function to calculate the number of distinct polycube forms possible given a set of n cubes, and present a visual representation of the set obtained. To achieve my goal, I will focused on the optimization of any algorithms used in order to handle the maximum possible value n in a reasonable timeframe.
Tensor Forms
Tensor Forms
3rd order tensors are used to represent polycubes contained within finite spaces. Here, a 0 represents an empty space, and a 1 represents a cube. This format is useful because it allows us to ask “Is there a cube here?” simply by accessing a point on the tensor, instead of manually filtering through a list of all points in a polycube.
Representations
Representations
(*Generatethetensorrepresentationgivenasetofpoints*)ClearAll[generateTensor];generateTensor[pts_]:=generateTensor[pts]=(Block[{n,t},n=Length@pts;t=ConstantArray[0,{n,n,n},SparseArray];(t〚#〚1〛〛〚#〚2〛〛〚#〚3〛〛=1)&/@pts;t])generateTensor[pts_,n_]:=generateTensor[pts,n]=(Block[{t},t=ConstantArray[0,{n,n,n},SparseArray];(t〚#〚1〛〛〚#〚2〛〛〚#〚3〛〛=1)&/@pts;t])
In[]:=
generateTensor[sample1]//MatrixForm
Out[]//MatrixForm=
|
|
|
| ||||||||||||||||
|
|
|
| ||||||||||||||||
|
|
|
| ||||||||||||||||
|
|
|
|
Operations
Operations
The most important uses of tensors for this program are their use in finding connected points (when checking validity) and their use in finding open points (when building). These functions test for either open or closed points surrounding another given point, p.
In[]:=
(*Returnalistofallfilledpointsconntectedtoagivenpoint,p*)ClearAll[getConnections];getConnections[p_,t_]:=(Block[{n,xy,yz,xz},n=Dimensions[t]〚1〛;xy=Table[{p[[1]],p[[2]],z},{z,{Max[p〚3〛-1,1],Min[p〚3〛+1,n]}}];yz=Table[{x,p[[2]],p[[3]]},{x,{Max[p〚1〛-1,1],Min[p〚1〛+1,n]}}];xz=Table[{p[[1]],y,p[[3]]},{y,{Max[p〚2〛-1,1],Min[p〚2〛+1,n]}}];Select[Join[xy,yz,xz],(t〚#〚1〛〛〚#〚2〛〛〚#〚3〛〛==1&&#≠p)&]])(*Returnalistofallopenpointsconnectedtop*)ClearAll[openConnections];openConnections[p_,t_]:=(Block[{n,xy,yz,xz,pts},(n=Dimensions[t]〚1〛;xy=Table[{p[[1]],p[[2]],z},{z,{Max[p〚3〛-1,1],Min[p〚3〛+1,n]}}];yz=Table[{x,p[[2]],p[[3]]},{x,{Max[p〚1〛-1,1],Min[p〚1〛+1,n]}}];xz=Table[{p[[1]],y,p[[3]]},{y,{Max[p〚2〛-1,1],Min[p〚2〛+1,n]}}];Select[Join[xy,yz,xz],(t〚#〚1〛〛〚#〚2〛〛〚#〚3〛〛==0)&])])
Rendered Forms
Rendered Forms
Generating Structures
Generating Structures
My first initiative was to generate structures I would be able to use as test data in the development of my helper functions. I find it helps when approaching a problem to do something, however small it may be, as it makes you more attached to solving it.
Random Cubes
Random Cubes
This function generates a random set of n points on a n x n x n tensor, which was useful for debugging the renderPolycube and generateTensor functions. These structures also provided ‘false’ examples when developing my valid function.
In[]:=
(*Generatearandomsetofncubes*)ClearAll[randomCubes];randomCubes[n_]:=(Block[{p,pts},pts={};While[Length@pts<n,p={RandomInteger[{1,n}],RandomInteger[{1,n}],RandomInteger[{1,n}]};If[!(p//MemberQ[pts]),pts=pts//Append[p]];];pts])
In[]:=
randomCubes[4]//renderPolycube
Out[]=
Random Polycubes
Random Polycubes
This function starts with a random point on an n x n x n tensor, and then repeatedly adds a cube to a random connected point until n cubes are contained. This function provided test data for my renderPolycube and generateTensor functions as well as ‘true’ examples for my valid function.
In[]:=
(*Generatearandomncubepolycube*)ClearAll[randomPolycube];randomPolycube[n_]:=(Block[{p,pts,t,ops},(p={RandomInteger[{1,n}],RandomInteger[{1,n}],RandomInteger[{1,n}]};pts={p};t=generateTensor[pts,n];While[Length@pts<n,(ops={};While[Length@ops0,p=RandomChoice[pts];ops=openConnections[p,t];];p=RandomChoice@ops;t〚p〚1〛〛〚p〚2〛〛〚p〚3〛〛=1;pts=pts//Append[p];)];pts)])
In[]:=
randomPolycube[5]//renderPolycube
Out[]=
In[]:=
randomPolycube[10]//renderPolycube
Out[]=
Generating Sets
Generating Sets
Acknowledgements
Acknowledgements
Cite this as: Noelle Crawford, "Enumerating Polycubes" from the Notebook Archive (2019), https://notebookarchive.org/2019-08-0gjg5e0
Download
