sonda/internal/mixes/pick.go
tgiachi 94dbf57544 feat(mixes): playlists made for a listener, by listening and by genre
GET /mixes lists the mixes a listener has, GET /mixes/{id}?variant= gives one with its
songs, and POST /mixes/{id}/playlist keeps one as a playlist of their own.

- Genre mixes: one for each genre with at least 30 songs by 4 artists, the genres the
  listener plays most first. Spellings that differ by case or punctuation are one
  genre (jazz+funk, jazz-funk); other and unknown are not genres.
- Made for the listener: Your favourites, Rediscover (liked artists not played for a
  month; both need history) and New to you (songs never played).
- A mix has up to 50 songs, at most 3 by one artist, never two of an artist in a row,
  picked by weighted chance (artist preference, never-played, less if played lately;
  skipped lately and avoided artists are out). The seed is user, mix, day and variant,
  so a mix is steady for a day and another is one variant away.
- Worked out when asked, from the listener's own history and the genre tags; nothing is
  stored and nothing leaves the server.

internal/mixes holds the selection and the service, internal/storage/mixes.go the
queries (SQLite and PostgreSQL). Spec, contract test, README and web types follow;
the web app comes separately.

Closes #95
2026-11-12 17:25:49 +01:00

123 lines
3.6 KiB
Go

package mixes
import (
"math"
"math/rand/v2"
"sort"
)
// Candidate is a song that may go into a mix. Weight says how much it is wanted: twice the
// weight is twice the chance. A weight of 0 or less keeps the song out.
type Candidate struct {
TrackID int64
ArtistID int64 // 0 when the song has no artist; such songs are all of the same "artist"
Weight float64
}
// Pick chooses up to size songs from the candidates and puts them in order.
//
// The choice is by weighted chance without repeats (a song of weight w gets the key ln(u)/w for
// a random u, and the largest keys win). At most perArtist songs of one artist are taken, unless
// the candidates are by so few artists that the size could not be reached, and then the limit is
// raised just enough. Two songs of the same artist are not put next to each other when the order
// allows it.
//
// The same seed gives the same mix, which is what keeps a mix steady for a day.
func Pick(cands []Candidate, size, perArtist int, seed uint64) []int64 {
if size <= 0 {
return nil
}
rng := rand.New(rand.NewPCG(seed, seed^0x9e3779b97f4a7c15))
type keyed struct {
Candidate
key float64
}
pool := make([]keyed, 0, len(cands))
artists := map[int64]bool{}
// The pool is walked in a fixed order, so that a seed means one thing.
sorted := append([]Candidate(nil), cands...)
sort.Slice(sorted, func(i, j int) bool { return sorted[i].TrackID < sorted[j].TrackID })
for _, c := range sorted {
if c.Weight <= 0 || math.IsNaN(c.Weight) || math.IsInf(c.Weight, 0) {
continue
}
u := 1 - rng.Float64() // in (0, 1]
pool = append(pool, keyed{c, math.Log(u) / c.Weight})
artists[c.ArtistID] = true
}
sort.SliceStable(pool, func(i, j int) bool { return pool[i].key > pool[j].key })
limit := perArtist
if limit < 1 {
limit = 1
}
if need := (size + len(artists) - 1) / max(len(artists), 1); need > limit {
limit = need
}
taken := map[int64]int{}
picked := make([]Candidate, 0, size)
for _, c := range pool {
if len(picked) == size {
break
}
if taken[c.ArtistID] >= limit {
continue
}
taken[c.ArtistID]++
picked = append(picked, c.Candidate)
}
rng.Shuffle(len(picked), func(i, j int) { picked[i], picked[j] = picked[j], picked[i] })
picked = spread(picked, rng)
out := make([]int64, len(picked))
for i, c := range picked {
out[i] = c.TrackID
}
return out
}
// spread puts the songs in an order where two of the same artist are not neighbours, as far as
// the songs allow it: each place takes a song of the artist with most songs left, other than the
// one that just played (ties by chance). The songs of an artist keep the order they came in.
func spread(s []Candidate, rng *rand.Rand) []Candidate {
left := map[int64][]Candidate{}
var artists []int64
for _, c := range s {
if _, ok := left[c.ArtistID]; !ok {
artists = append(artists, c.ArtistID)
}
left[c.ArtistID] = append(left[c.ArtistID], c)
}
sort.Slice(artists, func(i, j int) bool { return artists[i] < artists[j] }) // map order must not matter
out := make([]Candidate, 0, len(s))
var last int64
haveLast := false
for len(out) < len(s) {
best := -1
var tied []int64
for _, a := range artists {
n := len(left[a])
if n == 0 || (haveLast && a == last) {
continue
}
switch {
case n > best:
best, tied = n, []int64{a}
case n == best:
tied = append(tied, a)
}
}
var pick int64
if len(tied) > 0 {
pick = tied[rng.IntN(len(tied))]
} else {
pick = last // only the artist that just played has songs left
}
out = append(out, left[pick][0])
left[pick] = left[pick][1:]
last, haveLast = pick, true
}
return out
}