Report from ICFP Contest 2022

Publication date: 2022-09-05

Every summer, the International Conference for Functional Programming takes place. And alongside the conference, there's a contest.

And every summer, we form a team and participate in this contest. This wasn't the best contest for me personally, but after some thought, I've decided to document it anyway.

This is also the first ICFP Contest report that I'll prepare in English exclusively. Maybe this will help to make it more accessible to the readers.

Let's start by taking a look at this year's task.

So, we are provided with some 400×400 images and are asked to create programs for painting robots that will paint these images (or something similar to them). The winner is the team that produces programs that have the smallest cost (every instruction has its cost) and produce images the most similar to the required ones (yes, the absolute precision is not required).

The set of moves is unusual: initially, we are provided with a set of regions (aka "blocks") the canvas is divided into, and the robot may choose to either divide a region (into either two or four pieces, horizontally, vertically or both), paint a region, merge two regions into one, or swap two regions' contents. And one of the most important details: the cost of painting a small region is bigger than the cost of painting a big region.

Preparation Phase

Since last year we were using Scala, this year we use Haskell.

Before the contest started, we have created a GitHub project and asked every team member to check if they are able to build it in their environments. Initially, the following people were in the team:

But after its start, some other people have joined us:

To organize the team communications, as usual, we have prepared an XMPP room and a Telegram chat. And, as usual, I've made some improvements to our chat linking software, Emulsion, that allowed us to comfortably share files and images between our chats.

Also, I've taken a few days off from my work to participate in the contest every day (it spans across parts of Friday and Monday).

Below, I'll recite the events that happened in our team during the contest according to my current time zone, UTC+2.

2022-09-02, Day 0

The contest has started at 12:00 UTC. I quickly registered an account (and it was unclear whether I should share the password with my teammates, but eventually it turned out that yes, I should), and we've started reading the specification.

portnov has quickly picked a Haskell library to parse PNG files (JuicyPixels), and created some very basic framework of modules for us to work in.

I have voiced two different strategies we could use: either create a precise solver that will generate an image identical to the original (but with possibly huge cost), or create something like a "progressive JPEG" which gets closer and closer to the original with each step.

Closer to the evening, sergevp has contacted Minoru and proposed a plan:

At the same time, portnov has created a basic "dummy" solver that only works on images of size 3×3.

I have started working on a dynamic algorithm that would fill everything with the most appropriate color, then seek for subregions that aren't properly colored yet, color them, and repeat. I have called my algorithm SpiralSolver.

sergevp also tried to differentiate the similarity function to find its extrema and get some useful insight but had no luck with that (since it turns out to be a known hard algebraic problem).

Minoru found that our current data model requires significant upgrades to allow us to use better algorithms, and have started working on alternative foundation for future solvers (aka Alt).

In the meantime, we have encountered an issue with Stackage LTS 19.28 (GHC 9.0.2 that is shipped with it can't do profiling), and I have tuned our Emulsion infrastructure a bit.

2022-09-03, Day 1

portnov has created a function to calculate image similarity.

I have noticed that the specification includes a round function but has no description of rounding algorithm. It turns out that the organizers were using the JavaScript's Math.round function that has somewhat unorthodox behavior for negative numbers. Minoru writes a stub that throws an exception in cases where the behavior would differ, so we can keep track of this issue.

Akon32 has joined the team and is struggling to upgrade Stack to a new enough version.

The organizers have published a specification update which now includes initial block layouts for every new task (so there's no single big block, as it was before).

I am struggling with Haskell's forM_ and list functions, but have eventually written a clustering algorithm (that should process a set of pixels and create a block for every connected cluster) that at least compiles.

Folks have started discussing some integral calculation of a sum over a rectangle, but I wasn't able to figure out what's this all about.

Also, we are trying to profile our solvers and figure out what eats the most memory in them. And I have learned to get some stack traces from GHC-compiled programs when they fail with an error (since my stuff was failing a lot!).

At the dawn of the day, pink-snow has joined the team.

2022-09-04, Day 2

During the day, I've figured out why I had problems with downloading files from the internet all the time: it turns out that my internet provider also gives IPv6, and as usual, nothing works well if you suddenly enable IPv6.

Minoru has written a "billboard solver" that's showing some good initial results. The idea is to process the image in a way similar to how a billboard works: showing the image columns one by one. Afterwards, Minoru started working on optimizations for solvers.

pink-snow has contributed to improving the speed of some API functions, and has decided to solve some tasks in a semi-automated way, and started work on the visual solution editor.

I am struggling with clustering.

One sudden reveal is that the initial specification was talking about some kind of block trees (aka ComplexBlock) which turns out to be totally unused, and there are no such trees (only plain simple blocks).

In the meantime, the organizers have published a new version of the specification, which now includes blocks that have some images drawn on them (earlier, there were only monotone blocks in the initial problem set).

Minoru proposes an idea to do "something like a Fourier transform" to calculate a better cut place when cutting the blocks.

At some point, I've decided to write a UI editor in C#, and have started (using snippets from a contest that was two years ago). But haven't finished and decided this is a waste of time at the moment.

I had a bright idea of looking at the solution dashboard and figuring out what problems may bring us the most points (thanks to Out-GridView in PowerShell, that was the easy part!), so I've decided to desert my unfruitful attempts at clustering, and start investigating the most profitable (and unsolved) problems.

I've tried to take the required image that we should draw, simplify that image manually, and then run the solver algorithm again – in hope that it will then find a less complex (and thus less costly) solution to the problem. Interestingly, simple pixelization of the image didn't do well, but when I started editing it manually and removing some central blocks at random, it allowed our solver to achieve a better result, even regarding the initial image. That was a small success, and maybe my main contribution to the work this year.

2022-09-05, Day 3

Minoru has added rudimentary support for the new JSON format (when blocks started to refer to regions of an external PNG image), and finally our solver was able to do at least something to the final portion of the problems.

This was the last (half?) day of the contest, so some folks have decided they cannot participate (which is totally okay with me). So, not much happened during the day. I've tried to quickly run our solver on all the problems, to find if we missed to upload a good solution. We did not, so I didn't do anything useful.

Before the scoreboard was frozen, we were 69th out of 150.

Reflection

During the first few days of the contest, I was becoming increasingly frustrated by Haskell (and, mostly, my inability to do anything in it). At some point, I've decided to implement part of the algorithm in F# and then port to Haskell, but even this didn't help me to overcome all the monadic tricks. I was asking some questions about basic syntactic things and was getting the answers, but this wasn't helping me much (probably because I wasn't asking the right questions, out of my misunderstanding of what was happening in compiler's errors).

Why has that happened? Was the task too difficult? I don't think so. I like and relate what pink-snow said about himself: maybe I have just too low energy reserve to deal with everything happening this year. Yeah. Maybe. Maybe next year we'll do better.

Constant battle against a compiler isn't the kind of fun I am looking for, and something has to be done about that before I use Haskell again.

As I noted in previous contests, I become somewhat productive in Haskell on the 2nd–3rd day of the contest. This time, I wasn't productive at all. So, maybe, if I start practicing at least several days beforehand, then better results may be achieved?

But hey, there's also a good thing. I was very happy with the quality of Haskell development tools, and IntelliJ-Haskell in particular. Yes, there are still some issues, but the overall experience is good. And I hope I'll be able to report all the encountered issues and improve that even more by contributing there.