ICFP contest 2016

Egér a Marson - ICFP contest 2016
v0.92

(Note: The problem was about folding origamis, see the contest home page or the PDF description for details).

This year was a first for me in that this was the first time I participated alone (the usual mates had family programs and/or were sick). Since that also meant less external constraints, I decided to put my reasonably full efforts into the contest (unlike last year's lazy weekend, when we spent too much time on the beach :). I think I succeeded in this, but it was not enough, after all.

I used Haskell as usual, except for the REST API where I just hacked together some Python script using google / stackoverflow, as dealing with JSON in Haskell is not my favourite activity, to be completely honest...

General comments

I liked this years problem and the contest in general. Much more interesting problem than last year's pretty generic optimization problem, which I was frankly bored with. The organization was also quite professional; my favourite part was that the REST API guide had curl examples personalized with the team's API key, kudos for that! There were a few minor issues, but that's normal (though I read that some teams were seriously bitten by the under-communication of an early mistake in the description of scoring).

However, I found the task rather hard for a one-person team. Part of it was probably me being way too slow to figure out some basic geometric constructions (see below for details), but I also believe that there was simply too much details to work on for just one guy:

REST API
visualization / interactive GUI
geometry / mathematics of folding
manual solving of some problems
computational geometry algorithms
problem creation (with strict deadlines, too!)
various solver strategies
time management, handling network rate limits, checking scores...
etc etc

I mean, I spent as much time awake and coding or thinking as reasonably possible for a normal human, I wrote mostly nice code doing all kinds of fancy geometry, which was by the way not an alien subject to me even before, and it was still not enough: I only started to be able to solve relatively trivial problems about 3 hours before the end of the contest, and then in the last two hours I just gave up. It would have been a serious advantage to have access a few clones of myself, though!!

Timeline

At local time (UTC+2) the contest started two hours after midnight on Friday. I managed to sleep only approx. 3 or max 4 hours before the contest, not the best start. And, honoring a long tradition (or maybe you could say, to add insult to injury...), I kept drinking a beer about every 3 hours while awake during the contest (that's how we roll, baby!). Maybe that slowed me down, too, though I don't believe in that :)

I spent the first hour reading and hacking together a Python script to download the problem. I was able to parse problems at T+1:45 (using parsec); I had basic OpenGL rendering of problems set up, and "UI" for moving between them at T+4h. A nice touch was done at T+5h, when I wiggled the zoom factors so that the renderings on the screen were exactly the same size as my fortunately large supply of approx 10cm x 10cm square papers - this helped to be able fold (with real paper I mean) some problems the organizers gave. (Like some other contestant, I was also stumped on problem 17 for a while...). I wrote a better renderer, handling non-convex polygons properly, by T+6h.

an early and a later visualization attempt

At T+8h, I submitted my first solution (for problem 17), done completely by hand, and by that I mean I typed the solution into a text editor. But hey, it was accepted! (now we have to wait 42 hours for the next submission...). Based on the experience I had the not-too-bad idea of using the mouse to select vertices and edges (and later, also facets) and use their coordinates to semi-manually create solutions; thus I proceeded, and implemented the first half of that (but not the submissions...). I think I went to a sleep a few hours (meaning 3 hours) here. When I woke up I also wrote a parser for a simple scripting language intended to describe foldings; this remained unused later.

unsuccessfully trying to wrap my head around alien geometry

At some point I realized that I should really switch and think about how to create new problems for submitting, as there is a strict deadline for that (this was really though on me - even after I decided not to participate in the lightning round, I still had the same hard deadline of 24 hours!). I think by this time I realized the following geometric facts:

Lemma: A vertex where 4 edges meet can be folded if and only if the opposite angles sum to 180 degrees.

Lemma / Conjecture: The paper can be folded along a graph if and only if it can be locally folded around each vertex.

Thus the idea I had for creating problems was to create random graphs with these properties, and then fold them. So I started coding this; during which I wrote a simple graph library, and a complete mini-library to deal with the geometry of the edge of the square paper, among other things... However, one important thing was missing: folding the resulting graph! I couldn't for my life figure out how to fold it together. Finally I gave up and tried to do it manually for the specific type of "neklace" graphs I implemented, which half-succeeded (it only worked in some special cases when the corners of the paper lied in the "right" regions...); but at least I could submit some problems, if not at T+24h, but 15 hours later... (I even had time to sleep inbetween!)

a neklace graph, before and after folding

The breaktrough idea came at me finally around T+41h, a bit late, but finally I felt like I'm on track! This is really nice though: Consider an already folded origami. Now realize that you can take a scissor or knife, and just cut along some edges - of course, nothing will change! So here is how to fold along a graph drawn on a piece of paper:

select a facet which will be fixed;
choose an arbitrary spanning tree of the dual graph, rooted at the selected facet
cut all the edges which do not cross the spanning tree
fold the remaining edges as you walk down the tree
aaaand, that's it!

Use the scissor, Luke! This algorithm will fold any valid folding graph you throw it. So I proceeded and implemented this. I got it working around T+42h; shame it took such a long time... I started getting some points from the submitted problems though; at some point I was even as high as the 35^th place, with only a single submitted solution!

The next idea was that one can do valley-folds in the source space by doing "zig-zag raytracing", mirroring the ray each time it meets an edge. So I implemented this, too (got it working around T+46h). It helped creating a tiny bit more complex problems (but they looked good in the source space at least :). Unfortunately I only realized too late that normally you want to do valley folds in the destination space...

Lot's of confused thinking, and some sleeping followed.

Finally, as I had the geometry mostly down (or at least I thought...), I could concentrate on solving the problems! Except, I had no idea how to solve them. The half-formed thinking was to try guess the affine transformation, say based on the corners, then try to guess the edges along which it is folded (if you do a simple valley fold on a piece of paper, the original edges of the paper will be symmetric to the edge along which you solved; this is relatively easy to recognize), and then try to fold along these edges maybe in different orders. This should work at least for some simple cases, but not exactly robust... Also I was seriously running out of time (and ideas)

Meantime, I had problem 19's source graph done by hand from a much earlier time, so I thought maybe I should submit at least that. The rotation guesser didn't really work for this, so instead I used the interactive "GUI" to specify the transformation by selecting a source and target edge, and using the above folding algorithm to fold. Hurray, I now have 2 (read, TWO) submitted solutions, 10 hours before the end of the contest!

look! a problem the computer somehow solved itself?! I'm kind of impressed

And then, I managed to do proper valley folds, in the destination space this time, not the source space, 4 hours before the end! I'm a pro, really. And like a champion, I implemented the above plan to solve almost-trivial cases. And it even kind of worked! I submitted like 200+ solutions I think. Haven't cared about checking if they were any good, though I got lots of "resemblance = 1.0" replies. I guess those were the unfolded squares submitted by people without better ideas... Probably worth like 0.15 points each.

Anyway, I had about 2 hours left, I was tired, and had no more breaktrough ideas, so slowly I gave up. Spent some time checking out other people's problem submissions, scores, did a README and source code submission, etc, but I almost went to sleep 20 minutes before the end of the contest (I didn't, though!). And that's about it for this year, folks...

