This year’s ICFPC was about folding origami and creating origami problems for other teams to solve.

Our team Snakes vs Lambdas consisted of almost 4 members this year. We got into 22nd place according to frozen leaderboard. Full results will be announced on the conference in September. I would expect for us to stay around the same place +/- 3 positions. (update: we finished at 26th place, see bottom of the note)

Snapshot of our workdir could be found on github.

General impression

First of all, the contest was really great! In particular it had the following qualities that distinguish amazing ICFPC from mediocre ones:

• Common sense problem with cool mathematical background.
• Players are competing against each other rather than for some abstract score. (this wasn’t a full PVP as in ICFPC-2011, but still a close one)
• As a consequence of previous point, you were never “done” as the new and more complex problems were revealing each hour. It felt like an arms race.
• Leaderboard.
• Well defined API for programmatic access with clear limits.
• Problem was deep enough to explore different routes.
• Friendly checkers: keeping the best submitted score, good error messages.
• Organizers were fun folks: great problem flavour, good jokes in their twitter @ICFPContest2016, sushi leaderboard.

Tools

• Main language: python
• Glue language: bash
• UI language: javascript
• Visualization library: matplotlib
• Geometry library: sympy.geometry
• VCS and file sharing: dropbox

Solution

I can cover this part only briefly as I was mostly focused on submitting problems and general infrastructure.

Initially we thought about some brute force way of unfolding by edges, but even for small test case it felt too computationally intensive.

The breakthrough was to notice, that if polygon is convex and fully inside the source square then it’s possible to find exact solution: wrap the figure as if using piece of paper.

Even though the algorithm looks simple, coding it is non-trivial. We had to spent some time thinking about good abstractions to make it work:

• Maintain list of (facet, T), where T is the 3x3 matrix for congruent mapping that is currently applied for this facet.
• Originally it has only 1 element (square, diag(3)).
• Take the next edge L of target figure.
• For each facet, find intersection of L and T(facet).
• If it’s non empty, replace (facet, T) by two (facet1, T), (facet2, R * T), where facet2 is the one that on different side with figure and R is matrix for reflection by edge L.
• Continue process until reaching the limit on solution or nothing has changed.

This process worked pretty good: for non-convex it was finding good approximation, for convex the solution was exact. The problem was to fit the figure into original square. We need to find rotation so that conditions are true max(x) - min(x) <= 1 and max(y) - min(y) <= 1. All coordinates should be rational so such rotations correspond to pythagorean triples. We try all triples under 1000 and angles formed by segments in the figure.

This was a main idea of our algorithm that we used. The source code is in origami_deploy_rot.py.

• Total downloaded problems: 3528
• Sent solutions: 3464
• Solved perfectly: 1006
• Our problems: 45
• Server error: 21

Around 24 hours before the end of context our 4th team member appeared who was then writing solution for unfolding problem (the type of problems our algorithm was bad at solving). He implemented nagibagtor - brute force approach for unfolding polygons using C++ and CGAL as geometry library, but it didn’t give significant wins. Contest was almost over at that time so we didn’t have time develop it further.

TODO: stats comparison of algos

Submitted problems

T+25 hours: Our first problem. We hardcoded all coordinates and facets.

T+26 hours: We added some obfuscation in the form of rotation and shift.

T+33 hours: Simple bend.

T+43 hours: Reflections against 3 random lines.

T+49 hours: We applied theory about sum of alternated angles and produced this interesting example that couldn’t be constructed using paper. We wrote a script sgibatel.py that calculated resulting coordinates.

T+54 hours: We were trying to produce this example using the same theorem and script, but discovered several bugs in the program. After fixing a some of them we got almost the right result. But the right bottom corner was not quite there and it was already too late in the night to debug so we abandoned this approach.

T+65 hours: Our diamond-like problem was solved by number of teams. Presumably they were able to brute force it, so we added a few more reflections. In the end, this type of problems was solved only by 1 team.

Infrastructure

We were using dropbox for synchronization between team members. It works really great! You write your scripts that produces files in filesystem and they become automatically available for scripts of others. We wrote a bunch of such scripts that helped to semi-automate (we didn’t enable cron jobs) dealing with problems. This section will cover more details of this.

Here is subset of directory structure for our project.

Dropbox/
  - snapshots/
    - 1470603600
    - 1470610800
  - latest_snapshot -> snapshots/1470610800
  - tasks/
    - t1014.txt
    - t1018.txt
  - img/
    - t1014.png
    - t1018.png
  - solve_convex/
    - sols/
      - s1014
      - s1014_0.893841
      - s1018_1.0
  - js/
    - index.html
    - generic_queue.html
  - download_new_problems.py
  - convert_all_to_png.sh
  - new_queue.txt
  - approx_queue.txt

download_new_problems.py

1. fetches information about all available snapshot
2. downloads the latest one to snapshots/
3. creates a symlink latest_snapshot to it
4. goes through the list of available problems and finds the problem statements that are missing
5. downloads missing problems to tasks/ dir.

convert_all_to_png

1. goes through the list of files in tasks/t{Id}.txt
2. creates a visualization of task in img/t{Id}.png

origami_deploy_rot.py: our solver. Reads problem description from stdin and writes solution to stdout.

We used sols/s{Id} for solutions and sols/s{Id}_{resemblence} for submitted solutions. We wrote hacky bash script that was going through the list of problems, solving them and writing resulting files. There was another script that was sending solved problems without a resemblence. The scripts were smart enough not to do the same work twice by checking if particular file already existed. Since there is per-second rate limit, the sending script should work only from one computer, while solving scripts could work in parallel.

We wrote a pipe_line.py script that was computing new_queue.txt and approx_queue.txt. These are the order in which the solver should process files. new_queue.txt is for tasks that doesn’t have any solution. approx_queue.txt is for tasks without exact solution, sorted by amount of score we got in case of solving it precisely.

To deal with rate limiting I tried using ratelimit library in python:

from ratelimit import *

@rate_limited(1)
def make_request(self, endpoint, use_json=True):
  ...

But then we used good old sleep and retry logic, as most of the communication was happening outside python via curl.

We also built visualization html pages on top of generated files (mainly img/ and latest_snapshot):

• Leader board with clickable team names to see problems they submitted. It also contains score for submitted problems.
• The tasks we submitted
• Queues visualization

The code lives in js/ and UI itself is available at http://pankdm.github.io/icfpc/2016/.

[Update] Top 50 of final results