Lesson 5 of 8 · 25 min

Challenge: Pick fair football teams

Every Saturday, Tariro organises football on the dusty pitch in Mbare. Last week one team won 9-0 and nobody had fun. This week she has given every player a skill score, and she wants the two teams to be as fair as possible.

The teams do not need the same number of players (the smaller team can have the goalkeeper with the best gloves). What matters is that the total skill of each team is as close as possible.

Your task

Write team_gap(skills). It takes a list of skill scores, one per player, and returns the smallest possible difference between the two teams' totals when every player is put in one team or the other.

team_gap([1, 2, 3, 4])        # 0    1 + 4 = 5 against 2 + 3 = 5
team_gap([7, 3, 2])           # 2    7 against 3 + 2 = 5
team_gap([20, 3, 2])          # 15   20 against 3 + 2 = 5
team_gap([8, 7, 6, 5, 4])     # 0    8 + 7 = 15 against 6 + 5 + 4 = 15
team_gap([])                  # 0

Rules

  • Every player plays, in exactly one of the two teams.
  • A team can have any number of players, even none (useful when there is only one player).
  • Skill scores are whole numbers, 0 or more. There are at most 16 players.
  • Return the gap as a positive number (or 0).

Tips

  • A tempting shortcut is to sort the players and give each one to whichever team is weaker. Try it on [8, 7, 6, 5, 4] by hand: it gives a gap of 4, not 0. You need to look at more possibilities.
  • Idea 1, recursion: write a helper best(i, team_a, team_b) that decides player i. It tries putting them in team A, then in team B, and returns the smaller gap. When i reaches the end of the list, the gap is abs(team_a - team_b).
  • Idea 2, reachable totals: you only need the total of team A, since team B gets the rest. Start with a set holding 0. For each player, add t + skill for every total t already in the set. At the end, check which total is closest to half of everything.
  • min(...), abs(x) and sum(skills) are handy here.
main.py
def team_gap(skills):
    # TODO: find the split of players with the smallest difference in total skill
    return -1


print(team_gap([8, 7, 6, 5, 4]))  # should print 0
print(team_gap([20, 3, 2]))       # should print 15

Python 3.14 runs right here in your browser. The first run downloads about 10 MB; after that it is instant.

Discussion

Stuck? Ask here. Be kind, and share hints rather than full answers.

Loading the discussion…