swiss.go

package swiss

import (
	"log"
	"math"
	"sort"
)

type Scorer interface {
	ID() int
	Score() int
	Rating() int
	PastMatches() []int
	HasPairedDown() bool
}

type ByScore []Scorer

func (l ByScore) Len() int      { return len(l) }
func (l ByScore) Swap(i, j int) { l[i], l[j] = l[j], l[i] }

// Less puts higher scores at lower index
func (l ByScore) Less(i, j int) bool {
	iScore := l[i].Score()
	jScore := l[j].Score()
	if iScore == jScore {
		iScore = l[i].Rating()
		jScore = l[j].Rating()
	}
	return iScore > jScore
}

func max(ints ...int) int {
	max := math.MinInt32
	for _, i := range ints {
		if i > max {
			max = i
		}
	}
	return max
}

func SteamrollerPairs(scorers []Scorer) [][]Scorer {
	sort.Sort(ByScore(scorers))

	pairs := [][]Scorer{}
	if len(scorers)%2 != 0 {
		// Give the highest score the bye (eventually this will be configurable somehow)
		pairs = append(pairs, []Scorer{scorers[0]})
		scorers = scorers[1:]
	}

	remaining := len(scorers)

	// this is a safety valve to catch degenerate tournaments where pairDown protection is preventing matching. If
	// we are at a rematchThreshold of > the longest list of past matches, we are out of possible matches without
	// pairing down a second time. This prevents an infinite pairing sequence.
	longestPastMatches := 0
	for remaining > 0 {
		if remaining == 1 {
			pairs = append(pairs, scorers)
			break
		}

		pair := scorers[0:2]
		longestPastMatches = max(len(pair[0].PastMatches()), len(pair[1].PastMatches()))

		scorers = scorers[2:]
		rejected := []Scorer{}

		// Number of rematches acceptible when matching. Start at 0, but increment if no matches are found until
		// all players are matched.
		rematchThreshold := 0
		allowPairDown := false
		for !pairShouldMatch(pair, rematchThreshold, allowPairDown) {
			rejected = append(rejected, pair[1])
			if len(scorers) == 0 {
				// pair[0] should always be the higher score
				if !allowPairDown && !pair[0].HasPairedDown() {
					allowPairDown = true
				} else {
					rematchThreshold++
					if rematchThreshold > longestPastMatches {
						// we will have seen all possible Scorers at this point, so know what
						// the longest match list is. If the considered rematchThreshold is >
						// the maximum number of games played by any player, we're in a
						// degenerate state. In this case, there's no pairs possible without
						// additional pairdown. In reality, this will almost certainly never
						// happen unless someone is fucking with the scoring, so just allow the
						// second pairdown and avoid the infinite loop.
						allowPairDown = true
					}
				}

				if len(rejected) == 0 {
					log.Println("Error: There are no matches left %#v, and" +
						" the bye has already been calculated. This" +
						" should not happen.")
					return [][]Scorer{}
				}
				// reset the rejected list and try again with +1 rematch accepted.
				scorers = rejected
				rejected = []Scorer{}
			}
			pair = []Scorer{pair[0], scorers[0]}
			longestPastMatches = max(len(pair[0].PastMatches()), len(pair[1].PastMatches()), longestPastMatches)
			scorers = scorers[1:]
		}
		pairs = append(pairs, pair)

		scorers = append(rejected, scorers...)
		remaining = len(scorers)
	}
	return pairs
}

func pairShouldMatch(pair []Scorer, rematchThreshold int, allowPairDown bool) bool {
	if len(pair) != 2 {
		log.Printf("Error: tried to match %d players. Expected 2.", len(pair))
		return true
	}
	if pair[0].Score() != pair[1].Score() && !allowPairDown {
		return false
	}

	aMatches := 0
	for _, id := range pair[0].PastMatches() {
		if pair[1].ID() == id {
			aMatches++
		}
	}

	bMatches := 0
	// In a sane world, this second loop would not be needed, but it's pretty cheap to check both sides, so why not.
	for _, id := range pair[1].PastMatches() {
		if pair[0].ID() == id {
			bMatches++
		}
	}

	// Useful for tracing, so I'ma leave it here.
	// if aMatches <= rematchThreshold && bMatches <= rematchThreshold {
	// 	fmt.Printf("Accepting (threshold %d, pairdown: %t) : %v\n", rematchThreshold, allowPairDown, pair)
	// } else {
	// 	fmt.Printf("Rejecting (threshold %d, pairdown: %t) : %v\n", rematchThreshold, allowPairDown, pair)
	// }

	return aMatches <= rematchThreshold && bMatches <= rematchThreshold
}

swiss_test.go

package swiss

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/assert"
)

type Player struct {
	id            int
	Wins          int
	Losses        int
	Ties          int
	pastMatches   []int
	hasPairedDown bool
}

func (p *Player) ID() int {
	return p.id
}

func (p *Player) Score() int {
	return (p.Wins * 3) + (p.Losses * 0) + (p.Ties * 1)
}

func (p *Player) Rating() int {
	// Favor players with lower IDs cause idk.
	return 1200 - p.ID()
}

func (p *Player) PastMatches() []int {
	return p.pastMatches
}

func (p *Player) HasPairedDown() bool {
	return p.hasPairedDown
}

func (p *Player) String() string {
	return fmt.Sprintf("P%d[%d/%d/%d]", p.ID(), p.Wins, p.Losses, p.Ties)
}

func TestEmptySet(t *testing.T) {
	pairs := SteamrollerPairs([]Scorer{})
	assert.Equal(t, 0, len(pairs))
}

