ICFPC-2021: There is only one thing only I am interested in: bent figures
This is part two of the writeup, part one could be found here.
Day 3 (morning of Sunday)
Before we all went to sleep, our position on the leaderboard was 7th(!), but by morning (T+44h) we slipped to 14th
As before, Alex was the first to get up and by the time I had my morning coffee, he added an FPS counter to show the current speed of the solver and did some speedups for the solver code.
When coffee kicked in and brain fog lifted, I mentally went through the experience of manually solving the puzzles on the previous day.
In lots of the big ones figure looked like a big jumble of edge that would have to be "spread" to cover a relatively large hole. For example, here is Problem 125:
Our solver was of no help here, as it was also usually trying to bunch up all the free edges together. To aid in untangling the mess we made it so AWSD would move just the unfrozen nodes around. Now you would be able to "freeze" some of the nodes and move the rest away, rinse and repeat, and hope that tangle would start to look more intelligible and you would be able to "pin" it to the hole corners. It was still pretty hard manual work, but thankfully help was on the way.
At T+47h, Tom checked in implementation of "spring physics", in which edges that are too short would push nodes they are connected to, and edges that are too long would pull, and nodes would move around affected by these forces. "Spring physics" could be toggled on and off, and it greatly simplified the process of manual solving.
Sadly, other teams were going ahead full steam and we kept sliding down. By T+48h we were 19th.
Here is a quick demo of all the tools we had at this point based on problem 106. First I ask the solver to find me a unique edge from the figure that lines up with some hole edge. Them I run brute-force solved that places some neighbouring nodes for me. I freeze them, move the rest of the problem, and invoke several steps of "sprint physics" to untangle the problem a bit:
As you can see, movement is rather sluggish, and "sprint physics is not particularly fast either". Still, this enabled us to submit improved solutions to several problems. Despite that, by T+51h we were 18th, having gained back just one place.
At the end of the lightning round, organizers published the updated spec that added the concept of "bonuses" - special points that, if you were to cover them by the node in your solution, would grant you special powers for some other task. Special powers included: the ability to "break" any edge in half, the ability to have a single aggregate "elasticity budget" for your problem instead of an individual "elasticity limit" per edge or the ability to stretch a single edge without any limits at all.
We made a plot of the graph that showed which problems give bonuses to which other problems and realized that "has bonus for" relationship splits problems into three cycles of different sizes, where 1st problem will give bonuses for 2nd, which will give bonuses for 3rd, and so on, and Nth problem will give bonuses for the 1st.
So not only bonuses were hard to implement in our automatic solvers, but they also required us to temporarily sacrifice some points in a chosen single problem so that we could get the bonus, apply it to the next problem in the cycle and so on until we manage to close the cycle and recoup the points we sacrificed in the very beginning.
This sounded too complicated, plus we had lots of potential for improvement in lots of problems as it were, so we completely ignored the bonuses until the end of the contest (even though our solver is showing bonus nodes on screen).
By T+53h, Tom refactored and sped up "spring physics" and that was a game-changer. We were now able to drag nodes around with their neighbours following them, spring physics simulation was no longer glacial, and this led to a rather quick manual solution, especially for problems where the best score was zero (and so all hole corners were covered by nodes).
In the next video, you can see me solving problem 97 from scratch. I choose this problem because the initial figure is pretty spread out and you can readily see which nodes would go where, but even more, clumped-up problems were easily "spreadable" and then solved the same way.
Unfortunately, despite all this, by T+54.5h we were in 21st place. Evidently, other teams either had better solvers or used bonuses or both.
For the rest of the day, we were mostly solving puzzles with some cosmetic improvements to the solvers and visualizer. In particular, we solved 125 with a score of zero (remember, the lower the score the better):
I think that all of us called it a day by T+62h, give or take. We were in 19th place on the scoreboard, and I went to sleep thinking that surely tomorrow we will wake up to find ourselves in 45th place, or maybe even 100th
Day 3
Despite my fears, the next morning we were 25th, which I initially took to be good news, but then I realized that this probably means that getting extra points is getting harder and harder, and we probably have no chance of getting above 20th place.
My teammates kept solving the problems, and it looked like this is how the rest of the remaining time will be spent.
But on T+70h (two hours until the end of the context) Tom committed "optimizer", which will try to jiggle the points around their current position and will keep doing that as long as it improves the overall score.
All the solutions were pushed through that, and some of them were significantly improved (by 30%+). It seemed that unless we already had an optimal solution, the optimizer was able to squeeze some improvements out of what we had.
Tom also added "repulsion physics", where nodes behaved like the charged particles and repel their neighbours, which helped to untangle clumps that our solver oftentimes produced.
Unfortunately, soon after the optimizer was added scoreboard was frozen (1 hour till the end of the contest). Lots of our solutions were improved after that, but we no longer knew just by how much this improves our standing, which was 23rd at the time of the freeze. Nevertheless, optimization attempts were running all the way until the end, and the last solution was submitted 5 minutes before the deadline.
When organizers published final scoreboard, it became evident that these efforts paid off - we gained two places and finished 21st.
Our scoreboard standing vs time:
Conclusions
I rather enjoyed this ICFPC. The task was short and clean. The server-side infrastructure provided by organizers worked without a hitch (as far as I know). They even provided a very cute visual replay of your solution, complete with judges awarding you dislikes (picture taken from team "codingteam" writeup):
My teammates were amazing, and I secretly hope that next year they might be interested in teaming up together again. OCaml, I felt, was a decent choice as a language, and even the fact that we used graphics primitives library and not a UI toolkit did not hamper us that much.
I am happy with the 21st place we got, and while this is not the best result I personally hard, it is definitely far from the worst :)
See you all next year!
Links and resources
This entry was originally posted at https://dastapov.dreamwidth.org/132836.html. Please comment there using OpenID.
Day 3 (morning of Sunday)
Before we all went to sleep, our position on the leaderboard was 7th(!), but by morning (T+44h) we slipped to 14th
As before, Alex was the first to get up and by the time I had my morning coffee, he added an FPS counter to show the current speed of the solver and did some speedups for the solver code.
When coffee kicked in and brain fog lifted, I mentally went through the experience of manually solving the puzzles on the previous day.
In lots of the big ones figure looked like a big jumble of edge that would have to be "spread" to cover a relatively large hole. For example, here is Problem 125:
Our solver was of no help here, as it was also usually trying to bunch up all the free edges together. To aid in untangling the mess we made it so AWSD would move just the unfrozen nodes around. Now you would be able to "freeze" some of the nodes and move the rest away, rinse and repeat, and hope that tangle would start to look more intelligible and you would be able to "pin" it to the hole corners. It was still pretty hard manual work, but thankfully help was on the way.
At T+47h, Tom checked in implementation of "spring physics", in which edges that are too short would push nodes they are connected to, and edges that are too long would pull, and nodes would move around affected by these forces. "Spring physics" could be toggled on and off, and it greatly simplified the process of manual solving.
Sadly, other teams were going ahead full steam and we kept sliding down. By T+48h we were 19th.
Here is a quick demo of all the tools we had at this point based on problem 106. First I ask the solver to find me a unique edge from the figure that lines up with some hole edge. Them I run brute-force solved that places some neighbouring nodes for me. I freeze them, move the rest of the problem, and invoke several steps of "sprint physics" to untangle the problem a bit:
Click to viewAs you can see, movement is rather sluggish, and "sprint physics is not particularly fast either". Still, this enabled us to submit improved solutions to several problems. Despite that, by T+51h we were 18th, having gained back just one place.
At the end of the lightning round, organizers published the updated spec that added the concept of "bonuses" - special points that, if you were to cover them by the node in your solution, would grant you special powers for some other task. Special powers included: the ability to "break" any edge in half, the ability to have a single aggregate "elasticity budget" for your problem instead of an individual "elasticity limit" per edge or the ability to stretch a single edge without any limits at all.
We made a plot of the graph that showed which problems give bonuses to which other problems and realized that "has bonus for" relationship splits problems into three cycles of different sizes, where 1st problem will give bonuses for 2nd, which will give bonuses for 3rd, and so on, and Nth problem will give bonuses for the 1st.
So not only bonuses were hard to implement in our automatic solvers, but they also required us to temporarily sacrifice some points in a chosen single problem so that we could get the bonus, apply it to the next problem in the cycle and so on until we manage to close the cycle and recoup the points we sacrificed in the very beginning.
This sounded too complicated, plus we had lots of potential for improvement in lots of problems as it were, so we completely ignored the bonuses until the end of the contest (even though our solver is showing bonus nodes on screen).
By T+53h, Tom refactored and sped up "spring physics" and that was a game-changer. We were now able to drag nodes around with their neighbours following them, spring physics simulation was no longer glacial, and this led to a rather quick manual solution, especially for problems where the best score was zero (and so all hole corners were covered by nodes).
In the next video, you can see me solving problem 97 from scratch. I choose this problem because the initial figure is pretty spread out and you can readily see which nodes would go where, but even more, clumped-up problems were easily "spreadable" and then solved the same way.
Unfortunately, despite all this, by T+54.5h we were in 21st place. Evidently, other teams either had better solvers or used bonuses or both.
For the rest of the day, we were mostly solving puzzles with some cosmetic improvements to the solvers and visualizer. In particular, we solved 125 with a score of zero (remember, the lower the score the better):
I think that all of us called it a day by T+62h, give or take. We were in 19th place on the scoreboard, and I went to sleep thinking that surely tomorrow we will wake up to find ourselves in 45th place, or maybe even 100th
Day 3
Despite my fears, the next morning we were 25th, which I initially took to be good news, but then I realized that this probably means that getting extra points is getting harder and harder, and we probably have no chance of getting above 20th place.
My teammates kept solving the problems, and it looked like this is how the rest of the remaining time will be spent.
But on T+70h (two hours until the end of the context) Tom committed "optimizer", which will try to jiggle the points around their current position and will keep doing that as long as it improves the overall score.
All the solutions were pushed through that, and some of them were significantly improved (by 30%+). It seemed that unless we already had an optimal solution, the optimizer was able to squeeze some improvements out of what we had.
Tom also added "repulsion physics", where nodes behaved like the charged particles and repel their neighbours, which helped to untangle clumps that our solver oftentimes produced.
Unfortunately, soon after the optimizer was added scoreboard was frozen (1 hour till the end of the contest). Lots of our solutions were improved after that, but we no longer knew just by how much this improves our standing, which was 23rd at the time of the freeze. Nevertheless, optimization attempts were running all the way until the end, and the last solution was submitted 5 minutes before the deadline.
When organizers published final scoreboard, it became evident that these efforts paid off - we gained two places and finished 21st.
Our scoreboard standing vs time:
Conclusions
I rather enjoyed this ICFPC. The task was short and clean. The server-side infrastructure provided by organizers worked without a hitch (as far as I know). They even provided a very cute visual replay of your solution, complete with judges awarding you dislikes (picture taken from team "codingteam" writeup):
My teammates were amazing, and I secretly hope that next year they might be interested in teaming up together again. OCaml, I felt, was a decent choice as a language, and even the fact that we used graphics primitives library and not a UI toolkit did not hamper us that much.
I am happy with the 21st place we got, and while this is not the best result I personally hard, it is definitely far from the worst :)
See you all next year!
Links and resources
This entry was originally posted at https://dastapov.dreamwidth.org/132836.html. Please comment there using OpenID.