A 3D polycube generator based on the Computerphile video and this repository. This version is written in C with some optimizations indicated below.
make all
Note the current Makefile was written for Linux with GCC. The only external dependencies are pthreads and zlib. It seems to work in Cygwin or MinGW, though the executable is a bit slower.
The following returns the number of 3D polycubes of length 5:
./polycube_generator 5
The following returns the number of 3D polycubes of each length up to 8:
./polycube_generator 8 -a
For lengths larger than 9, the "-t" option allows specification of a number of compute threads. The default is 16 threads, shown here with 10 threads.
./polycube_generator 13 -n 10
A cache file can be generated by adding "-o" with the filename:
./polycube_generator 5 -o cubes5.pcube
A PCube cache file can be compressed by adding "-oz" with the filename:
./polycube_generator 5 -oz cubes5.pcube
A cache file can be input for use in computation by adding "-i" with the filename:
./polycube_generator 7 -i cubes5.pcube
Cache files can be generated in a smaller "bitface" format by changing the extension to something besides .pcube:
./polycube_generator 5 -o cubes5.dat
The job_processor.py
file is used as a client to a SnowmanPolycubeServer instance. By default, it continuously processes segments of a shared seed file and returns the number of polycubes found.
The only non-standard library used is requests.
Before starting, set the configuration in job_processor.cfg
. You need to set up the server name, how many hardware threads are available, the name of the command - such as polycube_generator.exe on Windows, and the name which you want to be called in your contribution:
[Job]
job_server = https://snowman-polycube-server.vercel.app/jobs/n18/job-tickets
job_folder = jobs
[General]
threads = 12
cmd = ./polycube_generator
contributor_name = snowmanam2
Note the job_server
must point to the proper job-tickets
node of an active job on the server, as configured by the server operator.
Once the configuration is saved (assuming the main executable was built as noted in the "Compiling" section), you can start the processor with:
python job_processor.py
The processor will run continuously until the server runs out of segments to compute. You can kill the process if needed, though all progress on the current ticket will be lost. The server will reallocate the dropped segment after the configured timeout has been reached.
Basics:
This is "hashtable-less" implementation similar to that described by presseyt. The difference is checking if the removed point from the new polycube is the highest possible index in the polycube point list. When doing this in combination with removing all duplicate polycubes from the current "seed" shape, we are left with a unique set of generated cubes. Specific steps taken:
The advantage of this method is we don't need to recanonize the combinations. I used a rather lazy implementation of steps 3 and 4:
Using a rather dated FX-8350 processor with 16 computing threads on Ubuntu with no cache generation or input, measured cumulatively:
This program can read or write the basic .pcube format. Compression is supported.
The alternative "bitface" cache file format is structured as follows:
The encoding is a bit / face scheme. The cubes are described in discovery order based on the +xyz / -xyz faces. We skip the face of each cube on which it was discovered, and we skip the last cube because it will always be zeroes. Each bit represents a discovered cube on the face of the current cube.
Note there will be exactly n-1 bits for a polycube of length n. This unambiguously describes the position of all cubes, making recovering the shape rather simple. It also could lead to further space reduction by noticing this data can only have a certain number of states, though I have yet to figure out a good way to do so.
For reference, the space utilization is 70.7 GB for n=15 with 9 bytes per polycube. Still, I estimate n=18 has 42.1 TB required, but I doubt anybody would want to generate that much data.
Example n=4 (note "." designates the skipped bit):
100000 100.00 100.00
a b c d
(this describes a straight line)
abcd
Example n=4:
100000 110.00 000.00
a b c d
(this is a T shape)
d
abc