Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Lightning submission:
lightning.zip
Full contest submission:
full.zip
Source code:
source.zip
The Frictionless Bananas had only one team member this year. This page describes my 2018 ICFP Programming Contest entry.
The task this year was to control a futuristic 3D printer that constructs objects using nanobots. For a series of 3D models, you must provide a set of commands to construct the object while minimizing the energy cost.
Energy costs on each time step are dominated by a term proportional to the size of the matrix, R^3 -- so much so that I ignored all other costs. That term is 10 times larger when harmonics are set to high, which is needed when the object is not "grounded" (connected to the floor of the machine). So, energy costs can be reduced in the following ways:
I chose to focus first on keeping objects grounded in order to use low harmonics. That requires determining a safe order in which to fill the voxels.
One constraint is that each filled voxel must be adjacent to either the floor or another already filled voxel. That is easy to check locally in constant time.
Another more subtle constraint is that you cannot completely surround a region with filled voxels (or the ground) when there are voxels inside the region that still need to be filled. Similarly, you cannot seal a bot inside a completely surrounded region. Those issues turn out to be related to "articulation points" in graph theory. An articulation point (or cut vertex) is a vertex in a graph that when removed would split the graph into unconnected pieces. In the graph made up of empty voxels, filling an articulation point voxel would disconnect a region of empty voxels from the rest. I used a standard linear time algorithm to find the articulation points. Filling an articulation point is fine as long as there is nothing important remaining in the disconnected region, so I modified the algorithm to track whether a disconnected region contains any unfilled voxels needing to be filled, or any bots.
I used a simple greedy strategy to control the actions of the bots. I perform a breadth first search starting from a bot's location to find the closest location where it can fill a voxel that is safe to fill. After filling that voxel, the process repeats. I only used a single bot during the lightning round, but the approach in theory seemed extensible to multiple bots executing the same strategy.
I got the above algorithm marginally working near the end of the lightning round, but I ran into issues with performance. My program was not able to solve the larger problems in a reasonable amount of time. In the end, I managed to submit solutions to 77 out of 186 problems.
For the full contest, nanobots gained the ability to empty as well as fill voxels. Two new problem types were added: disassembly (destroying an existing object) and reassembly (converting one object to another). Also, powerful new commands were added to fill or empty an entire 1D, 2D, or 3D region in one time step, using multiple cooperating bots at the corners of the region.
After implementing the spec changes, I modified my program to use multiple bots (fission/fusion). I used a hand-coded set of commands to create 40 bots at coordinates (0-19, 0, 0) and (0, 1, 0-19), and a corresponding set of commands to fuse bots at those coordinates back into a single bot. Each bot independently executed a greedy strategy of filling the nearest safe voxel while avoiding voxels in use by other bots.
I continued to have issues with running time on larger problems. I did not expect linear time algorithms like breadth first search and articulation point finding to be a problem, but when repeated many times on a large matrix the time adds up. Using multiple bots exacerbated the problem: With a single bot, I could perform a search once and then emit a sequence of commands to follow an entire path. With multiple bots, I would emit one command and then repeat the search so that each bot could react to changes made by the others.
The scoring system had the effect that any remotely reasonable solution for a problem would gain a large fraction of the available points, with far fewer points gained by producing an exceptionally good solution. Therefore, it was crucial to be able to produce decent solutions for all problems.
I decided to focus on finding algorithms that could solve even the largest problems, both assembly and disassembly, with solution quality as a secondary consideration. (I solved reassembly problems by concatenating separate disassembly and assembly solutions.)
For disassembly problems, I chose to divide the object into rectangular columns of size 31x31xN. Bots working in groups of four use GVoid commands to erase a column one layer at a time, working from top to bottom. I make no attempt to keep the object grounded (other than by working from top to bottom), but I at least detect solutions where the object remains grounded the whole time and use low harmonics in that case.
I implemented the above algorithm based on my earlier code. Specifically, I reused the logic of multiple bots searching for paths to desirable locations, but those locations were determined by the new column-based strategy.
Running time was still an issue. While I no longer needed to find articulation points, I still needed to perform breadth first searches. The search was fast in cases where the target location was close to the bot's current location, like when moving down a column one layer at a time, but it was slow in other cases, like when moving from one column to another or to/from the starting locations. After some profiling and optimization, I was able to solve all disassembly problems in a reasonable amount of time.
For assembly problems, I decided to build the object one level at a time, from bottom to top. As with disassembly, objects were not kept grounded except by chance.
This approach was implemented as a fairly minor variation on my earlier code by adding restrictions to the search. When constructing level L, the search would only terminate at voxels in level L, and bots were only permitted to travel through voxels where y = L + 1 or where x <= 1 or z <= 1 (to permit travel to and from the starting locations). This reduced the search space from R^3 to R^2, greatly improving the running time.
At this point I had solutions to all problems, so I submitted to the server to check my results. I found that I was scoring better on disassembly problems than assembly problems, so I looked for ways to improve assembly.
I decided to use GFill to fill rectangular regions within a level. In each level, I look for sufficiently large rectangular regions (those with area >= 15). Bots work in groups of four to fill those regions, then work individually to fill the remaining voxels.
Up until this point, I was using low or high harmonics for an entire solution. As my last improvement before the end of the contest, I implemented a simple optimizer to check which time steps actually require high harmonics and automatically switch as needed.
When I submitted solutions a few hours before the live standings were frozen, I was in third place. As other teams continued to submit solutions, I dropped to 7th. Then for some reason I increased to 6th and then 5th. I'm not sure why that happened. Perhaps the organizers were changing the set of problems used for live standings. My final submission should perform better, but of course the same is true of other teams.
This was a well-run contest and the task was a lot of fun and a good challenge. There was a time at the end of the second day when I was getting tired of the task, but that is because I was having difficulty coming up with an approach that would do well (and I needed sleep). I woke up the next day with new ideas and had a lot of fun finishing the contest. Thanks to the organizers for all your hard work!