Zig, Skia, Clojure, Geometry and the Japanese TV Show: ICFP Contest 2021

Every year I participate in ICFP Contest, or ICFPC for short (ICFP stands for International Conference on Functional Programming). This is a team coding challenge that lasts for 72 hours and in which you have to solve a series of very hard tasks by writing (functional) code.

Tasks are usually too hard to find a perfect solution, the best you can hope for is a good approximation. The team that found the most solutions and approximated the best wins.

This weekend was my third contest, and, as usual, it was great fun. Here’s my experience report.

Preparation

None :)

ICFPC is best played with friends in the same room. Second best is the team over Skype.

Unfortunately, I completely forgot about the contest and didn’t assemble any team in advance. So I played solo this time.

It also makes sense to prepare a little: have a project template set, rent some EC2 servers for hard number crunching, build a dashboard, build a mastermind service that distributes problems and collects solutions, assign the roles in the team, etc.

As you can imagine, I did nothing of that too :)

The Problem

The problem this year was inspired by a Japanese show where people must fit in a hole in the wall, usually very creatively shaped.

More precisely, you are given a hole (gray) and a figure (green):

Your task is to transform the green figure so that it fits in a hole. The original figure is not ok: it doesn’t fit.

If we move some vertices around, we can make it fit:

Unfortunately, this won’t do either: you are not allowed to change the length of the segments.

Moves, rotations, flips and overlaps are ok though. This is a valid solution:

Of course, many different valid solutions are possible. To score most points, you must find a solution that is most spread out (for exact definition check the spec).

Oh, and all the points have integer coordinates. But don’t get excited: most tasks have 10+ vertices and a grid in the range of 100×100. That gives you at least (100×100)¹⁰ = 10⁴⁰ permutations, rendering bruteforce waaaaay out of the question. But at least there’s a grid!

First quick score

Ok, so what’s the approach here? After reading the problem on Friday at 2 pm, the best idea is to inspect some problems with your bare eyes. Kudos to the organizers who put PICTURES next to the problem descriptions! The source of truth is JSON, but pictures certainly help.

After scrolling through few first problems, I found one that can be solved in a notepad! Problem 11 requires you to just rotate a triangle.

Perfect! I typed in the solution into the Sublime Text directly and uploaded it via web form. The first score, just 22 minutes after the start!

Visualizer + manual solver

After exploring a few more problems, it became obvious that many of them can be solved manually by just moving a few points. Together with Twitch Chat we decided to build a tool to assist with manual solving.

My language of choice is Clojure (of course!), a language perfect for rapid prototyping.

But what to use for UI? The obvious choice is browser, but I didn’t want to go to the browser: it’s slow, complicated, not reliable, ClojureScript is a pain in the ass. So I decided to aim for the native UI.

Luckily for me, I have just built the thing for that! It’s called JWM, a Java Window Management library, and Skija, a Skia wrapper for JVM. So I went with those.

An anecdote: JWM is still in the active prototyping phase, barely enough to get something useful out of it. It works, but don’t expect miracles. E.g., it doesn’t have mousedown event yet, but it does have mousemove and keydown. So in my UI you press space and then move your mouse :)

Otherwise, all went great with the visualizer. Clojure + Skija are performant enough to hit 144 Hz with thousands of nodes, edges, circles, text labels, and grid redrawn every frame with no significant slowdown. Perks of not living in the browser!

After that, I just went and solved as many tasks as I could. Here’s an example:

Sorry, no dark theme this time.

First taste of automation

After a few hours, it became obvious that some problems have the perfect solution: if a figure’s vertices occupy all of the hole’s vertices, that gives you a perfect score of zero (less is better).

Since the amount of hole/figure vertices is relatively small, this became a perfect target for brute-forcing. Here, all the edges are places automatically (if there’re multiple possible placements, they are iterated over), and the rest is easy to figure out manually.

Believe it or not, this approach allowed me to do as high as 14th place in the first 12 hours. Unfortunately, after that, other teams caught up.

The joy of first half-automated solution bearing fruit

The comforts of Clojure

