Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Source code:
source.zip
Solutions:
solutions.zip
The Frictionless Bananas had only one team member this year. This page describes my 2023 ICFP Programming Contest entry.
This year’s task was an optimization problem with a theme based on a musical performance.
A group of musicians is performing on a rectangular stage inside a larger rectangular room. Audience members are at fixed locations within the room. The task is to arrange the musicians on the stage to maximize the audience’s enjoyment.
Each musician plays a particular instrument, and each audience member has different tastes for different instruments. Musicians should be placed closer to audience members who enjoy their respective instruments. Sound from a musician is blocked from reaching an audience member if another musician is in the way. Since an audience member’s taste for an instrument may be negative, such blocking can be useful.
After the lightning round, several specification changes were introduced:
My basic approach was simulated annealing. I start with a random solution and repeatedly make random changes, evaluating the impact of each change on the score to decide whether to keep or discard the change. If the new score is better or the same, the change is kept. If the new score is worse, the change is kept with some probability, which decreases over time. The probability is adjusted based on the magnitude of the score decrease, so that changes which decrease the score by larger amounts are less likely to be kept.
In most cases, a change consists of moving one musician to a new location. The location is generated by randomly choosing a distance and a direction to move, with the distance chosen from a distribution that favors small changes but sometimes also makes large changes.
About 10% of the time, I instead swap the locations of two musicians who play different instruments. Swapping was intended to handle situations where it is important for a musician to be at a location in order to block sound, but it would be better to use a different musician.
A major difficulty in this contest was calculating scores efficiently. It even seemed to cause the organizers some trouble.
The scoring function includes terms for each of A attendees impacted by each of M musicians, which requires O(A*M) time to compute. However, the sound between each pair of attendee and musician can potentially be blocked by any of M musicians—and after the lightning round, any of P pillars. A straightforward approach would require O(A*M*(M+P)) time to check for obstructions.
For simulated annealing, I needed to repeatedly calculate the score of a solution as changes are made. I developed data structures to incrementally update the score when moving a single musician. Swaps are handled as two separate moves.
When a musician moves, it is necessary to recompute the impact of that musician on all attendees, which takes O(A*(M+P)) time to check for obstruction. It is also necessary to check whether that musician’s old or new location blocks the sound between any other musician and any attendee, which takes O(A*M) time.
After the lighting round, a musician’s impact on attendees depends on the “closeness” to other musicians playing the same instrument. If there are K musicians playing the same instrument, recomputing the closeness factors for each of them takes O(K^2) time. (In theory, it can done incrementally in O(K) time, but I was worried about accumulating floating point errors.) Recomputing the impact of each of those musicians on all attendees takes O(K*A) time.
It is not strictly necessary to check every triple of <musician, attendee, obstruction> to determine sound blocking. Given two of the three, a spatial data structure can be used to find candidates for the third.
Specifically, the approach I used was to build a k-d tree of attendee locations. Given a musician and an obstruction, I use the k-d tree to look up all attendees that cannot hear the musician due to the obstruction.
For a given musician and obstruction, I first find the tangent lines from the musician’s point to the obstruction’s circle. The region where attendees cannot hear the musician is bounded by the two tangent lines and the line connecting the two tangent points.
In the k-d tree, each node represents a set of attendees that lie within a rectangular region. While traversing the k-d tree, once we find a rectangular region that is entirely outside one of the three lines, we can stop searching that portion of the tree.
After reading some post-contest discussion, I think a k-d tree or other generic spatial data structure was not the best approach. A simpler and more efficient approach would be for each musician to store a list of attendees sorted by angle, which can be used to quickly find all attendees that are within the range of angles blocked by an obstruction. I tried that after the contest and it was about three times faster.
I ran my solver on 16 cores across two reasonably powerful desktop computers. I ran most problems for one hour, though towards the end of the contest I ran some of the important problems for up to four hours.
I tried to determine which problems were likely to benefit from more running time in a few ways:
When the scoreboard was frozen two hours before the end of the contest, I was in 10th place. I continued to submit improvements, but I’m sure others did as well.
This was an interesting task and a well-run contest. Thank you to the organizers for all the hard work!
The task and the techniques needed to solve it reminded me a lot of Al Zimmermann’s Programming Contests (AZsPCs). Many of those contests can be solved via a combination of simulated annealing and efficient incremental score updates. It was through those contests that I first learned about simulated annealing. Anyone who liked this task may also enjoy AZsPCs.
Here are some links I collected:
See also this GitHub search for icfpc2023.