This year ICFPC was about finding optimal solution to 3D printing problem.
- Contest was really well organized. Everything went smoothly and without hiccups.
- There was leaderboard! It’s a big deal and helped to strive for being competitive.
- The problem was quite visual and easy to understand.
- On the other hand, I think that the problem wasn’t really deep enough (compared to “Lambda the gathering” or “Cars and Fuel” years).
- Initially I thought the problem space is quite narrow, but after lightning round there was enough parallelization between team members to work on different tasks.
- The problem ended up being computationally expensive, so I am glad we used C++ and not python.
We finished on 3rd place in frozen results. Here is top16 of teams:
UPDATE. In final results we were only on 51st place as several of our solutions had a bug that wasn’t caught by our checker and we thought they are legit.
After fixing the bug and recalculating score we have
2664144 scores which would get us to 8th place. Oh, wow.
UPDATE. In lightning round we finished on 7th place.
Usually we skip lightning round and focus solving the main problem. But this time organizers initially published only lightning round task description, so we had to solve that. There still was a chance that main round would be completely different, but that sounded unlikely and in any case every other team would be in the same boat too.
On a high-level the problem this time was quite simple. You are given image for 3D printer and you need to write a program for bots to create it with minimal cost (spent energy). You were allowed to switch between high and low harmonics mode, which basically meant enabling/disabling levitation mode. This levitation was actually quite interesting, as unlike regular 3D printing it allowed you to create parts of the figure that would be flying in the air. The final result have to be grounded.
Here is the list of available commands:
- do nothing (
- move (
- switch low/high harmonics (
- create pixel (
- spawn new bot (
- merge 2 bots (
There was energy cost associated with each command.
The first key observation was that
in addition to command cost, every game tick you spend enormous amount of energy:
3 * R^3 or
30 * R^3 for high harmonics. This is order of magnitude larger than what commands cost themselves.
So really the main goal is to build the image in smallest number of steps.
This means that we should always build with as many robots as possible. Having extra bots on the field is super cheap, but they can reduce the total number of steps potentially by 20x.
Initially we were thinking about writing in python, but our other half of the team who were sitting in Irvine started leading the effort on C++, so we sticked to that.
What we did as a solution for lightning round:
- Always use levitation mode (except the few problems where all layers are always grounded on previous one)
- Build figure layer by layer
- Split the bots into 20 ones (or smaller if the size is small) and each works on its own split of XZ plane. This way it is guaranteed they won’t interfere with each other.
- Once the layer is done, all bots go up one layer and continue process
- On top of this have a solver that within certain timeout (
10 min) tries different splits (by both X and Z axis) and returns the best found result
- Small optimization to disable final
Flipafter we did last
Things that didn’t work out
- We implemented a visualizer in jupyter notebook, but it wasn’t really useful as we ended up using python. Here is screenshot how the things look
- We tried to do BFS-like filling in order to not use levitation for layer-grounded figures (which means each layer is grounded when built on top of previous layer, for example, this is not layer-grounded figure:
But this ends up being too complicated to implement with multiple bots working simultaneously.
Once the lightning round was finished they released the description for main round. The main differences were the following:
Voidcommand to erase the pixel
GVoidcommands to erase group of pixels in one step.
2^nbots should specify the corners of n-dimensional simplex.
- Maximum number of bots increased to 40.
- New set of problems:
Disassmble- from a given figure get the empty field
Reassemble- from a figure A get the figure B.
- On the high level we have multiple solvers that were running for each type of problem and choosing the best result
- We implemented autoharmonics - postprocessing step which turns on/off harmonics if it’s possible. Even if we would do it only for 2 steps it would still be beneficial.
- We have multiple layers of protection when saving results to make sure we never overwrite with worse solution
We call object grounded if it’s possible to construct it without high harmonics switched on. The property can be easily checked with BFS.
We run BFS to split whole object by the distance from the floor (one can via faces of the voxels).
Further action is a sheer prescripted work. We construct the object layer by layer.
- We fission bots into 20 or less if the size is small.
- These bots can decouple each other and cover one-dimension straps on the current level with
- Than all bots lift-up on one level and repeat construction.
- At the end, we merge them together, and than put a single bot to the origin.
- Split the bounding box of figure into long strip of width 29.
- And then use it as sliding window to swipe the whole Layer.
- Continue until reaching ground.
- We often used inversing of commands for code simplicity (e.g. after we spawned the bots on the gird, we can do inverse command in reversed order to despawn them back)
- This only works on problems less than
30x30x30dimensions of bounding box.
- It forks bots and puts into corners of the cube.
- Then does one
GVoidto wipe it
- Doesn’t even flip the harmonics
- Obviously, finely tuned versions to improve energy usage
- Fissions and fusions are manually aligned to axis to save energy
- Bounding box is
(0, 0, 0)-based when possible to save time on movement
- Empty slices are ignored
- The main solution we used here was to just use best of Assembly + Disassembly from all of the above solvers.
- We tried using greedy incremental reassembler (only change the xor of figures), but this idea didn’t pan out
Command line tools
- To run the solution on all problems:
cd src/cpp/ make && ./build/cpp_solver
- For specific problem one can use
./build/cpp_solver -test A042
- The parameter
testalso supports a regexp:
./build/cpp_solver -test "D\d\d\d"
- All the algorithms live in corresponding folders:
src/cpp/solver_assembly/ src/cpp/solver_disassembly/ src/cpp/solver_reassembly/
- The solver can use multiple threads for processing (
- Solutions organization:
- The solver output solutions to
- We join the current best solutions with candidates using
-mode mergemode and write into
- We also can use
-mode check -levitation 0for validation of current solutions.
- The solver output solutions to