The goal is too find a pairing of the current player with any player he never was paired with or with the player he paired with the longest time ago.
The way you describe the problem it really sounds trivial (you may have to provide an explicit example of what you mean). The player ID at the end of the indexed collection is the player that was played against the longest time ago (oldest match up).
However, the most obvious candidate may itself have a better candidate: in a worst case scenario where
Player A played against Player C 300 days ago Player C is the oldest match up of Player A and therefore the best candidate for * Player A*.
But for Player C who played against Player D 600 days ago the oldest and therefore best match up would be Player D.
In conclusion, the match up has to be fair for both, the current player and the candidate. To accomplish that fairness we need additional information. The order of player IDs is pretty much useless. Instead we need to create a mapping of the match date to the matched up player.
Unless you want match up Player A with Player C where Player C is the oldest match up for Player A but Player A is the latest match up for Player C (unfair for Player C) you have to introduce a timestamp or any other attribute to weight the matches globally (and not for every player individually like the sort order).
In order to give both the best match up you would have to fins the player that has the smallest delta between the oldest match of the current player and the candidates. For example, if this delta is 0 this would mean that both players have their oldest match on the same date which would make a perfect match for both. But this ideal result hasn't a high probability to occur often. This means, you have to find the player that has its oldest match date as close as possible to the oldest match date of the current player or in other words where the delta between the oldest match date of the current player and the oldest match date of the candidate is the smallest.
The algorithm is as follows:
Generate a list of all available players (match up candidates). If the available players pool is of type HashSet<T> you can improve the lookup performance to O(1).
Find the first ID in this player pool that is not contained in the current player's ID index. If one is found, you have a player that the current player was never matched up against. The algorithm successfully ends here.
If your query doesn't return a result (because all available players have already been paired with the current player) traverse the current player's match up index from back to front (oldest match to latest): get the last item (player ID) of the current player that is also contained in theavailable player pool (from step 1). If not, either the current player never had a match before or the recent players are not available (e.g. offline). The algorithm ends here as we can simply pick a random player from the available player pool.
If we found old match ups that are available (candidates), we have to compare each candidate's oldest match date with the oldest match date of the current player by subtracting both dates. The candidate that produces the smallest delta wins.
class Player
{
public int Id { get; }
public IReadOnlyCollection<Player> SortedMostRecentMatches => this.SortedMostRecentMatchesInternal.Values;
// Use a SOrtedDictionary for the sorting to provide better sort performance
private SortedDictionary<DateTime, Player> SortedMostRecentMatchesInternal { get; }
// Lookup table to get a match date by Player
private Dictionary<Player, DateTime> MostRecentMatchesIndex { get; set; }
public Player(int id)
{
this.Id = id;
this.SortedMostRecentMatchesInternal = new SortedDictionary<DateTime, Player>();
this.MostRecentMatchesIndex = new Dictionary<Player, DateTime>();
}
public void AddMatchUp(Player player)
{
DateTime matchUpTimestamp = DateTime.Now;
AddMatchUpInternal(player, matchUpTimestamp);
player.AddMatchUpInternal(this, matchUpTimestamp);
}
private void AddMatchUpInternal(Player player, DateTime matchUpTimestamp)
{
// Only keep the most recent key
if (this.MostRecentMatchesIndex.TryGetValue(player, out DateTime mostRecentMatchDate))
{
this.SortedMostRecentMatchesInternal.Remove(mostRecentMatchDate);
}
// Create or update
this.MostRecentMatchesIndex[player] = matchUpTimestamp;
this.SortedMostRecentMatchesInternal.Add(matchUpTimestamp, player);
}
public bool TryGetMatchInfo(Player player, out DateTime mostRecentMatchDate)
=> this.MostRecentMatchesIndex.TryGetValue(player, out mostRecentMatchDate);
}
class Program
{
private static IEnumerable<Player> AvailablePlayers { get; set; }
static async void Main()
{
var player1 = new Player(1);
var player2 = new Player(2);
var player3 = new Player(3);
var player4 = new Player(4);
this.AvailablePlayers = new List<Player>()
{
player1,
player2,
player3,
player4
};
player1.AddMatchUp(player2);
await Task.Delay(TimeSpan.FromMilliseconds(100));
player1.AddMatchUp(player3);
await Task.Delay(TimeSpan.FromMilliseconds(100));
player1.AddMatchUp(player3);
await Task.Delay(TimeSpan.FromMilliseconds(100));
player3.AddMatchUp(player4);
await Task.Delay(TimeSpan.FromMilliseconds(100));
player4.AddMatchUp(player3);
await Task.Delay(TimeSpan.FromMilliseconds(100));
player4.AddMatchUp(player1);
await Task.Delay(TimeSpan.FromMilliseconds(100));
player4.AddMatchUp(player2);
foreach (Player player in this.AvailablePlayers)
{
Debug.WriteLine(Environment.NewLine);
Debug.WriteLine($"************ Matches of player {player.Id}:");
foreach (var matchUpPlayer in player.SortedMostRecentMatches)
{
if (player.TryGetMatchInfo(matchUpPlayer, out DateTime matchDate))
{
Debug.WriteLine($"Player: {matchUpPlayer.Id} Date: {matchDate.ToString("H:mm:ss:fff")}");
}
}
}
Debug.WriteLine(Environment.NewLine);
// Specify the player we want to find a match candidate for
Player currentPlayer = player1;
if (TryFindNextMatchUp(currentPlayer, out Player? suggestedMatchUp))
{
Debug.WriteLine($"===> Sugested match up player for current player {currentPlayer.Id}: {suggestedMatchUp.Id}");
Debug.WriteLine(Environment.NewLine);
}
else
{
Debug.WriteLine($"===> No player found for a match up.");
}
}
// The actual algorithm
private static bool TryFindNextMatchUp(Player currentPlayer, out Player? suggestedMatchupCandidate)
{
// Create a copy of the available players pool that we can modify
// to pre-filter it in order to improve the overall performance
// by reducing the number of necessary iterations
var candidates = new HashSet<Player>(this.AvailablePlayers);
// The current player can't play against himself, so remove from the temporary pool
candidates.Remove(currentPlayer);
// Get the oldest match up tha is currently available.
// This is the preferred candidate.
Player? oldestMatchupOfCurrentPlayer = currentPlayer.SortedMostRecentMatches.LastOrDefault(this.AvailablePlayers.Contains);
if (oldestMatchUpOfCurrentPlayer is null
|| !currentPlayer.TryGetMatchInfo(oldestMatchupOfCurrentPlayer, out DateTime oldestMatchDateOfCurrentPlayer))
{
// Current player never had a match before
// or the recent players are not available (e.g. offline)
suggestedMatchupCandidate = this.AvailablePlayers.FirstOrDefault();
return suggestedMatchupCandidate is not null;
}
// TimeSpan.MaxValue is about 10,675,199 days. Good enough for a meaningless seed value
(double OldestMatchDateDelta, Player? Candidate) suggestedCandidateInfo = (TimeSpan.MaxValue.TotalMicroseconds, null);
// Set preferred candidate as seed
if (TryGetOldestMatchDateDelta(oldestMatchDateOfCurrentPlayer, oldestMatchupOfCurrentPlayer, out double absoluteDeltaSeed))
{
suggestedCandidateInfo = (absoluteDeltaSeed, oldestMatchupOfCurrentPlayer);
// The ideal candidate is now matched.
// Remove from temporary pool.
candidates.Remove(oldestMatchupOfCurrentPlayer);
Debug.WriteLine($"Oldest matchup delta player {currentPlayer.Id} Vs player {oldestMatchupOfCurrentPlayer.Id}: {absoluteDeltaSeed} (seed)");
}
foreach (Player candidate in candidates)
{
if (!currentPlayer.SortedMostRecentMatches.Contains(candidate))
{
// Found a player that was never matched up against the current player
suggestedMatchupCandidate = candidate;
return true;
}
if (TryGetOldestMatchDateDelta(oldestMatchDateOfCurrentPlayer, candidate, out double absoluteDelta))
{
Debug.WriteLine($"Oldest matchup time delta of current player {currentPlayer.Id} Vs candidate {candidate.Id}: {absoluteDelta}");
if (absoluteDelta < suggestedCandidateInfo.OldestMatchDateDelta)
{
suggestedCandidateInfo = (absoluteDelta, candidate);
}
}
}
suggestedMatchupCandidate = suggestedCandidateInfo.Candidate;
return suggestedMatchupCandidate is not null;
}
// Calculate the absolute time delta
// by subtracting the oldest match dates of the current player and a candidate
private static bool TryGetOldestMatchDateDelta(DateTime oldestMatchDateOfCurrentPlayer, Player candidate, out double absoluteDelta)
{
absoluteDelta = -1;
Player oldestMatchupOfCandidate = candidate.SortedMostRecentMatches.Last();
if (candidate.TryGetMatchInfo(oldestMatchupOfCandidate, out DateTime oldestMatchDateOfCandidate))
{
double deltaInMicroseconds = oldestMatchDateOfCurrentPlayer.Subtract(oldestMatchDateOfCandidate).TotalMicroseconds;
absoluteDelta = Math.Abs(deltaInMicroseconds);
}
return absoluteDelta is not -1;
}
