Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Submission:
submission.tar.gz
The Frictionless Bananas had only one team member this year. This page describes my 2016 ICFP Programming Contest entry.
This year's task involved origami. Specifically, given a description of a 2D shape you must determine how to fold a square piece of paper into that shape.
Shape descriptions are provided in two forms: a "silhouette" representation consisting of a polygonal outline and zero or more polygonal holes, and a more detailed "skeleton" representation that includes line segments on the interior of the silhouette representing the folds and edges that result from one possible way to fold the shape. Solutions are only required to match the silhouette.
As an additional twist, participants were able to submit problems for other teams to solve, receiving more points for problems that were solved by fewer teams. Most of the problems in the contest were provided by participants themselves.
As usual for the ICFP contest, the lightning round presents a dilemma regarding how to spend the first 24 hours. It is often the case that the work to produce the best possible results in 24 hours is not incrementally useful for producing the best possible results in 72 hours. This year the situation was even worse, because to begin publishing problems for other teams at the 24 hour mark you need to spend some of the first 24 hours on an activity that doesn't affect lightning round scoring.
As usual, I decided to mostly ignore the lightning round and focus on doing as well as possible in the full contest. That means the top priority was to generate problems for other teams to solve. I did work a bit on my solver, mainly because I thought it might give me insight into what problems would be hard to solve, but towards the end I switched to problem generation full time. The only problem I solved in the first 24 hours was done by hand, just to test my server communication code.
I generated problems for other teams by starting with a square piece of paper, rotating and translating it slightly, and then folding several times at randomly chosen locations. The locations were chosen so that an existing vertex was folded onto either another vertex or an edge, which seemed to produce more confusing looking results. I limited the number of folds to keep the solution sizes around 500-1500 bytes.
I examined each result and rejected ones that I didn't like for whatever reason. The main objective reason for rejection was if the shape was convex, since there is a simple strategy for folding arbitrary convex polygons. Other than that, I just picked things that looked complicated. Unfortunately I didn't have a visualizer for solutions, only for problems, so I took the poor man's approach of submitting a solution to the server, downloading the corresponding problem, and viewing that in my existing visualizer. (Sorry, organizers!) As a one-person team you learn not to spend time writing unnecessary code.
Remarkably, just by publishing problems without solving any (other than the first problem as a test), I was able to maintain a rank of around #20 for most of the contest. I knew the task was challenging, but it was still surprising to see. In hindsight I think the most important aspect of the problems that I created was that they were not convex, so fewer people were able to solve them exactly. Keeping the byte sizes down probably also helped.
Early in the contest I came up with a few simple but non-general strategies:
It was clear that the best results would be achieved by a solver that can find exact solutions to arbitrary problems. I had an idea of how to achieve that, though it would not be easy, and it was not at all certain that I would finish in time. I decided to try anyway, hoping for a chance of being one of the top teams.
My main solver takes advantage of the skeleton, which divides the given shape into regions. My solver tries to fill a square piece of paper with transformed copies of those regions (translated, rotated, and mirrored) in a way that respects the rules of origami. Specifically, once a region has been placed, there are only two possibilities for what region can be placed along each of its edges: a reflected copy of the same region (representing a fold), or an unreflected copy of the adjacent region from the original skeleton (representing a flat piece of paper). Once the square is filled and all regions have been used at least once, a valid solution has been found. This approach transforms the task into a search problem with a finite number of choices at each step, something I am more prepared to deal with than a geometrical problem—even though the exponential search space may become problematic.
The first step is to process the skeleton into a more useful form. This involves splitting the segments at their intersection points, grouping common endpoints into vertices, sorting the segments around each vertex by angle, and tracing paths from edge to vertex to next edge to find regions. Information from the silhouette must also be used to determine which regions represent holes.
The next step is to place the first region. Since there is no existing region to place it next to, this is the only step in the search when all regions must be considered. My solver tries to place each edge of each region along the X axis, with a vertex at the origin. One subtlety is that not all edges can be rotated into that configuration due to the use of rational numbers. For example, an edge from (0, 0) to (1, 1) has an irrational length, and thus cannot be rotated onto the X axis using rational coordinates.
After that, the solver performs a fairly typical depth first search. It chooses an edge of an existing region to place a new region next to, tries to place each of the two possible new regions next to that edge, and recursively places more regions.
Initially my solver chose the edge to place a new region next to arbitrarily. Later I tried considering all possible edges in order to find the edge with the smallest number of regions that can be placed next to it. Sometimes there is an edge where nothing can be placed, in which case the search can immediately backtrack. Otherwise, it is better to choose an edge where only one region can successfully be placed rather than two, to help reduce the branching factor of the search. It is not entirely clear whether that helped, since trying all edges is expensive, but I feel like my program was able to solve a few more problems after the change than before.
At about 12 hours before the end of the contest, I finally had a program that was capable of generating solutions to at least some problems. As it churned through the full set of problems over several hours, I watched my rank on the hourly leaderboard increase from 17 to 14 to 7 to 4 to 3. That is where I was when the leaderboard was frozen, and it is where I suspect I remained at the end of the contest, though I can always hope for second. First place seems well out of reach.
Towards the end of the contest, I was looking at some of the problems that my program had solved and noticed that often only 2-4 other teams had solved them exactly, which meant I was doing pretty well, though probably behind a few teams. Then I looked at a problem that my program was having trouble with, and was surprised to find that 30 teams had solved it exactly. I was puzzled until I realized that the shape was convex. Many teams must have written solvers specifically for convex polygons.
With 1.5 hours remaining, I didn't think I had enough time to write another solver, but then I realized that I had almost all of the pieces already written. My program that generates problems for other teams was already capable of starting with a square, translating and rotating it, folding it at various locations, and generating a properly formatted solution. All I had to do to produce a working solver for convex polygons was change the initial translation to move the square to fit around the polygon and change the folding locations to be the polygon's edges. Within an hour, I had the code working and used it to solve 74 additional problems. That left me with only 8 unsolved convex problems, because they did not fit inside an unrotated square and I didn't think I had time to add support for rotation.
With 30 minutes remaining, I again didn't think I had enough time to write another solver, but then I realized that it wouldn't be hard to make a solver that finds approximate solutions by folding a rectangle equal to the bounding box of the given shape. Starting with my convex solver, all I had to do was change the folding locations to be the edges of the bounding box. Since the solution is approximate, it doesn't even matter if the shape fits in the initial square. It's not the best approximate solver, but it's something I could finish in a few minutes with the tools at hand. Still, I had about 800 unsolved problems to get through and about 16 minutes to do it. I reduced the server communication delays to try to get as close as possible to one submission per second given the server's own delays in responding. In the end, there were 61 problems remaining when the contest ended and the server started rejecting my submissions. Another minute and a half would have been enough.
My program was written in C++ using GCC on Linux. I used the following libraries:
I also used a few homegrown tools that I have developed in recent years specifically with the contest in mind. They support both Linux and Windows, wrapping the necessary APIs of both platforms, though in practice I was only able to build on Linux during the contest due to all the other libraries I was using. This is the first year when I had occasion to use my graphics library.
When I first read the task description, my initial thought was that it's not my kind of problem as much as many other recent years have been, but that's okay. One of the interesting things about the ICFP contest is that you never quite know what to expect, and a variety of problem types have been represented over the years.
I can only describe programming and debugging the geometric algorithms as tedious. I had quite a few bugs in my main solver that I struggled with for hours, and I'm convinced that some remained even after I got things somewhat working. I also groaned when I saw the need for arbitrary precision numbers, though that may have been a blessing is disguise: at least there were no issues with rounding errors and tolerances as would exist with floating point numbers.
The contest was extremely well organized and executed. Thank you to the organizers for that! Even if the task was not quite what I expected, it was a lot of fun to work on and a good challenge. In the end I am quite happy with how the contest turned out.