The beer diary

(the diary is published in it's original form, edited only for formatting)

My dear Diary,

T-07:00 drank a can of beer as a special preparation technique [Heineken, #0]
T-04:00 I went to the bed, and managed to sleep something like 3 hours before the contest
T+01:00 the task seems hard, and I'm sleepy. So I opened a beer :) [Pilsner, #1]
T+03:45 time for another beer! I really need to start to think about how to solve the problem... [Pilsner, #2]
T+09:30 GUI programming requires another beer [Pilsner, #3]
T+11:30 went to a walk. Bought more beer.
T+13:00 let's try another beer, maybe it helps, who knows?? [Krusovice, #4]
T+15:30 i'm brave enough and now try to sleep before generating problems for upload (even though there is a deadline!)
T+19:00 woke up. I'm reasonable confident I would be able to sleep until the morning, though!
T+21:00 maybe rational geometry is also helped by a beer [Pilsner, #5]
T+24:00 no problem submissions yet, but I seem to be on track. What about a beer? [Pilsner, #6]
T+28:00 still somewhat stuck (even though I understand things better, I'm tired). Let's sleep.
T+33:00 breakfast. I could have slept more...
T+35:00 i'm really fed up about still not finding a good representation of the source graph for which I could finally code the proper algorithms, so let's have a beer [Pilsner, #7]
T+38:00 managed to (manually) generate a valid unfolded source problem, but cannot fold it correctly :( time for a 3-hour beer [Pilsner, #8]
T+41:00 bought more beers. And finally got a usable idea! Shame it took such a long time... But let's try it
T+42:30 beer time! [Pilsner, #9]
T+45:45 debugging the raytracer, time for another beer, it should help i think :) (and indeed, it helped!) [Pilsner, #10]
T+48:45 the 3 hour beer cycle rythm seems to be really stable (also, again debugging) [Staropramen, #11]
T+51:00 one last beer before sleep. I should figure out how to automatically solve at least the easy problems... [Krusovice, #12]
T+53:00 time to sleep (even though I'm running out of time!)
T+57:00 while 3 hours makes a fine beer cycle, I can't say that about the sleep cycle of the same length...
T+59:00 fuck, i need to somehow get the silhouette of a solution to be able to match the rotations... maybe a beer will tell me how? [Pilsner, #13]
T+61:00 seriously running out of time (and beer). I'm panicking, no idea how to automatically submit solutions... [Staropramen, #14]
T+61:30 bought more beers before the shop closes
T+64:00 i haven't bought those beers to let them sit in the fridge!!! [Staropramen, #15]
T+67:30 4.5 hours before the end of the contest, I can now *also* do a valley fold on a folded thing like a champion... and to cope with that, I need a beer. [Staropramen, #16]
T+69:45 I submitted some 200+ trivial cases blindly. Given some more time, I think I could come up with better solvers... Time for a final beer. [Pilsner, #17]
T+70:30 I kind of gave up. I don't see how to do anything significant in the remaining one hour and half. Tried to check the (surprisingly few) unsolved problems. I also checked my own submitted problems, many of the later ones are only solved exactly by only one team so far.

beer consumption during the contest

T-07:00	drank a can of beer as a special preparation technique [Heineken, #0]
T-04:00	I went to the bed, and managed to sleep something like 3 hours before the contest
T+01:00	the task seems hard, and I'm sleepy. So I opened a beer :) [Pilsner, #1]
T+03:45	time for another beer! I really need to start to think about how to solve the problem... [Pilsner, #2]
T+09:30	GUI programming requires another beer [Pilsner, #3]
T+11:30	went to a walk. Bought more beer.
T+13:00	let's try another beer, maybe it helps, who knows?? [Krusovice, #4]
T+15:30	i'm brave enough and now try to sleep before generating problems for upload (even though there is a deadline!)
T+19:00	woke up. I'm reasonable confident I would be able to sleep until the morning, though!
T+21:00	maybe rational geometry is also helped by a beer [Pilsner, #5]
T+24:00	no problem submissions yet, but I seem to be on track. What about a beer? [Pilsner, #6]
T+28:00	still somewhat stuck (even though I understand things better, I'm tired). Let's sleep.
T+33:00	breakfast. I could have slept more...
T+35:00	i'm really fed up about still not finding a good representation of the source graph for which I could finally code the proper algorithms, so let's have a beer [Pilsner, #7]
T+38:00	managed to (manually) generate a valid unfolded source problem, but cannot fold it correctly :( time for a 3-hour beer [Pilsner, #8]
T+41:00	bought more beers. And finally got a usable idea! Shame it took such a long time... But let's try it
T+42:30	beer time! [Pilsner, #9]
T+45:45	debugging the raytracer, time for another beer, it should help i think :) (and indeed, it helped!) [Pilsner, #10]
T+48:45	the 3 hour beer cycle rythm seems to be really stable (also, again debugging) [Staropramen, #11]
T+51:00	one last beer before sleep. I should figure out how to automatically solve at least the easy problems... [Krusovice, #12]
T+53:00	time to sleep (even though I'm running out of time!)
T+57:00	while 3 hours makes a fine beer cycle, I can't say that about the sleep cycle of the same length...
T+59:00	fuck, i need to somehow get the silhouette of a solution to be able to match the rotations... maybe a beer will tell me how? [Pilsner, #13]
T+61:00	seriously running out of time (and beer). I'm panicking, no idea how to automatically submit solutions... [Staropramen, #14]
T+61:30	bought more beers before the shop closes
T+64:00	i haven't bought those beers to let them sit in the fridge!!! [Staropramen, #15]
T+67:30	4.5 hours before the end of the contest, I can now also do a valley fold on a folded thing like a champion... and to cope with that, I need a beer. [Staropramen, #16]
T+69:45	I submitted some 200+ trivial cases blindly. Given some more time, I think I could come up with better solvers... Time for a final beer. [Pilsner, #17]
T+70:30	I kind of gave up. I don't see how to do anything significant in the remaining one hour and half. Tried to check the (surprisingly few) unsolved problems. I also checked my own submitted problems, many of the later ones are only solved exactly by only one team so far.