func TestBalancedPair(t *testing.T) {
	players := []Scorer{
		&Player{id: 1},
		&Player{id: 2},
		&Player{id: 3},
		&Player{id: 4},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
}

func TestPairWithBye(t *testing.T) {
	players := []Scorer{
		&Player{id: 1},
		&Player{id: 2},
		&Player{id: 3},
		&Player{id: 4},
		&Player{id: 5},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 3, len(pairs))
	for _, pair := range pairs {
		if pair[0].(*Player).id == 1 {
			assert.Equal(t, 1, len(pair))
		} else {
			assert.Equal(t, 2, len(pair))
		}
	}
}

func TestPairsWithScore(t *testing.T) {
	players := []Scorer{
		&Player{id: 5, Wins: 1},
		&Player{id: 2, Wins: 3},
		&Player{id: 3, Wins: 2},
		&Player{id: 7, Wins: 0},
		&Player{id: 4, Wins: 2},
		&Player{id: 8, Wins: 0},
		&Player{id: 6, Wins: 1},
		&Player{id: 1, Wins: 3},
		&Player{id: 9, Wins: 4},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 5, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 1:
			assert.Equal(t, 2, pair[1].(*Player).id, "Expected pair: 1,2")
		case 3:
			assert.Equal(t, 4, pair[1].(*Player).id, "Expected pair: 3,4")
		case 5:
			assert.Equal(t, 6, pair[1].(*Player).id, "Expected pair: 5,6")
		case 7:
			assert.Equal(t, 8, pair[1].(*Player).id, "Expected pair: 7,8")
		case 9:
			assert.Equal(t, 1, len(pair), "Expected 9 to get the bye, as 9 has the most wins")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}

func TestByScoreLess(t *testing.T) {
	players := ByScore([]Scorer{
		&Player{id: 1, Wins: 1},
		&Player{id: 2, Wins: 2},
	})

	assert.False(t, players.Less(0, 1))
}

func TestAvoidRematches(t *testing.T) {
	players := []Scorer{
		&Player{id: 1, pastMatches: []int{2}},
		&Player{id: 2, pastMatches: []int{1}},
		&Player{id: 3, pastMatches: []int{4}},
		&Player{id: 4, pastMatches: []int{3}},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 1:
			assert.Equal(t, 3, pair[1].(*Player).id, "Expected pair: 1,3")
		case 2:
			assert.Equal(t, 4, pair[1].(*Player).id, "Expected pair: 2,4")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}

func TestAllowRematchesWhenRequired(t *testing.T) {
	players := []Scorer{
		&Player{id: 1, pastMatches: []int{2, 3, 4}},
		&Player{id: 2, pastMatches: []int{1, 3, 4}},
		&Player{id: 3, pastMatches: []int{1, 2, 4}},
		&Player{id: 4, pastMatches: []int{1, 2, 3}},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 1:
			assert.Equal(t, 2, pair[1].(*Player).id, "Expected pair: 1,3")
		case 3:
			assert.Equal(t, 4, pair[1].(*Player).id, "Expected pair: 2,4")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}

func TestAllowRematchesWhenRequiredButStillPreferNotTo(t *testing.T) {
	players := []Scorer{
		&Player{id: 1, pastMatches: []int{2, 3}},
		&Player{id: 2, pastMatches: []int{1, 4}},
		&Player{id: 3, pastMatches: []int{1}},
		&Player{id: 4, pastMatches: []int{3}},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 1:
			assert.Equal(t, 4, pair[1].(*Player).id, "Expected pair: 1,4")
		case 2:
			assert.Equal(t, 3, pair[1].(*Player).id, "Expected pair: 2,3")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}

func TestRematchInsteadOfPairDownTwice(t *testing.T) {
	players := []Scorer{
		&Player{id: 1, Wins: 1, pastMatches: []int{2, 3}, hasPairedDown: true},
		&Player{id: 2, Wins: 1, pastMatches: []int{1, 4}},
		&Player{id: 3, Wins: 0, pastMatches: []int{1}},
		&Player{id: 4, Wins: 0, pastMatches: []int{3}},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 1:
			assert.Equal(t, 2, pair[1].(*Player).id, "Expected pair: 1,2")
		case 3:
			assert.Equal(t, 4, pair[1].(*Player).id, "Expected pair: 3,4")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}

func TestRematchAfterCheckingPairdown(t *testing.T) {
	players := []Scorer{
		&Player{id: 1, Wins: 1, pastMatches: []int{2, 3}},
		&Player{id: 2, Wins: 1, pastMatches: []int{1, 1, 1, 1, 4}},
		&Player{id: 3, Wins: 0, pastMatches: []int{1}},
		&Player{id: 4, Wins: 0, pastMatches: []int{1, 3}},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 1:
			assert.Equal(t, 3, pair[1].(*Player).id, "Expected pair: 1,3")
		case 2:
			assert.Equal(t, 4, pair[1].(*Player).id, "Expected pair: 2,4")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}

func TestEveryonePairsDown(t *testing.T) {
	// Not sure if this could ever happen, but let's make sure the algorithm doesn't explode.
	players := []Scorer{
		&Player{id: 1, Wins: 1, hasPairedDown: true},
		&Player{id: 2, Wins: 2, hasPairedDown: true},
		&Player{id: 3, Wins: 3, hasPairedDown: true},
		&Player{id: 4, Wins: 4, hasPairedDown: true},
	}

	pairs := SteamrollerPairs(players)
	assert.Equal(t, 2, len(pairs))
	for _, pair := range pairs {
		switch pair[0].(*Player).id {
		case 4:
			assert.Equal(t, 3, pair[1].(*Player).id, "Expected pair: 4,3")
		case 2:
			assert.Equal(t, 1, pair[1].(*Player).id, "Expected pair: 2,1")
		default:
			assert.Fail(t, fmt.Sprintf("%#v is not expected to be the first in a pair.", pair[0]))
		}
	}
}