matching.go

  1package main
  2
  3import (
  4	"strings"
  5	"unicode"
  6
  7	"golang.org/x/text/unicode/norm"
  8)
  9
 10const (
 11	matchThreshold  = 0.8
 12	lowerThreshold  = 0.3
 13
 14	pointsTitle    = 4
 15	pointsArtist   = 2
 16	pointsAlbum    = 4
 17	pointsPerRound = pointsTitle + pointsArtist + pointsAlbum
 18)
 19
 20func fuzzyScore(guess, answer string) float64 {
 21	a := similarity(normalize(guess), normalize(answer))
 22	b := similarity(normalize(withoutParentheses(guess)), normalize(withoutParentheses(answer)))
 23	return max(a, b)
 24}
 25
 26func scoreFor(similarity float64, weight int) int {
 27	if similarity >= matchThreshold {
 28		return weight
 29	}
 30	if similarity < lowerThreshold {
 31		return 0
 32	}
 33	return int(float64(weight) * similarity + 0.5)
 34}
 35
 36func withoutParentheses(s string) string {
 37	var b strings.Builder
 38	depth := 0
 39	for _, r := range s {
 40		switch r {
 41		case '(':
 42			depth++
 43			b.WriteRune(' ')
 44		case ')':
 45			if depth > 0 {
 46				depth--
 47			}
 48			b.WriteRune(' ')
 49		default:
 50			if depth == 0 {
 51				b.WriteRune(r)
 52			}
 53		}
 54	}
 55	return b.String()
 56}
 57
 58var ligatures = map[rune]string{
 59	'Æ': "ae", 'æ': "ae",
 60	'Œ': "oe", 'œ': "oe",
 61}
 62
 63func normalize(s string) string {
 64	s = strings.ReplaceAll(s, "&", "and")
 65	s = norm.NFKD.String(strings.ToLower(s))
 66	var b strings.Builder
 67	for _, r := range s {
 68		if l, ok := ligatures[r]; ok {
 69			b.WriteString(l)
 70			continue
 71		}
 72		if unicode.IsLetter(r) || unicode.IsNumber(r) {
 73			b.WriteRune(r)
 74		}
 75	}
 76	return b.String()
 77}
 78
 79func similarity(a, b string) float64 {
 80	x, y := []rune(a), []rune(b)
 81	if len(x) == 0 || len(y) == 0 {
 82		return 0
 83	}
 84	row := make([]int, len(y)+1)
 85	for j := range row {
 86		row[j] = j
 87	}
 88	for i, r := range x {
 89		previous := row[0]
 90		row[0] = i + 1
 91		for j, s := range y {
 92			cost := 0
 93			if r != s {
 94				cost = 1
 95			}
 96			old := row[j+1]
 97			row[j+1] = min(row[j]+1, old+1, previous+cost)
 98			previous = old
 99		}
100	}
101	return 1 - float64(row[len(y)])/float64(max(len(x), len(y)))
102}