ICFPc 2022

ICFPc 2022 was a good contest. It had a relatively interesting problem and possibly the lowest barrier to entry compared to earlier ICFP contests. It was time well spent.

This year's task is essentially a lossy compression problem, approximating target images with rectangles.

It actually works quite well for something like Mondrian's paintings (which has lots of rectangles), but for most other pictures it came up to be a blur. This is because this year's task requires minimizing a cost function that is the sum of the image's similarity plus the cost of operations, and the similarity function is well tuned such that additional operations only marginally improved similarity. By tweaking the similarity function, we can see how work done on this contest can actually produce something practical.

I approached this task in two steps:

1. Finding where to place all the nested shapes, where nested shapes are created by cutting existing rectangles.
2. After having find the shape placements, assign colors to the shapes to minimize cost.

I spent ~34 hours on this year's task, about 2 hours of it was spent on step 2 (coloring) and that bit remained roughly the same throughout the contest. Majority of the time was spent on step 1 (where to cut).

Color selection

Coloring was done by traversing the nested shapes from root to leaf and assigning colors to the largest shape.

1. Rasterize all nested shapes onto a grid, where each cell contains a shape ID. The intent is to have shapes that are drawn later overwrite some or all of the pixels claimed by an earlier shape, so that I can decide which pixels mattered in assigning colors to shapes.
2. For each shape, decide which color to use by averaging all pixels that aren't covered by another shape.
3. Assign color to this shape if it's cost effective. If some parent shape is completely covered, assign the color to that parent instead, since it's cheaper to color larger shapes.
4. An extra optimization was added in the full round, where if a shape and its children does not have any color assigned, remove all cuts from this shape to reduce costs.

Or, it would have worked like this if I fixed all the bugs, which I probably didn't. A great time saving strategy is to never write any bugs in the first place, then I wouldn't need to test for them or fix them later. Well, this year I survived purely with assertions and didn't bother writing any tests, and honestly I had lots of bugs, but this year's contest was very lenient so I just rolled with it.

Where to cut

For the lightning round, two strategies were attempted:

• Divide the target image into uniform halves and quads recursively up to a predetermined depth, and assign colors to those.
• Divide the target image only once into nonuniform quads, using binary search to find a good position.

Neither really worked because the code was buggy, so most of my lightning round submissions are actually just a single color that is the average of all pixels in target image.

For the full round, I tried a few different strategies:

• Assign uniform color to the whole block. This is meant to verify the handling of multiple initial blocks, which is a new feature added in the full round that wasn't in the lightning round.
• Find a horizontal or vertical position to make a linear cut, and accept the result if replacing both halves with a uniform color is better than replacing the whole block with a uniform color. If any cuts were made, apply the process recursively to the two halves until it's no longer cost effective.
• Find a position to make a linear cut or a point cut, and accept the result if replacing any of the sub-parts is an improvement, then apply the process recursively. This was the best strategy I found. It was also quite slow because I was testing all (x,y) positions by brute force. Porting the binary search bits from lightning round might have sped this up, but I figured just letting the computer run the search in the background is a better use of my time than fixing my buggy search.
• Manually find where to cut. I tried this on two of the problems, it didn't work at all for one of them and produced only slight improvement for the other.
• Apply a pre-processing step to swap various blocks. This is needed because it's too expensive to color the small blocks in some of the later problems. Or is it? I am not sure I got the cost function right.

Missed opportunities

I didn't make an interactive tool to solve the problems manually, so I didn't quite get the same hands-on experience that I had last year. I suspect it would have been fun to play with such a tool, but my experience with the two problems I did try to manually solve suggests that a manual tool probably wouldn't have helped.

Throughout the entire contest all the way up until the end, my program never produced the same cost values as the contest playground. I had fixed some of the more egregious bugs that caused wildly different cost values, but I never quite matched the cost values exactly. Most of them were in the same order of magnitude so it was kind of workable, but there were likely some solutions I missed because I had bugs in computing costs.

None of the initial or target images contained alpha values, but alpha values for the intermediate shapes might have helped to better approximate the gradients seen in the target images. I did not explore any of that because I didn't think I would be able to get the alpha composition code correct in time.

Actually, I didn't use the full contest spec -- the "merge" command I did not use at all, even though that would have made it cheaper to apply color to some of the shapes. The "swap" command I only implemented very late as a preprocessing step, and not integrated as a more generalized search step. These are things I might do if I had more time, but in 3 days, it wasn't quite worth the effort and risk.

Final thoughts

This year's contest had roughly the lowest barrier to entry ever, where submitting even a blank solution could score me some points. I greatly appreciate task that are easy to start but has hidden depths that are difficult to master, so this year's task had just the right difficulty.

I also very much enjoy problems that are visual in nature, and had a good laugh over the many variations of Mona Lisa this year. Due to the low accuracy similarity function, most of the output came out to be a blur. I suspect the alpha constant for the similarity function was tuned to make deep searches not cost effective, and I can kind of appreciate the blocky aesthetics, so I would say this aspect of the task went rather well.

Overall, I would say the ~34 hours spent on this year's contest was time well spent. 34 hours is less than the ~43 hours I spent last year, mostly because there are fewer things I wanted to try this year, and it wasn't that the task was any way less engaging. I was actually worried about how this year would turn out due to scheduling problems, but it turned out OK and I had a good time.

Many thanks to the organizers for another great year!

Appendix

• Album with target images and my solutions.
• ZIP file with my source code.

Previous (2022-08-02): "Project Hail Mary" by Andy Weir
Next (2022-09-14): "No Game No Life" volume 11 by Kamiya Yuu

Index

uguu...