![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovGather round and settle down for the next instalment of the ICFPC write-ups.
ICFPC stands for ICFP Contest (and ICFP, in turn, stands for International Conference on Functional Programming), and I have been participating in them since early 2000s and writing up my adventures here. My most famous writeup (in Russian) about the best ICFPC so far -- 2006 -- could be found here.
TL;DR: This year, our team name was "Folding at home", there were three of us + my wife who solved a bunch of puzzles manually (but did not write code). We wrote an interactive computer-aided solver in OCaml and finished 36th in the Lightning Round and 21st in the Main Round. I liked this year's contest more than 2020 (but less than 2006 :). Puzzle was somewhat similar to the Origami puzzle from ICFPC-2016.
And if you want to know more than just TLDR, prepare for the wall of text :)
Day one
This year ICFPC started at 13:00 in my time zone. I was working but took a moment to check the contest website and saw that a)there is a nice, neat and rather small spec and b)there is a scoreboard! Excitement!
However, only at 18:30 I was able to sit down and read the spec.
It seems that all past ICFPCs could be roughly divided into two piles: "puzzle-solving" and "game bot writing". Last year was (mostly) "game bot writing", so it was only fitting that this year would be "puzzle-solving", which I secretly liked.
This year's puzzle went like this: you are given a planar figure that is drawn on the grid with integer coordinates. The figure consists of vertices lying on the grid intersections, and edges that connect some of the vertices.
You are also given a polygonal hole drawn on the same grid. Your task is to rearrange the figure so that it will fit inside the hole without any parts sticking out. To this end, you can rearrange vertices of the figure, making sure that edges that connect them roughly keep their length. I say "roughly" because edges have some "elasticity", and could be shrunk and stretched a little bit.
This is what has been the inspiration for the task:
Here is red figure drawn over the black hole:
And here is the same figure deformed so that it would fit into the hole:
Have you ever played "World of Goo"? Then you would have a really good intuition for how the figure would behave. If there are triangles or triangle meshes, they would be "rigid" and keep their shape. Any other part of the figure that forms a polygon with more than 3 sides would be freely twistable and deformable (provided that edge lengths allow it).
Obviously, for a sufficiently pliable figure, there would be many ways to fold it into the hole, so there is a scoring function that incentivizes you to cover all the corners of the hole (rather than, say, scrunch up your figure in a "ball" and set it in the middle of the hole).
I finished reading the spec (at T+6h) and got in touch with the rest of my team. Turned out that Tom is not feeling well, but will hopefully join us tomorrow. Alex though had been busy and wrote a visualizer that was able to show us both "figure" and "hole".
I don't remember who was the first to propose extending the visualizer into an interactive editor, but we both thought that this sounds like a good idea. We decided to make a module called "Pose" that would serve as the state that the interactive editor modifies. After a brief discussion of the API, I started to write Pose and Alex started to integrate it into the visualizer.
After several rounds of bug-fixing and API extension, we got something working around the T+8h mark. The editor would show you the figure and the hole, and you would be able to drag nodes around with the editor restricting your movements when you are trying to violate the elasticity limits of the edges.
We quickly realized that enforcement of the elasticity limits gets in the way: when a figure has lots of triangles, you will not be able to quickly move them about, instead, you would be forced to move each vertex one by one in small increments, which is very slow and infuriating.
So instead we allowed the user to move nodes around without any restrictions, but edges that violate elasticity limits would be coloured red, the redder the colour the more stretched (or compressed) is the edge. That was way better than before, and at T+9h we added the ability to save solutions to the file and tried to post them. At T+9.5h we scored our first points!
This is how our solved looked like (on problem 13):
For the next couple of hours, until T+12h, we have solved a bunch of problems by hand (which, surprisingly, got us to the 27th place) and discussed the next steps. One of the ideas we had was to exploit the fact that the figure has to be drawn of the grid with integer coordinates. There is only a limited number of ways to draw a segment of length L if the coordinates of its start and end have to be integer numbers. Alex extended the editor with the ability to draw circles that show you just how far you can stretch the edge and started to implement the beginnings of a solver based on this idea, and I kept solving the problems manually.
By T+13h I realized that a whole host of problems could be solved easier if you could shift the figure around and then "tuck in" the parts that stick out. The ability to move the figure around with "AWSD" was added and I solved a bunch of other problems this way. We moved to 20th place!
Here is how our (still fully manual) solver looked like at T+13h on problem 72:
At this point, I went to sleep, but Alex worked on solver up to T+15.5h. The idea was to allow the user to "freeze" the positions of a bunch of nodes, and then try and place all the remaining nodes in a way that does not violate elasticity constraints and does not put parts of the figure outside of the hole boundaries. To speed the search up, the solver would start with the nodes that have as many connections to "frozen" nodes as possible and will utilize the knowledge of the potential "integer" endpoint for each edge to limit the search even further.
We went to sleep, but other teams sadly did not. While we slept, we slid down to 39th place on the leaderboard.
Day 2
At T+20.5h, Alex was awake again and finished the solver that would perform the placement of the nodes without checking intersections with the hole. This would not allow us to solve problems without manual intervention yet. But we were able to display all the additional pieces of data precomputed for the solver, in particular - all the placement points for the node you are currently moving that will not violate the elasticity constraints of the edges connected to it.
This allowed us to manually solve a bunch of problems that had fiddly node placement, like problem 27:
By T+22 I was also awake and trying to speed up computations of "integer placements" for all edges. Our third teammate, Tom, also joined us and started to work on geometry primitives so that we would be able to implement "hole intersection" checks and make our solver respect hole boundaries.
By T+23.5 we had rudimentary geometry checking working, and added undo to the editor. Our position on the leaderboard was 42nd, and it was clear that there is no need to rush trying to solve more problems by the end of the Lightning Round.
By T+24.5h, we were on a roll. Our editor got a bunch of features: 1)ability to "snap" currently moved node to the closes hole corner, 2)solver that respects hole boundaries (with some minor issues), 3)ability to rotate figure by 90 degrees and reflect it relative to the line going through the centre of the hole and 4)ability to see solver progress in realtime and abort it, keeping current progress.
Features demonstrated on problem 1 (as you can see, solver avoids corners and edges of the hole):
Despite all the current flaws of the solver, we rose back to 29th place and kept slowly climbing. Alex and Tom were fixing the geometry bugs, I was solving problems for which we had no solutions yet and adding small bits to the editor (like a display of the score of the current solution state).
By T+26h I started to write the code that would try to pair edges of the hole with edges of the figure that could be perfectly placed to cover them. Geometry bugs were fixed, and solver improvements started to go in. We've changed the order in which the solver considers potential node placements to favour the spots on or near the yet-uncovered hole corners.
We also wrote the shell script which would wait for you to close the editor, and after checking that the new saved solution is better than the old one will submit it and commit it into the version control.
By T+28h the code that matches hole edges to figure edges was complete. Solved was also sped up in several ways. We went over a bunch of problems with bad solutions and improved them. By T+29.5h we were 25th.
The scoring model in the contest was giving the "perfect solution score" to each problem based on the number of nodes and edges in the figure and the number of corners in the hole. This perfect score was only available to those who managed to cover all the corners of the hole with nodes of the figure. Any other solution was penalized, proportional to the distance between uncovered hole corners and figure nodes nearest to them.
Organizers were publishing the score of the best solution found by all participants, per problem. If your solution had worse than the best, you received a percentage-based penalty. If your solution was 2x worse, you got about 75% of the points. If your solution was 10x worse, you were getting less than 10% of the points. It was therefore imperative to try and solve problems for the perfect score.
For a bunch of problems, the perfect score was zero, which mean that solution managed to cover all hole corners. We added a bunch of "quality of life" improvements to the editor (visual indicators for hole corners, ability to freeze all nodes, ability to zoom the problem and pan it around etc) and kept pushing for the perfect solutions on all medium and small problems.
This took a while, but by T+38h we were 7th!
This is how our solver looked at this stage, on problem 78:
To be continued in part two.
ICFPC stands for ICFP Contest (and ICFP, in turn, stands for International Conference on Functional Programming), and I have been participating in them since early 2000s and writing up my adventures here. My most famous writeup (in Russian) about the best ICFPC so far -- 2006 -- could be found here.
TL;DR: This year, our team name was "Folding at home", there were three of us + my wife who solved a bunch of puzzles manually (but did not write code). We wrote an interactive computer-aided solver in OCaml and finished 36th in the Lightning Round and 21st in the Main Round. I liked this year's contest more than 2020 (but less than 2006 :). Puzzle was somewhat similar to the Origami puzzle from ICFPC-2016.
And if you want to know more than just TLDR, prepare for the wall of text :)
Day one
This year ICFPC started at 13:00 in my time zone. I was working but took a moment to check the contest website and saw that a)there is a nice, neat and rather small spec and b)there is a scoreboard! Excitement!
However, only at 18:30 I was able to sit down and read the spec.
It seems that all past ICFPCs could be roughly divided into two piles: "puzzle-solving" and "game bot writing". Last year was (mostly) "game bot writing", so it was only fitting that this year would be "puzzle-solving", which I secretly liked.
This year's puzzle went like this: you are given a planar figure that is drawn on the grid with integer coordinates. The figure consists of vertices lying on the grid intersections, and edges that connect some of the vertices.
You are also given a polygonal hole drawn on the same grid. Your task is to rearrange the figure so that it will fit inside the hole without any parts sticking out. To this end, you can rearrange vertices of the figure, making sure that edges that connect them roughly keep their length. I say "roughly" because edges have some "elasticity", and could be shrunk and stretched a little bit.
This is what has been the inspiration for the task:
Here is red figure drawn over the black hole:
And here is the same figure deformed so that it would fit into the hole:
Have you ever played "World of Goo"? Then you would have a really good intuition for how the figure would behave. If there are triangles or triangle meshes, they would be "rigid" and keep their shape. Any other part of the figure that forms a polygon with more than 3 sides would be freely twistable and deformable (provided that edge lengths allow it).
Obviously, for a sufficiently pliable figure, there would be many ways to fold it into the hole, so there is a scoring function that incentivizes you to cover all the corners of the hole (rather than, say, scrunch up your figure in a "ball" and set it in the middle of the hole).
I finished reading the spec (at T+6h) and got in touch with the rest of my team. Turned out that Tom is not feeling well, but will hopefully join us tomorrow. Alex though had been busy and wrote a visualizer that was able to show us both "figure" and "hole".
I don't remember who was the first to propose extending the visualizer into an interactive editor, but we both thought that this sounds like a good idea. We decided to make a module called "Pose" that would serve as the state that the interactive editor modifies. After a brief discussion of the API, I started to write Pose and Alex started to integrate it into the visualizer.
After several rounds of bug-fixing and API extension, we got something working around the T+8h mark. The editor would show you the figure and the hole, and you would be able to drag nodes around with the editor restricting your movements when you are trying to violate the elasticity limits of the edges.
We quickly realized that enforcement of the elasticity limits gets in the way: when a figure has lots of triangles, you will not be able to quickly move them about, instead, you would be forced to move each vertex one by one in small increments, which is very slow and infuriating.
So instead we allowed the user to move nodes around without any restrictions, but edges that violate elasticity limits would be coloured red, the redder the colour the more stretched (or compressed) is the edge. That was way better than before, and at T+9h we added the ability to save solutions to the file and tried to post them. At T+9.5h we scored our first points!
This is how our solved looked like (on problem 13):
For the next couple of hours, until T+12h, we have solved a bunch of problems by hand (which, surprisingly, got us to the 27th place) and discussed the next steps. One of the ideas we had was to exploit the fact that the figure has to be drawn of the grid with integer coordinates. There is only a limited number of ways to draw a segment of length L if the coordinates of its start and end have to be integer numbers. Alex extended the editor with the ability to draw circles that show you just how far you can stretch the edge and started to implement the beginnings of a solver based on this idea, and I kept solving the problems manually.
By T+13h I realized that a whole host of problems could be solved easier if you could shift the figure around and then "tuck in" the parts that stick out. The ability to move the figure around with "AWSD" was added and I solved a bunch of other problems this way. We moved to 20th place!
Here is how our (still fully manual) solver looked like at T+13h on problem 72:
At this point, I went to sleep, but Alex worked on solver up to T+15.5h. The idea was to allow the user to "freeze" the positions of a bunch of nodes, and then try and place all the remaining nodes in a way that does not violate elasticity constraints and does not put parts of the figure outside of the hole boundaries. To speed the search up, the solver would start with the nodes that have as many connections to "frozen" nodes as possible and will utilize the knowledge of the potential "integer" endpoint for each edge to limit the search even further.
We went to sleep, but other teams sadly did not. While we slept, we slid down to 39th place on the leaderboard.
Day 2
At T+20.5h, Alex was awake again and finished the solver that would perform the placement of the nodes without checking intersections with the hole. This would not allow us to solve problems without manual intervention yet. But we were able to display all the additional pieces of data precomputed for the solver, in particular - all the placement points for the node you are currently moving that will not violate the elasticity constraints of the edges connected to it.
This allowed us to manually solve a bunch of problems that had fiddly node placement, like problem 27:
By T+22 I was also awake and trying to speed up computations of "integer placements" for all edges. Our third teammate, Tom, also joined us and started to work on geometry primitives so that we would be able to implement "hole intersection" checks and make our solver respect hole boundaries.
By T+23.5 we had rudimentary geometry checking working, and added undo to the editor. Our position on the leaderboard was 42nd, and it was clear that there is no need to rush trying to solve more problems by the end of the Lightning Round.
By T+24.5h, we were on a roll. Our editor got a bunch of features: 1)ability to "snap" currently moved node to the closes hole corner, 2)solver that respects hole boundaries (with some minor issues), 3)ability to rotate figure by 90 degrees and reflect it relative to the line going through the centre of the hole and 4)ability to see solver progress in realtime and abort it, keeping current progress.
Features demonstrated on problem 1 (as you can see, solver avoids corners and edges of the hole):
Despite all the current flaws of the solver, we rose back to 29th place and kept slowly climbing. Alex and Tom were fixing the geometry bugs, I was solving problems for which we had no solutions yet and adding small bits to the editor (like a display of the score of the current solution state).
By T+26h I started to write the code that would try to pair edges of the hole with edges of the figure that could be perfectly placed to cover them. Geometry bugs were fixed, and solver improvements started to go in. We've changed the order in which the solver considers potential node placements to favour the spots on or near the yet-uncovered hole corners.
We also wrote the shell script which would wait for you to close the editor, and after checking that the new saved solution is better than the old one will submit it and commit it into the version control.
By T+28h the code that matches hole edges to figure edges was complete. Solved was also sped up in several ways. We went over a bunch of problems with bad solutions and improved them. By T+29.5h we were 25th.
The scoring model in the contest was giving the "perfect solution score" to each problem based on the number of nodes and edges in the figure and the number of corners in the hole. This perfect score was only available to those who managed to cover all the corners of the hole with nodes of the figure. Any other solution was penalized, proportional to the distance between uncovered hole corners and figure nodes nearest to them.
Organizers were publishing the score of the best solution found by all participants, per problem. If your solution had worse than the best, you received a percentage-based penalty. If your solution was 2x worse, you got about 75% of the points. If your solution was 10x worse, you were getting less than 10% of the points. It was therefore imperative to try and solve problems for the perfect score.
For a bunch of problems, the perfect score was zero, which mean that solution managed to cover all hole corners. We added a bunch of "quality of life" improvements to the editor (visual indicators for hole corners, ability to freeze all nodes, ability to zoom the problem and pan it around etc) and kept pushing for the perfect solutions on all medium and small problems.
This took a while, but by T+38h we were 7th!
This is how our solver looked at this stage, on problem 78:
To be continued in part two.