To figure out which problems have the perfect solution, I scrapped the organizers’ website where they posted the best scores for each problem.

Surprisingly, it only took me ten minutes, including figuring out page structure, looking up http library docs, making a request, a few trials and errors, integrating and committing the final code.

Here’s the entirety of that code:

That’s the perfect example of why Clojure is so good for rapid prototyping.

Going low-level

Solving tasks manually did well in the beginning, but going forward, we need some automation.

Participating in 2019 ICFPC taught me one thing: it’s hopeless to do number-crunching and brute-forcing in anything but C/C++/Rust. Clojure is too slow, Java is too slow, and speed here is the most important advantage. Faster solutions win the ladder.

The irony: functional programming contest is won year after year by good old imperative/OOP languages:

Ok, so I need down-to-the-metal, low-level language. C was ruled out as too old, C++ was ruled out as no fun, Rust was ruled out based on my 2019 experience with it.

Rust is great for reliable production systems, sure, but for quick-and-dirty prototyping, it’s too strict. Imagine figuring out a perfect algorithm and spending a few hours implementing it just to be told by the borrow checker it won’t let it pass.

For something like a 3-day coding sprint I’m happy to have unallocated memory, data races, undefined behavior, and data corruption as long as I get to try out ideas quickly. And it’s hard to convince Rust to let it go.

Meet Zig

Based on the logic above, and also my curiosity, I decided to give Zig a go. Did I have tons of experience in it? No. Do I like checking out hot new things and learning languages? Yes. So in the end, was it fun? Hell yes.

What do I have to say about Zig?

I like its approach: get rid of all the complexity that computers and programming languages have accumulated over the years and try to re-implement everything from scratch, raw, bare, but also simple and not constrained by the prior conventions and restrictions.

It’s primarily developed by one person, so it’s not bloated (yet, hopefully, forever).

It’s very low-level, C-like. I honestly almost forgot how it feels to carefully worry over every string you concatenate. It’s not bad, it’s exactly what the language aims for. Just took me by surprise.

It improves over C significantly. Both in the sane defaults, language ergonomics, macros and build complexity.

defer is pure genious. It lets you write cleanup code (free memory, close file, etc) right next to the resource initialization itself:

const path = try std.fmt.allocPrint(allocator, "problems/{}", .{ id });
defer allocator.free(path);

var file = try std.fs.cwd().openFile(path, .{});
defer file.close();

const stat = try file.stat();
var contents = try allocator.alloc(u8, stat.size);
defer allocator.free(contents);

This way it’s way harder to forget to clean up since the code is right next to initialization, not at the end of the scope. And if you need to return early, only already allocated resources will be cleaned. Genious!

Error monad is built into the language too, which is also very convenient. Every function has two return paths: normal and error. There’s also special syntax to work with that (try, errdefer, Error Union Type).

C interop must be very good, but I didn’t have a chance to check it out. Comptime (~macros) should be good as well, but I haven’t got that far either.

So overall I like Zig language very much and absolutely happy with my choice. Just beware: it’s still way less finished than, say, Rust is. But it already feels great and can be used for a lot of things already.

A quick home-made snack in the middle of the contest

I only have one serious question for Andrew Kelley, the author of the language: why did you name a for loop a while?

var i: i64 = 0;
while (i < 1000) : (i += 1) {
}

A quick geometry lesson

Ok, so we are working with geometry. What do we need?

First, we need a way to check if two line segments intersect. Turned out it’s pretty simple: line segment A and line segment B interset if and only if:

Looking from A, B’s ends lie on different sides of A.
Looking from B, A’s ends lie on different sides of B.

It’s that simple.

Left: true/false, middle: false/true, right: true/true

Quick lesson for the future participants: don’t hesitate to google code like this. Someone has already figured that out.

Quick lesson #2: when copying it, try to not mess up variables name/order, otherwise you’ll be like me :)

Ok, the second thing we need: how to figure out if a point is inside a polygon?

Very simple, actually. Cast a ray from the point in any direction, count how many times the ray intersects with the polygon. If the number is odd, the point is inside, if it’s even, then it’s outside:

