Find max possible Total from a list of player scores across their positions

Question

How would I find the maximum possible team score given a list of players?

I maintain a social fantasy league (Aussie Rules) website where by you pick 18 players at the start of the season, then each week you select a team of 6 players with 1 player assigned to each position. Your score for the week is the sum of each players score you picked. E.g. If each player were to score 50, your team score for the week would be 300.

In the interest of analysing your team after the round has finished - I wanted to show a couple of metrics. The first being the highest score in each position, and the second being your team of the week.

I can figure out the highest score in each position doing something like this (the green highlighting in the 'list of player scores' screenshot).

foreach (var player in playerList.Where(p => p.Forward == playerList.Max(x => x.Forward) && p.Forward > 0)) { player.ForwardTopScore = true; }
foreach (var player in playerList.Where(p => p.TallForward == playerList.Max(x => x.TallForward) && p.TallForward > 0)) { player.TallForwardTopScore = true; }
foreach (var player in playerList.Where(p => p.Offensive == playerList.Max(x => x.Offensive) && p.Offensive > 0)) { player.OffensiveTopScore = true; }
foreach (var player in playerList.Where(p => p.Defensive == playerList.Max(x => x.Defensive) && p.Defensive> 0)) { player.DefensiveTopScore = true; }
foreach (var player in playerList.Where(p => p.OnBaller == playerList.Max(x => x.OnBaller) && p.OnBaller > 0)) { player.OnBallerTopScore = true; }
foreach (var player in playerList.Where(p => p.Ruck == playerList.Max(x => x.Ruck) && p.Ruck > 0)) { player.RuckTopScore = true; }

However, figuring out the max possible score the team could have achieved is proving more difficult than I'd have thought. In that, a high score may be shared across positions. Also - the "best possible team" you could have picked might not mean that player has the highest score for a position.

The best possible score I calculate for this example (i.e. best 6 players you could have picked across each position) for that team is 288. I.e. by adding up the 6 scores I've highlighted in red boxes you arrive at 288. See how even though Josh Kennedy would have got 57 in the "Off" position, you'd have been better of selecting him in the "FW" position as the difference between the next best "FW" player score of 19 (by Toby Greene) is 23. Remember, you must assign a player to 1 position before the rounds starts so you can only use 1 score from each player.

Any suggestions? How would I code a loop/query that pulls out the list of players and their scores making up the best possible team score of 288?

Just for some more info, playerList is built like this, I add the actual scores later on after some web service calls which get the stats (Kicks, Handballs, etc..)

List<PlayerScore> playerList = new List<PlayerScore>();

foreach (var t in teams)
{
    playerList.AddRange(t.TeamSelections.Where(x => x.DateInactive == null).OrderBy(x => x.PlayerName).Select(p => new PlayerScore
    {
        TeamId = p.TeamID,
        PlayerName = p.PlayerName,
        Club = p.Club,
        ClubAbbreviation = Helper.Stats.GetClubAbbreviation(p.Club),
        TeamLeagueId = p.Team.LeagueId,
        TeamSelection = p.TeamSelectionId
    }));
}

Answer 1

