ICFP Contest 2023
As every year since 2012, our team (codingteam) has participated in the annual ICFP Contest.
Just now it is over, and I'm here to tell you about it.
In this post, I'll detail the contest timeline and what our team was doing these days.
The team this year consisted of the following members (in alphabetical order):
Here's the link to our code if you want to take a look.
And let's discuss the detailed contest timeline. I'll note each date in my local time zone, so this may be a bit different (especially along the date boundaries) from the perspective of other team members.
Long Before
Previous years, we were altering between using Haskell and Scala each year. (Though Minoru says that we actually use Haskell every year, but sometimes it is just a weird kind of Haskell.)
This year, I've asked the team to try something new instead of Scala (which has a bit disappointed me with how it goes with Scala 3 — though I am not discounting it completely, yet). And I have convinced folks to try F# for this year, having the advantage of the only permanent team member who extensively uses the language (other years, I am at a disadvantage, so this is only fair! Don't look at me like that!).
And so be it, we've agreed on that.
T-30 (2023-06-10)
Yes, this year I've decided to start the preparations long before the contest itself. So I've started to prepare the project structure, the repository, checking if all the chat rooms work properly, setting up CI (yes, we've got a CI!) and such.
I've also asked the folks to check if .NET environment works well on their computers, and they were slowly answering me all the way until the contest has started.
T-20 (2023-06-20)
gsomix has decided to join us (he doesn't participate each year), which was very welcome since he's well experienced in F# (perhaps even more than myself).
T-16 (2023-06-24) – T+0 (2023-07-07)
One of the problems we periodically have in the contests is the lack of history in our XMPP chat (one of our main channels is still on jabber.ru, and the server has disabled their history completely since the last year). This year, I've decided to do something about that. Since we already use a bot that synchronizes XMPP and Telegram chats, I've decided to also make the bot to preserve the history of all chat messages, and allow to grab it via a simple HTTP API.
I've been making slow progress on that, and finally, just in time for the contest start, I've rolled a version of Emulsion, our bot for chat sync (incidentally, also written in F#!), that now also provides HTML UI to read all the chat log. And folks have been using that during the contest!
F#: connecting people.
T-5 (2023-07-02)
The contest registration has been open, and so I've registered our team on the contest site. But I was a bit confused by the name field: I thought everyone will get their own account, while actually I was supposed to register an account for the team. So I named the account in a wrong way, and was forced to fix it after the start of the contest :(
Akon32 and foxtran mentioned that they will participate as part of our team as well, so here we have our full member list (Portnov and Minoru confirmed their participation earlier, IIRC).
One funny thing we've noticed this day was that two people named Minoru have both joined the official ICFP Contest Discord chat. It is still unknown which of them is our Minoru, and if a secret replacement took place at some moment.
T-2 (2023-07-05)
The contest site was enabled, and we were able to discover test tasks and the scoreboard UI (with no details or clues about the real task, yet).
T+0 (2023-07-07)
The contest has started! The first task specification has been posted, and so I'll outline it here.
We have a rectangular room and a stage inside that room. There are musicians and attendees who want to listen to their music. Each musician plays one particular instrument, and each attendee has tastes for each of the instruments (some tastes may be negative).
Our task is to prepare musician placement on the stage to maximize the total happiness of the attendees. There were 90 tasks in total, each providing a different room and stage layout, attendee placement, instrument set, and for later tasks, certain features such as obstacles blocking the sound.
The attendee happiness is proportional to the taste in particular instrument and inversely proportional to the square of the distance to the musician playing that instrument. Also, musicians block each other: if the direct line from a musician to an attendee comes close to another musician, the attendee will not hear the first musician at all.
All the calculations in the task are done using float arithmetics, which is… an interesting choice, to say the least.
We have almost immediately noticed a field pillars in the task definition, unused at the time. We've started to speculate what it could be, and Minoru has guessed correctly that they will block the sound in the future.
I've started with implementing the HTTP client to do quick upload of our solutions and download the task definitions (this is a nice and useful automation to have at any contest).
Portnov has suggested that we use gradient descent or neural networks to solve the task, while foxtran started writing some crazy formulas and looking at finding minimum for them (I don't understand what he was doing to this day, even though his approach was somewhat resultative).
Interestingly, Portnov also suggested that we write a visualizer for room and allow manual moving the musicians across the stage: something I've actually done, albeit a bit later… after the contest has already ended :(
Portnov has decided to work on the math side of the problem and started plotting a graph for the "happiness function" if I understand correctly, using Python.
Then, I have prepared a foundation for the domain types (such as Problem, Solution and PointD for the good measure, because why not), and a simple function to calculate total score, provided a problem and a solution.
I have also found that a figure like an oval but with straight sides is called a stadium, and a fair part of our calculations during were concentrated around figuring out whether some points lay inside a stadium or not.
foxtran has prepared some "lambda-scoring" program in Python and asked me to convert it to F#, which I did. (The Python program was not working, but meh, it's how Python normally behaves, I wasn't surprised.)
Closer to the evening, Minoru and Akon32 have joined the team, and Minoru left a small enhancement request for the chat log service, which I've timely implemented.
I have also implemented a first version of the "dummy solver" that was just placing all the musicians at the same place (which is even invalid, according to the task specification, but we have to start from something!).
Minoru has improved the dummy solver to place musicians at least correctly, and so we've started getting the first points. We've also found that not every task allows simple rectangular placement, and circle packing is required to even place the musicians properly on some stages.
Even closer to the evening, gsomix joined the team and started working on meta-solver that tries to apply all the other available solvers and choose the best for each solution.
I've switched to preparing a visualizer in Avalonia, and even got first images this day. The image has shown that a big part of the room is not used at all, while all the attendees may concentrate on certain spots.
A bunch of smaller problems have landed onto the task list, and several tasks that were too complex for the contest participants were replaced. These things happen from time to time during contests, this is pretty normal.
Unfortunately, today was the last day we've heard anything from Portnov, and he only got back after the end of the contest. These things happen, and we are definitely not mad at him.
T+1 (2023-07-08)
gsomix has added so-called .meta.json files: this is our own notation to save information on score and solver that was used to get every solution, so that we can use this to compare solutions and figure out which solver was previously used and how to improve the results.
foxtran has started to work on an idea where we calculate the best positions for each musician in isolation, without considering other musicians. While these solutions are, by their nature, incorrect (musicians actively block each other), they allow for pretty quick calculation and thus can be used as a starting point for further optimization.
Minoru has prepared a random solver that just places musicians at random positions, and it was surprisingly good at solving some tasks.
While working on helping foxtran with his ideas, I've suddenly encountered a deadlock in my IDE, and thus had to immediately debug this and gather some diagnostic information to investigate later.
gsomix has been helping foxtran on his other idea related to lambda-solver.
I have added an interface for so-called "partial solutions," the ones where not every musician is placed, to use in our solver that considers the musicians in isolation. Interestingly, the FoxtranV1 solver, as I called it, was the first place when I found a justified use for a singly-linked list: when placing musicians for each particular instruments, I've found it useful to keep the list of musician index in a list, and remove the head of said list each time I need a new musician. This is honestly the first time I found a good use for this data structure.
Minoru found some issues in my code that does stadium calculations and have been struggling to fix them.
Akon32 is working on some Monte-Carlo score estimation thing.
Specification v2 has been published, and it has introduced the pillars field that we've already seen earlier. And they indeed block the sound, similarly to how the musicians do, but each pillar may have a different radius. The pillar placement in the tasks is quite chaotic, but in some cases, there are some hallways decorated with them. Also, several musicians now can amplify each other if placed closely.
gsomix has been trying to use some things from MathNet in our code, but they were incompatible with our types, so we spent some time on discussing possible ways to convert from a PointD[] to a Vector<double>. He wasn't very enthusiastic about my suggestion of converting them using unsafe code, for some reason :(
After I've finished with FoxtranV1, I've found that it's quite slow, and started implementing parallel optimizations for it (Enumerable.Range(0, instrumentCount).AsParallel() was a bad idea, by the way).
But then, after it started working, it turned out to be quite good, actually. And significantly improved our results on almost every task.
foxtran has given up on F# and Python (for whatever reason) and started working on Fortran solver. I've been assisting with providing data in so-called .ini format (which looks similar and yet not the same as the ol' good INI files), because, apparently, it's hard to read a JSON file in Fortran (look, I don't know for sure, but since our Fortran guy founds it hard, I assume it is hard, m'kay?).
Minoru started working on incremental scoring (for the scorer to be able to do fewer calculations if we do small changes in the solution).
We've found some kind of floating arithmetic problem in .NET runtime or in hardware (yet to investigate), which caused the results of score calculation for certain tasks to be different on my and Minoru's computers, using the same input data and code. I've put that aside to investigate later. Maybe that'll be interesting!
I've noted that FoxtranV1 really loves to group musicians near the edges of the scene if there's an attendee close to it. Here's an example.
This is good from the standpoint of the solver, because all these points near the attendee allow the attendee to hear a lot of music. But in real scoring, this is not so good, because the musicians block each other, and so the attendee can't hear all of them. I thought of various ways to fix it, and implemented the simplest one: a "shadow matrix" that gets changed each time a musician is placed, and tries to reflect a small "shadow" said musician would get if the nearest scene edge was lighting the musician. When looking for the best placement, I was also multiplying the results on the corresponding cells of the shadow matrix (and now, looking at it, I think it was used as a "light matrix," not the "shadow" one, but whatever). This optimization did good, so it still until the very end of the contest, improving the existing solutions here and there with some minor variations.
I have also added a concept of "fuel" for the shadows to get their own additional shadows, but that one gets the musicians too sparse across the scene, so, despite my tries to make this work, fuel always stayed equal to 1 in almost all the good solutions.
T+2 (2023-07-09)
foxtran voiced an idea to seek for the attendees who cannot hear anything because of the pillar placement, and filter them out. This is useful, but was never implemented later.
We have added a check for musician closeness in our scoring code (musicians are forbidden to be placed closer than 10 by the task specification).
I have implemented a reader back from Fortran .ini format to upload the solutions, and there were several good ones.
Minoru has convinced me to finally try using a k-d tree to try speeding up our scoring algorithm (because most of the solvers depend on the scoring, and can be made significantly faster or more precise if we get a better scoring algorithm). My idea was simple: instead of checking each musician whether they block each other when considering each attendee, let's first filter the musicians using a k-d tree (for each stadium, spin up a radial search from the stadium center and of the stadium total radius). I've spent quite a lot of time on this idea, but eventually got nothing: the solution was still too slow to consider. I have even tried forking a KdTree to make the radial search lazy (there's no need to consider every musician in the range if the first found bunch already blocks the sound), but even this didn't help us much.
After that, I've put my thought into some other kind of spatial index, and decided to just add a simple grid. It would collect all the musicians in each of the grid cells, and then later, when checking for stadium intersection, we wouldn't need to check every musician, but only those from the grid cells that intersect with the stadium. Since there are much fewer grid cells than musicians, this should be faster. And, after some tuning, it made the scoring about 1.5–2 times faster on typical tasks, which is not bad, but consumed a fair amount of my time. I have even done a couple of drawings in inkscape to figure out certain peculiarities of how this grid is supposed to work.
A hint: there's a really simple way to check if a line (defined by two points) intersects a rectangle. No need for complex vector arithmetic!
gsomix and foxtran were working on lambda and "DerFree" (something about derivatives, I guess?) solvers, though I can't say much about those since I wasn't working on them. Both were pretty heavy, and so we were often running them in background while performing other tasks. The results were pretty good, though! Eventually, we've even used some stuff from AccordMath.
Akon32 is still struggling in Monte-Carlo scoring. Also, he said he doesn't like F# :(
The third and the last version of the specification has been published, this time introducing volume control. It's now possible to control the sound volume of the musicians. For the most part, every solution we had was improved after we've made all the musicians to use max volume (10.0), except the ones that are not liked by the audience (those we've set to 0.0).
gsomix suggested that we can create our own implementation of a k-d tree, and that was an interesting thought, though we've discarded it after some arguing.
We've found a bug in score calculation: it doesn't consider musicians' volumes at all. Everyone thought that someone else has implemented it, but it turns out nobody did. gsomix implemented this, finally.
I've been making additional notes about floating point inconsistency we've found, and determined that it sometimes reproduces for me in tests (tests calculate one value, while same code started via dotnet run calculate it differently). Definitely a very peculiar case that deserves more investigation.
I've tried adding pillars to the Foxtran family of solvers, to no avail: the results became worse after considering the pillars, for some reason.
foxtran described a scheme of local grid refinement, which was implemented in Fortran code.
T+3 (2023-07-10), The Last Day
Over the night, I have been recalculating everything via FoxtranV1 and FoxtranV2 solvers with some minor changes (in particular, grid of odd size 11), to find local improvements, and have uploaded some good results.
Minoru has added a "SUOSI" solver (ShapeUpOrShipOut) that tries to get the best volume for each musician.
gsomix has implemented a swap solver that tries to swap the musicians to find a better configuration for them.
Nothing else of note happened until the end of the contest, but after it has already ended, I've finished the visualizer with minor editing abilities, which helped me find a better solution for at least one task. If it was done earlier, then we'd probably done better, but then — where's the fun in manual problem-solving?
Conclusion
Our final known rating when the contest was close to the end is 51'th place with a score of 97,433,577,912. (This is not the final result, as the final one will be published during the ICFP conference.) Not the best one, but the main point is: did we have fun? I definitely did. Though other folks were struggling with F#, and foxtran was struggling at writing working code at times :)
Update: this year, we won the judges' prize:
Finally, the judges prize was attributed to team Codingteam, whose writeup we really enjoyed reading (and the mix of F# and Fortran in their solution was both surprising and fun to see)
Regarding the process: we need to focus more on incremental work. Since we already have a format to store solutions and their metadata, we need to get more solvers that can rearrange the results of previous solvers, and thus gradually improve the results.
I am thinking of some improvements in how we approach the contest, to make folks have more fun and struggle less in the process, but that will require some more discussion. Next year will be likely Haskell-oriented, and we'll see if we'll implement any of my ideas.
See you next year on ICFP Contest 2024!