0, 4 = even = outside, 1, 3 = odd = inside

One gotcha, though. What if your ray hits a vertex exactly, intersecting two edges this way? Or what if the polygon’s edge aligns perfectly parallel with your ray?

Unfortunately, we hit those problems really hard. After trying to patch it with special case handling, we gave up and just choose a point with large prime coordinates way outside of our polygon.

We chose (530711, 378353), two different large prime numbers. What it gives you is that line segment (0, 0) .. (530711, 378353) is guaranteed to not hit ANY integer coordinate in 0..530711 × 0..378353 area.

P.S. Our implementation has a bug, though. The far end should’ve been x + 530711, not always 530711. Still worked in practice—I guess we were lucky!

Do I need to explain how to calculate the edge’s length? Hopefully not :)

Benefits of programming live

I was not completely accurate when saying I was flying solo. After the start, Dmitry joined me through Twitch Chat and gave me a lot of useful advice. Enough, in fact, that I consider him a part of the team.

Many other people visited, too, which kept the whole thing alive and entertaining. Thank you all!

Brute forcing all the problems

With all this preparation in place, we started writing a brute force solution.

The idea was quite stupid, really: place the first node in all possible 0..maxx × 0..maxy coordinates, check if it’s inside, for each position, try placing the second node in all possible coordinates. If edges are too long/short, abort early, otherwise, continue with point three and so on.

This is a stupid, most straightforward solution and it only worked for a very few problems with a low number of nodes. Anything 12+ was out of reach and required a different approach.

Unfortunately, by that time I had no time nor energy to experiment. So I left the solver overnight in a hope that it will find at least something. Spend a good hour writing a program that runs my solvers in parallel and kills them after 30 minutes to free up CPU time for other tries.

Leaving it for the “night” at 6am in the morning

The end

I woke up an hour before the end of the contest to see if my program has fished anything out.

The algorithm did, in fact, found some solutions. Many of them could be very obviously improved, though: it finished (didn’t have time) too early.

Still, it was partially useful, and I corrected and submitted everything that was found during the night.

Before the rating was frozen, I rated at 70-80 place in the ladder, about its 50% median.

Ideas started coming, though. If only I had one more day!

Meta game

As usual, rules change a little along with the contest. There are two major additions: one 24 hours after the start, and then one more 24 hours after that.

I suppose it’s mostly for the teams who perform better so that they have something to do. Not me, though: I was too busy solving the original task, though, and haven't looked into additionals at all.

To sum it up

As you might’ve guessed, ICFPC is totally my cup of tea. 72 hours of very condensed programming on a very hard problem—what could be better?

Also, few things compare to the feeling when you hit a super confusing task, run a program that you just wrote and haven’t even tested, and after a slight delay it figures out a beautiful and simple solution. I almost cried every time it happened.

Some hints if you decide to participate next year:

Certainly try, it’s worth it 100%.
Gather a small team, preferably in a single physical location.
Prepare some infrastructure, at the very least: a github repo and a project template.
Take breaks, sleep well and eat well. Did I do it myself? Haha, of course not. But don’t be like me :)
Bet on a low-level language, you’ll get an upper hand in the end.
Rapid prototyping is another key. Whether it’s more important than raw performance, I don’t know :)
Do write a visualizer. No matter how much time it’ll take, it’s always net win in the end.
Save all solutions in some central shared location, good or bad. In the end, then choose the best solution, no matter which algorithm or which version found it.
Don’t make your code too clean, best practices don’t really apply to a code that you’ll throw out in 3 days. But try to keep it at least sane.
Do read writeups after the thing is over. It’s about as much fun as the contest itself. Different algorithms, different ideas, different UIs. It’s almost like looking at parallel realities.
Write writeups, too. At the very least, share some screenshots.

Source code? You don’t want to look at the source code. Even more: I strongly discourage you from looking at the source code. But it’s available.

Thanks to the organizers, to Dmitry, to everyone who came visiting my stream. Hope to see you in the rating next year!