Ruin my Marathon Charts
Ruin my Marathon is a fundraising app that my son, Asher, is making. I contributed these components.
The idea is that sponsors bid for time slots in a runner's marathon and select songs for them to listen to. It has Spotify integration for creating the playlist and so on.
Asher was having a little difficulty with the Difficulty Curve feature, so I offered to help.
The Difficulty Curve is configured by the runner and represents their anticipated pain level while running the marathon. Sponsors who pay the most per minute for their song get the most difficult slots. Sponsors also see a non-editable curve showing their song's placement.
I created the chart component as a library. What you see below is a demo component that imports the library. Feel free to play with the controls. The algorithm is described below the fold.
The Algorithm
We want to place songs along a timeline and ensure that higher-value songs get placed at peaks of difficulty but with no overlaps. The solution is implemented as a React hook and uses a gap-tracking system.
First, we sort all songs by their per-minute value to make sure that highest-paying songs get first choice of placement.
The algorithm maintains a list of available gaps in the timeline where songs can be placed. Initially, there's one gap spanning the entire marathon. As we place songs, we update the list of gaps. A new song in the middle of a gap will result in 2 new gaps.
For each song, the algorithm scans the available gaps and finds the position where the difficulty value is highest. To do this, it breaks the gaps up into spans so that spans do not contain control points. Therefore, the value anywhere along a span can be calculated by interpolating between the boundaries of the span. The image below illustrates this.
Songs have a duration, so we have to determine the highest value at the center of the song, provided the start and end do not conflict with existing songs.
After placing each song, the algorithm reconfigures the available gaps to account for the newly occupied space.
Silence
After all songs are placed, there may be songless gaps at the lowest points of the curve. There are options to handle these silent gaps. We can either evenly distribute silence between songs or stack all songs from the beginning with no silent gaps. This may ultimately depend on how controllable Spotify playlists are.