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

__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.

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.

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.

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!)

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!

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!

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. |