So here's where it ended up.. Might help anyone battling with the logic of picking the highest possible total across a set of numbers. So far so good, I've not seen an instance where it doesn't return the correct result.. Feel free to suggest code clean-ups / optimizations.

    private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
    {
        return length == 1 ? list.Select(t => new[] {t}) : GetPermutations(list, length - 1).SelectMany(t => list.Where(o => !t.Contains(o)), (t1, t2) => t1.Concat(new[] {t2}));
    }

    public static List<PlayerScore> TeamOfTheWeek(List<PlayerScore> playerList)
    {
        // Remove the players who scored 0 accross the board.
        playerList.RemoveAll(player => player.Forward + player.TallForward + player.Offensive + player.Defensive + player.OnBaller + player.Ruck == 0);

        // Rank each player score within a position.
        var forwardRank = playerList.RankByDescending(p => p.Forward, (p, r) => new {Rank = r, Player = p});
        var tallForwardRank = playerList.RankByDescending(p => p.TallForward, (p, r) => new {Rank = r, Player = p});
        var offensiveRank = playerList.RankByDescending(p => p.Offensive, (p, r) => new { Rank = r, Player = p });
        var defensiveRank = playerList.RankByDescending(p => p.Defensive, (p, r) => new { Rank = r, Player = p });
        var onBallerRank = playerList.RankByDescending(p => p.Defensive, (p, r) => new { Rank = r, Player = p });
        var ruckRank = playerList.RankByDescending(p => p.Ruck, (p, r) => new { Rank = r, Player = p });

        for (int i = playerList.Count - 1; i >= 0; i--)
        {
            //var rankName = forwardRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Player.PlayerName;
            var fw = forwardRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Rank;
            var tf = tallForwardRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Rank;
            var off = offensiveRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Rank;
            var def = defensiveRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Rank;
            var ob = onBallerRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Rank;
            var ruck = ruckRank.First(x => x.Player.PlayerName == playerList[i].PlayerName).Rank;

            if (fw >= 6 && tf >= 6 && off >= 6 && def >= 6 && ob >= 6 && ruck >= 6)
            {
                // Player is outside top 6 for each position so remove, and reduce permutations.
                playerList.RemoveAt(i);
            }
        }   

        // Now update the playerId as this is used to join back to the array later.
        var playerId = 0;
        foreach (var p in playerList.OrderBy(p => p.PlayerName))
        {
            p.Id = playerId;
            playerId = playerId + 1;
        }

        // Create and fill the position scores.
        List<int[]> positionScoreArray = new List<int[]>();
        foreach (var player in playerList.OrderBy(p => p.PlayerName))
        {
            // Player scored more than 0 so add to the positionScoreArray.
            int[] playerScores = { player.Forward, player.TallForward, player.Offensive, player.Defensive, player.OnBaller, player.Ruck };
            positionScoreArray.Add(playerScores);
        }

        // Players remaining in list pulled into array, ready for processing.
        string[] playerNameArray = playerList.OrderBy(x => x.PlayerName).Select(p => p.PlayerName).ToArray();

        // Load up the actual position scores to use in Parallel.For processing.
        for (int i = 0; i < playerNameArray.Length; i++)
        {
            for (int j = 0; j < positionScoreArray.Count; j++)
            {   
                if (j == 0)
                {
                    var player = playerList.FirstOrDefault(p => p.PlayerName == playerNameArray[i]);
                    if (player != null)
                        positionScoreArray[i][j] = player.Forward;
                }
                if (j == 1)
                {
                    var player = playerList.FirstOrDefault(p => p.PlayerName == playerNameArray[i]);
                    if (player != null)
                        positionScoreArray[i][j] = player.TallForward;
                }
                if (j == 2)
                {
                    var player = playerList.FirstOrDefault(p => p.PlayerName == playerNameArray[i]);
                    if (player != null)
                        positionScoreArray[i][j] = player.Offensive;
                }
                if (j == 3)
                {
                    var player = playerList.FirstOrDefault(p => p.PlayerName == playerNameArray[i]);
                    if (player != null)
                        positionScoreArray[i][j] = player.Defensive;
                }
                if (j == 4)
                {
                    var player = playerList.FirstOrDefault(p => p.PlayerName == playerNameArray[i]);
                    if (player != null)
                        positionScoreArray[i][j] = player.OnBaller;
                }
                if (j == 5)
                {
                    var player = playerList.FirstOrDefault(p => p.PlayerName == playerNameArray[i]);
                    if (player != null)
                        positionScoreArray[i][j] = player.Ruck;
                }
            }
        }

        Stopwatch parallelForEachStopWatch = new Stopwatch();
        parallelForEachStopWatch.Start();

        var count = 0;
        var playerIds = Enumerable.Range(0, playerNameArray.Length).ToList();
        var best = new { PlayerIds = new List<int>(), TeamScore = 0 };
        var positions = new[] { "FW", "TF", "Off", "Def", "OB", "Ruck" };

        // Thread safe the Parallel.ForEach
        lock (ThreadSafeObject)
        {
            Parallel.ForEach(GetPermutations(playerIds, positions.Length), perm =>
                {
                    var teamScore = 0;
                    var players = perm.ToList();
                    for (int i = 0; i < positions.Length; i++) teamScore += positionScoreArray[players[i]][i];
                    if (teamScore > best.TeamScore) best = new {PlayerIds = players, TeamScore = teamScore};
                    if (count++%100000 == 0) Debug.WriteLine($"{count - 1:n0}");
                }
            );
        }

        parallelForEachStopWatch.Stop();
        TimeSpan parallelForEach = parallelForEachStopWatch.Elapsed;

        Debug.WriteLine($"Parallel.ForEach (secs): {parallelForEach.Seconds}");
        Debug.WriteLine($"Permutations: {count:n0}");
        Debug.WriteLine($"Team Score: {best.TeamScore}");

        // Track Parallel.ForEach result.
        var tcTotwRequest = new TelemetryClient();
        tcTotwRequest.TrackEvent($"Permutations: {count:n0} Score: {best.TeamScore} Time (sec): {parallelForEach.Seconds}");

        lock (ThreadSafeObject)
        {
            if (best.PlayerIds.Count > 0)
            {
                for (int i = 0; i < positions.Length; i++)
                {
                    // Update the playerList, marking best players with TeamOfTheWeek position.
                    var player = playerList.FirstOrDefault(p => p.Id == best.PlayerIds[i]);
                    if (player != null)
                    {
                        player.TeamOfTheWeekPosition = positions[i];
                        player.TeamOfTheWeekScore = best.TeamScore;
                    }
                }
            }
        }

        return playerList.OrderBy(p => p.PlayerName).ToList();
    }
}

Answer 2

I don't know the rules of how teams are picked, but presumably exactly one player has to fill each of the six roles?

A brute force approach could work, if you don't have too many players (e.g. on the above table it might well work.) Then, if you have n players, there are n choices for the first, n-1 for the second (because you can't have the same player in two different positions), etc. This gives a total of nP6 (falling factorial) possibilities. This is pretty large, of the order of n⁶. If you wanted to implement this, you could, to be quick and dirty, implement a six-deep loop (making sure to exclude players already chosen), check the score, and keep track of the highest one(s).

One way of cutting down the number of possibilities to check, which I think is sound, is this: choose your player in position X from only the top 6 scorers in that position. The intuition is this: if I've chosen (optimally or not) 5 players for my other positions, I can't have chosen all six of the best scorers for position X! So at least one of them is still available. Then I can't do better than choosing the best of them that's still left. So I can certainly exclude anyone from that position, who didn't score top 6. Issues may come in when there are ties, in which case, for safety, keep anyone who ties for any of the top 6 positions.

This way (assuming no ties), you only ever have to search through 6⁶ possibilities, at most (fewer if the same players are getting top 6 in different categories). And the initial search for top 6 will be tractable even for a large list.

Any or all of this could be done with LINQ, but it needn't be necessary.