Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Solutions:
solutions.tar.gz
Source code:
source.tar.gz
The Frictionless Bananas had only one team member this year. This page describes my 2021 ICFP Programming Contest entry.
This year’s task was based on a game show where contestants must contort their bodies to fit through a hole in a styrofoam wall that is moving towards them.
In the contest, each problem consists of a polygon representing a hole, and a graph of edges and vertices representing a figure that must be made to fit in the hole. Corners of the hole and vertices of the figure have 2D integer coordinates. A solution consists of new locations for the vertices of the figure, subject to the constraint that edge lengths must be preserved within an epsilon tolerance. More points are awarded for solutions with vertices closer to the corners of the hole.
I started with some necessary tools and infrastructure:
The main difficulty was checking solution validity: it requires testing whether an edge lies within a polygon. That was tedious, but I got it working.
My first strategy was to exhaustively search for all valid solutions to a problem. At each step in the search, I choose a vertex to work on, find all legal locations for the vertex (respecting edge length constraints and edge containment within the hole), and try each location one by one.
One optimization was to choose a vertex to work on that minimizes the branching factor. At each step of the search, I find the set of legal locations for all vertices, and then work on the vertex with the fewest possibilities. In some cases there may be no legal locations and the search can backtrack immediately, or there may be only one in which case the choice is forced. Otherwise, some branching is necessary, but at least the branching factor is minimized.
To efficiently generate the set of legal locations for a vertex, I precompute certain data. For each edge length present in the problem, I compute the set of (x, y) offsets that satisfy the length constraints. I also generate a grid that stores whether each point within a bounding box lies within the hole. Then to generate the legal locations for a vertex, I choose one of the edges connecting it to an already placed vertex, use the precomputed offsets to find all locations satisfying the length constraints, and look each one up in the grid to check whether it is inside the hole. If so, I check whether the length constraints are satisfied for all other edges. Finally, I perform the relatively slower check that all the edges are inside the hole.
With this approach I was able to find optimal solutions for about 34 problems, earning about 200,000 points. Here are the problems solved and rough running times:
To solve larger problems, I needed a heuristic solver that could find decent but not necessarily optimal solutions. A simple approach to optimization problems is hill climbing: repeatedly make random changes to a solution, keeping those that improve the score. The difficulty in this contest is that there is a large interdependence between different parts of a solution, so that making a small change is likely to result in an invalid solution. One approach I have used successfully in the past (notably in the 2012 and 2019 contests) is to combine hill climbing with search. Instead of making random changes to a solution directly, I make changes to a more abstract solution “plan” which is then converted into a concrete solution via search.
After some aborted attempts, I settled on a solution plan consisting of a target location for each vertex. The plan is converted to a solution by a simple modification to the exhaustive search code: after generating the list of legal locations for a vertex, I sort the list by distance from that vertex’s target so that locations closest to the target are tried first. The first valid solution found by the search is kept. Later, I extended solution plans so that a vertex can be “greedy” instead of having a specific target location. For greedy vertices, the search prefers locations that produce the largest immediate score improvement.
The quality of solutions produced by the heuristic solver varies, but on average it achieved over 80% of the maximum score on problems that don’t seem to have exact solutions (i.e. solutions with a vertex at every corner). Combined with the exhaustive solver achieving 100% of the maximum score on some problems, I figured I was not doing too badly, considering that the top team only had about 90% of the maximum score across all problems.
I used the heuristic solver for about 63 problems—all those numbered 1-10 and 50-132 that did not have exact solutions. I also coaxed out an exact solution for problem 70 by initializing the target locations to the initial vertex locations shifted right by 10 units. After using both the exhaustive and heuristic solvers, I had about 900,000 points.
At this point in the contest, the biggest issue I faced was that I had no viable way to solve large problems with exact solutions. I could use the heuristic solver to produce valid solutions, but it was nearly pointless. The scoring formula was such that if an exact solution was found by any team, an even slightly worse solution would earn very few points.
With 8 hours remaining, I needed a new strategy. I briefly considered writing a UI to solve problems manually, but I wasn’t convinced it was feasible to solve the larger problems that way, nor did I think I had enough time to solve a lot of problems one by one.
Instead, I returned to the idea of exhaustive search, this time restricting the search space to exact solutions. The task of the ordinary exhaustive search is to assign a location to each vertex. When searching for exact solutions, we can consider the additional task of assigning a vertex to each corner. That provides additional opportunities to reduce the branching factor: at each step of the search, I consider both the number of legal locations for each vertex and the number of legal vertices for each corner. Whichever has the fewest possibilities is worked on next.
I also incorporated some additional search pruning that I had implemented and discarded while developing the heuristic solver. I precompute the maximum possible distance between each pair of vertices and use that information to constrain the legal locations for a vertex based not only on adjacent vertices but on all vertices in the graph.
The exact solver managed to find solutions for about 20 more problems, or about 60% of those remaining, giving me a total of around 1,100,000 points. Here are the problems solved and rough running times:
About 13 problems remained elusive:
After the 2016 contest, someone on Reddit asked contest participants what 80-character message they would send back in time to most improve their contest performance. My answer was “write a visualizer for your solver.” I only did it after the fact in 2016, but it proved very helpful in understanding the behavior of my solver.
This year I took my own advice. All of my solvers included the ability to watch the partial solutions produced as they worked. It helped with development of the solvers as well as with understanding how they were performing on specific problems, deciding whether to let them keep running or move on to another problem, etc.
During the contest, the spec was modified to introduce several kinds of “bonuses.” If a solution to a problem contains a vertex at a specific location, a bonus is earned which can then be used in a specific other problem. Bonuses relax the constraints on valid solutions, e.g. by allowing an edge to be broken in half or a vertex to be placed outside the hole.
Throughout the contest, I always had higher priority work to be done just trying to solve enough problems using the original rules, so I never did anything with bonuses.
This year’s contest was probably my favorite in some time.
Thank you to the organizers for all the hard work, and congratulations on a job well done!