Skip to content

Instantly share code, notes, and snippets.

@Katharsas Katharsas/AutoMatchup.java
Last active Dec 19, 2018

Embed
What would you like to do?
Team matchmaking respecting positions (untested, untried)
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
class AutoMatchup {
/**
* Assume that this exists somewhere
*/
interface TrueSkill {
int get1v1Quality(String playerA, String playerB);
}
/**
* An imaginary 1v1 and the quality that this 1v1 would have
*/
class Matchup1v1 {
String playerA;
String playerB;
int quality;
Matchup1v1(String playerA, String playerB, int quality) {
// always save in same order so that order of given players does not matter
this.playerA = playerA.compareTo(playerB) > 0 ? playerA : playerB;
this.playerB = playerA.compareTo(playerB) <= 0 ? playerA : playerB;
this.quality = quality;
}
boolean overlaps(Matchup1v1 other) {
return other.contains(this.playerA) || other.contains(this.playerB);
}
boolean contains(String player) {
return this.playerA.equals(player) || this.playerB.equals(player);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj instanceof Matchup1v1) {
var other = (Matchup1v1) obj;
return playerA.equals(other.playerA) && playerB.equals(other.playerB);
}
return false;
}
@Override
public int hashCode() {
return Objects.hash(playerA, playerB);
}
}
/**
* A team viewed as a number of imaginary 1v1s (one per position) and combined 1v1 qualities
*/
class TeamComposition {
Set<Matchup1v1> matchups = new HashSet<>();
int combinedQualityOfMatchups = 0;
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
return obj instanceof TeamComposition && matchups.equals(((TeamComposition) obj).matchups);
}
@Override
public int hashCode() {
return matchups.hashCode();
}
}
/**
* Entry point
*/
public TeamComposition getBestTeamMatchup(Set<String> players, TrueSkill trueSkill) {
if (players.size() % 2 != 0) {
throw new IllegalArgumentException("Number of players must be even");
}
// get all possible 1v1s and their qualities
var all_1v1s = new HashSet<Matchup1v1>();
for (var playerA : players) {
for (var playerB : players) {
if (!playerA.equals(playerB)) {
int qualityOfAvsB = trueSkill.get1v1Quality(playerA, playerB);
all_1v1s.add(new Matchup1v1(playerA, playerB, qualityOfAvsB));
}
}
}
// get all possible combinations of teams as multiple 1v1 matchups per composition
Set<TeamComposition> compositions = createTeamCompositions(all_1v1s);
// set quality for team compositions
calculateCompositionQualities(compositions);
// sort by quality and return last
var sorted = new ArrayList<>(compositions);
sorted.sort((a, b) -> Integer.compare(a.combinedQualityOfMatchups, b.combinedQualityOfMatchups));
return sorted.get(sorted.size() - 1);
}
/*
* Returns possible team compositions and (recursively adds more matchups to finish compositions).
*/
private Set<TeamComposition> createTeamCompositions(Set<Matchup1v1> availableMatchups) {
if (availableMatchups.size() == 1) {
// if there is only one possible matchup, the team composition IS that matchup
var result = new HashSet<TeamComposition>();
var newComposition = new TeamComposition();
newComposition.matchups.add(availableMatchups.iterator().next());
return result;
} else {
Set<TeamComposition> result = new HashSet<>();
// select a matchup from available
for (var selected : availableMatchups) {
// remove any matchups that have overlapping players with out selected matchup
var remaining = new HashSet<Matchup1v1>(availableMatchups);
removeOverlappingMatchups(selected, remaining);
// recursively get team compositions for the remaining matchups (which now include
// exactly two players less, the players from our selected matchup). If all players
// except two were removed, only their matchup will be left and recursion stops.
Set<TeamComposition> compositions = createTeamCompositions(remaining);
// we add our selected matchup to all existing (unfinished) team compositions
for (var composition : compositions) {
composition.matchups.add(selected);
result.add(composition);
}
}
// do this for all possible selections to get all possible compositions
return result;
}
}
private void removeOverlappingMatchups(Matchup1v1 matchup, Set<Matchup1v1> target) {
for (var i = target.iterator(); i.hasNext();) {
if (i.next().overlaps(matchup)) {
i.remove();
}
}
}
private void calculateCompositionQualities(Set<TeamComposition> compositions) {
for (var composition : compositions) {
composition.combinedQualityOfMatchups = 0;
for (var single_1v1 : composition.matchups) {
// could also be squared
composition.combinedQualityOfMatchups += single_1v1.quality;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.