This year was about fitting the given figure into a given contour, inspired by famous Japanese TV Show Brain Wall.

This is example of one the tasks:

This was my 12-th year participating in ICFPC. Below are some of my random thoughts and screenshots.

Final results

We finished at 25th place:

We were at 24st place in frozen monitor with 11k more scores submitted after freezing the monitor. This would brought us to 22nd place assuming other teams did nothing:

Members

This year we continued to write from one location and also got a new team member, bringing the total number to 6:

  • Dmitry K.
  • Dmitry P.
  • Mikhail K.
  • Oleg G.
  • Victor K.
  • Vitaly A.

Languages used

  • Javascript (UI)
  • Python (attempts at solvers)

Solution

Our main approach was to build user interface tool to assist the human in manually solving the puzzles. At some it became obvious that automated solvers approach is not fruitfull for us so we went all-in on this UI. Over time it grow in functionality so much and so that we started calling it ICFPC IDE.

UI

Watch video demo

Here is overview of main funtionality:

  • Physics: on/off
    • Enables spring forces on edges that helps the vertices to stabilize
  • Inflate
    • Moves points out of each other. This is helpful in untangling the vertex mess
  • Hole In
    • Applies gravity force at each of the hole vertices. Helps to move the points closer to hole edges.
  • Glue Points
    • Attaches points to fixed position so that they don’t move when physics is enabled
  • Snap Winners
    • Glues points that are located in the hole vertices
  • Snap
    • Snaps points to integer coordiantes
  • Traffic Light
    • Shows red/green depending if solution is good for submittion
  • Save
    • Saves the solution as checkpoint (with glued points) or for submission (clean json).

Running the UI:

cd ui/ && yarn install && yarn dev

then navigate to [http://localhost:3000]

We also built page to access top-problems and their scorers, so that we can prioritize the manual solving of the problems with the highest potential score.

Solvers

We did some attemtps at solvers, but they were not super successfull:

  • Bruteforce solver
    • Doing recursive exhaustive search by trying all possible placements of all vertices. It did solve some number of simple problems, but was quickly choking at bigger problems.
  • Pymonk solver
    • Using physics engine implemented via pymunk library to shrink all vertices into a small area and then release those in the middle of the contour to get some valid solution after edges come to equilibrium. Was suffering from numerical instability.
  • Integral Solver
    • Smarter brute force approach with more heuristics on placement the vertices and limits on recursion depth and time spent in particular branch.

Fun Stuff

One of the highlights was the epic story of solving problem 85:

Somewhere around 2 hours before the end of contest I was manually clicking through that problem until I get to a state:

Basically I needed to solve the left part of the figure which was pretty tricky to do manually:

So I went and quickly implemented small script to do a brute force solution of that (click_solve.py). It was my very suprise when the only solution found was this one:

which doesn’t satisfy edge constraints! Which means this problem couldn’t be solved to full score without bonuses! Among all bonuses available for this problem GLOBALIST from #64 was the most suitable one. I wrote about this in our slack and Vitaly offered to solve the problem 64 taking the needed bonus while I would be clicking through the rest of the problem to have a solution.

We also didn’t have a checker in UI to check the validity of globalist solution (again I had to quickly implement this) nor the support in submitter code (I had to manully update the javascript to include that enabling of the bonus) But after 4 attemtps and ~30 minutes before the end of contest I successfully submitted the solution: