Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Source code:
source.zip
Solutions:
solutions.zip
The Frictionless Bananas had only one team member this year. This page describes my 2022 ICFP Programming Contest entry.
This year’s task was to replicate a series of images by providing instructions for a robotic painter. The instructions mainly allow splitting a canvas into rectangular blocks, applying a solid color to a block, and merging blocks back together.
Scoring is based on two factors: the similarity of the resulting image to the original and the cost of the instructions. Instructions are more costly when they operate on smaller blocks, so it is difficult to reproduce fine details accurately.
One of the main building blocks used by my solvers is a tool for determining the optimal colors to use in a solution. Given a solution containing multiple instructions that apply color a block, I first determine which pixels are colored by which instructions, and then for each instruction I find the color that minimizes the sum of the distances between that color and the desired color for each pixel.
Finding the correct color is equivalent to finding the geometric median, which is not a trivial problem. At first, I used Weiszfeld’s algorithm as described on the Wikipedia page. Later I switched to an approach where I start with an arbitrary color and continually adjust one of the components by decreasing powers of two until no further improvement is possible. In the initial stages I also use a sample of the points rather than all of the points to improve performance.
I chose to build my solutions by first choosing a sequence of rectangles to draw, and then converting it to a sequence of instructions. For each rectangle, I split the canvas to obtain a block of the appropriate shape, then color it, and finally merge all of the blocks back together. I use an optimal set of cuts and merges for each rectangle in isolation, but I don’t optimize across multiple rectangles.
In problems where the initial canvas is split into multiple blocks, I first merge them all back together, and then proceed with drawing rectangles as above.
My first attempt at a solver builds up a list of rectangles one at a time. At each step, I choose a random rectangle and then repeatedly tweak it by adjusting one of the four boundaries until no further improvement is possible. I repeat that process for ten random rectangles. Whichever rectangle results in the largest score improvement is added to the end of the solution. The process continues until none of the rectangles produces an improvement.
This solver produced some reasonable solutions for some problems, but it was slow and did not do well with other problems.
Since the number of problems was so low, I decided to try building a manual solver. The idea was to manually draw a sequence of rectangles, then let the code tweak their boundaries automatically (in addition to finding optimal colors).
I had hopes for a tool that would let me select rectangles, drag them around, resize them, change their order, delete them, etc. What I ended up with was a tool that lets me draw the rectangles in order with no editing. I did add an undo feature after making one too many mistakes.
While solving problems manually, I noticed how important it was to draw large rectangles. Rather than drawing the rectangle I actually wanted, I would draw a large rectangle all the way to one of the corners of the canvas, and then cover most of it up with another rectangle. I realized I could automate that process.
I extended my manual solver to start with an initial grid of rectangles, all sharing a corner with one of the corners of the canvas. I also added a feature to delete any rectangles that are not improving the score.
At that point I was no longer drawing rectangles by hand. Instead, I was using the manual solver as an interface to select a sequence of automatic optimizations. Typically I would start with a grid of rectangles of an appropriate size for the image, then repeatedly run the automatic optimizers that delete unnecessary rectangles and tweak rectangle boundaries until no further improvement was possible. Some of my best solutions towards the end of the contest were produced that way.
When the scoreboard was frozen two hours before the contest, I was in 16th place with a score of 931467. By the end of the contest I had improved my score to 822715. That would put me in 11th place if other teams kept the same scores, but of course they were also improving.
This was a really fun contest. I liked the task. I understand there were a number of bugs and glitches along the way, but they were usually resolved by the time I looked.
Thank you to the organizers for stepping forward at the last minute and running an excellent contest!