A Ruby sorting program for multiple criteria

Question

This code review expands on an earlier one that deals with generating a football table from match data. This review deals with ordering said table based on several criteria.

Your opinions/refactorings are welcome. In particular, I'm looking for ways to optimise this.

Given a table with columns name, goals_for, goal_diff, and points, the program sorts the table based on the following criteria (in order of precedence):

1. Greatest number of points
2. Greatest goal diff
3. Greatest goals for
   • IF two or more teams are still tied, the following is used:
4. Greatest number of points from matches between tied teams
5. Greatest goal diff from matches between tied teams
6. Greatest goals scored from matches between tied teams
   • IF two or more teams are still tied, the following is used:
7. Draw lots

Background

The table is based on a World Cup group. Each group has four teams, and each team must play all other teams at least once. A total of six matches is played. A win is worth three, a draw one, and a loss zero points.

The program receives data in this form:

  [
    { home_team: "Algeria", away_team: "Slovenia", home_score: 2, away_score: 1 },
    { home_team: "USA",     away_team: "Slovenia", home_score: 5, away_score: 1 },
    { home_team: "England", away_team: "Slovenia", home_score: 4, away_score: 0 },
    { home_team: "Algeria", away_team: "USA",      home_score: 3, away_score: 0 },
    { home_team: "USA",     away_team: "England",  home_score: 2, away_score: 0 },
    { home_team: "England", away_team: "Algeria",  home_score: 3, away_score: 2 }
  ]

It uses a separate class to tabularize the data into this format (see previous review):

  [
    { name: "Algeria",  goals_for: 7, goals_against: 4,  goal_diff: 3,  points: 6 },
    { name: "England",  goals_for: 7, goals_against: 4,  goal_diff: 3,  points: 6 },
    { name: "USA",      goals_for: 7, goals_against: 4,  goal_diff: 3,  points: 6 },
    { name: "Slovenia", goals_for: 2, goals_against: 11, goal_diff: -9, points: 0 }
  ]

Sorting according to criteria 1 to 3 is very easy:

table.sort_by! { |team| [ team[:points], team[:goal_diff], team[:goals_for] ] }

Problem

But things get complicated if we have a tie between two or more teams. Criteria 4 to 7 require us to calculate a new table. This table must be based on a subset of matches that involve only the tied teams.

Note a tie can have 2, 3, or 4 teams. This is very important. For example, if all group games end with the same result, say a 1-1 draw, you get a four-way tie.

My example hash a three-way tie (according to criteria 1 to 3) between Algeria, England, and USA. To break this tie we must calculate a table based on matches involving those teams only.

  [
    { home_team: "Algeria", away_team: "USA",      home_score: 3, away_score: 0 },
    { home_team: "USA",     away_team: "England",  home_score: 2, away_score: 0 },
    { home_team: "England", away_team: "Algeria",  home_score: 3, away_score: 2 }
  ]

This data produces a different table.

  [
    { name: "Algeria",  goals_for: 5, goals_against: 3, goal_diff:  2, points: 3 },
    { name: "England",  goals_for: 3, goals_against: 4, goal_diff: -1, points: 3 },
    { name: "USA",      goals_for: 2, goals_against: 3, goal_diff: -1, points: 3 }
  ]

Once rank of this subset-table is determined, it must be applied to the original table, which is used to display the data. The original table's data must remain unchanged as it's complete (contains data for all matches). Only the order should change.

The final table, when both tables are combined (original, and from data subset), should be identical to the first table in my example.

Program

class Sorter
  attr_reader :table, :tied_teams

  def initialize(matches)
    @matches = matches
    @table = build_table_for(matches)
    @tied_teams = []
  end

  def sort
    table.sort! { |a, b| compare_teams(a, b) }.reverse!
    return table unless tied_teams.any?

    # If there are any ties

    # Get names of tied teams for easier lookup
    tied_team_names = tied_teams.map { |team| team[:name] }

    # Get a subset of matches involving tied teams
    matches_between_tied_teams = @matches.select do |match|
      tied_team_names.include?(match[:home_team]) && tied_team_names.include?(match[:away_team])
    end

    # Build a new table from only the matches between the tied teams
    tied_teams_table = build_table_for(matches_between_tied_teams)

    # Reset tied teams and sort the new table
    @tied_teams = []
    tied_teams_table.sort! { |a, b| compare_teams(a, b) }.reverse!

    # Teams are still tied. Sort by coin toss (shuffle)
    tied_teams_table.shuffle! if tied_teams.any?

    # combine the ranks of the subtable into the original table
    mapped_teams = tied_teams_table.map { |tied_team| table.find { |team| team[:name] == tied_team[:name] } }
    table.map! do |team|
      if tied_teams_table.find { |tied_team| tied_team[:name] == team[:name] }
        mapped_teams.shift
      else
        team
      end
    end
  end

private

  def compare_teams(a, b)
    comparison = compare_points(a, b)
    return comparison unless comparison.zero?

    comparison = compare_goal_diff(a, b)
    return comparison unless comparison.zero?

    comparison = compare_goals_for(a, b)
    return comparison unless comparison.zero?

    add_to_tied_teams(a, b)

    comparison
  end

  def compare_points(a, b)
    a[:points] <=> b[:points]
  end

  def compare_goal_diff(a, b)
    a[:goal_diff] <=> b[:goal_diff]
  end

  def compare_goals_for(a, b)
    a[:goals_for] <=> b[:goals_for]
  end

  def add_to_tied_teams(*teams)
    teams.each { |team| tied_teams << team }
    tied_teams.uniq!
  end

  def build_table_for(matches)
    Tabularizer.new(matches).build_table
  end
end

For more information on how FIFA tie breakers work, see this article by Aaron Willians.

If you want to see the table creating algorithm, you can find it in this Gist.

Answer 1

This answer's been through some revisions. See note at the end.

From a cursory it glance it looks OK, except that I feel there too much going on in Sorter#sort.

Also, with a name like Sorter, I almost expect the class to be state-less. Because if the class doesn't do anything but sort, why bother instantiating it? Shouldn't it just automatically do the only thing it can, and just return the ranking?

Such functionality can be added quite easily, of course:

class Sorter
  def self.sort(matches)
    self.new(matches).sort
  end
  # ...
end

But if you do want more functionality than just returning the sorted table, I'd call the class something other than Sorter.

For instance, you might simply call it Group, since it's a World Cup group you're trying to model. Sure, it'll still sort the teams, but that's not what it is.

While you're at it, it might be worth modelling the domain in greater detail. This doesn't have to be part of the public interface, but it'll be helpful just for the Group class to operate on first-class objects instead of hashes.

For larger logic refactoring, here's my take:
You're following the rules to the letter by sorting first and then checking for ties. The rules seem written with the expectation that ties aren't common, so the focus is on steps 1-3, and only if necessary, the other steps come into play. Your code reflects this, in a sense: If there are tied teams, you start doing a lot of work to sort subsets, and "manually" stitch them back together.

Instead, what you could do is simply sort one array once. It just needs to have information to be sorted correctly (i.e. the tie-breakers).

So, in pseudo-code, you'll want to compare arrays like this:

team_rank = [
  points in group,
  goal difference in group,
  goals total in group,
  points vs other teams (if tied),
  goal difference vs other teams (if tied),
  goals vs other teams (if tied),
  random number (if tied)
]

The first 3 values are needed regardless of ties, whereas the last 4 are added in the event of a tie. Obviously, the first 3 values are calculated the same as the next 3 values, just from a different set of matches. And to find which teams are tied, group_by comes in handy. Once the arrays have been built, all you need is a sort_by and you're done.

To do all this, I propose the following structure

class Match; end                    # a played match
class MatchAggregator; end          # a set of matches
class Group < MatchAggregator; end  # a World Cup group

I'll start at the end, since Group is the one which contains the sorting logic. It doesn't concern itself with formatting the data for display, but that's simple to add. For now, its #ranking method simply returns an array of team names and the arrays used to sort them.

class Group < MatchAggregator
  # takes an array of match-result hashes, like those in the question
  def initialize(matches)
    super matches.map { |result| Match.new(result) }
  end

  # returns a sorted array of hashes containing a team's name, and
  # the array used to rank it against the other teams
  def ranking
    # get the teams plus their rank within this group
    unsorted_teams = teams.map { |team| { name: team, rank: rank_for(team) } }

    # group teams by their "basic" rank (points, goal diff, goals),
    # i.e. group them if they're tied
    tie_groups = unsorted_table.group_by { |team| team[:rank] }.values

    # resolve ties (if any)
    # this is essentially a block with side-effects, so it's not pretty
    # but at least the side-effects are well-contained 
    tie_groups.each do |tied_teams|
      # a subset of 1 team can't be tied, so skip it
      next if tied_teams.one?

      # get the names of the tied teams
      names = tied_teams.map { |team| team[:name] } 

      # create a new MatchAggregator containing only matches
      # played between the tied teams
      subgroup = MatchAggregator.new matches_between(*names)

      # update the teams' :rank with their rank in the subgroup,
      # plus a random number
      tied_teams.each { |team| team[:rank] += subgroup.rank_for(team[:name]) + [lots.pop] }

      # the final tie-breaker: Randomness
      lots = (1..teams.count).to_a.shuffle
      tied_teams.each { |team| team[:rank] << lots.pop }
    end

    # Put it all together
    tie_groups.flatten.sort_by { |team| team[:rank] }.reverse
  end
end

Meanwhile, MatchAggregator, as mentioned, models a set of matches, and provides some convenient methods for, well, aggregating information from those matches.

class MatchAggregator
  attr_reader :matches

  # Note that this expects Match instances, not hashes.
  # We'll leave the hash -> Match conversion to Group,
  # as that's intended as the public-facing class
  def initialize(matches)
    @matches = matches.freeze
  end

  # returns an array of team names
  def teams
    matches.map(&:teams).flatten.uniq
  end

  # matches that include 1 or more of the given teams
  def matches_including(*teams)
    matches.select { |match| match.includes?(*teams) }
  end

  # matches between any of the given teams
  def matches_between(*teams)
    matches.select { |match| match.between?(*teams) }
  end

  # returns an array of values, based on the matches in
  # this group, that can be used for ranking teams
  def rank_for(team)
    methods = [:points_for, :goal_difference_for, :goals_for]
    methods.map { |method| sum(method, team) }
  end

  protected

  # returns the sum of calling the given method
  # on all matches that include the given team
  def sum(method, team)
    matches_including(team).inject(0) { |memo, match| memo += match.send(method, team) }
  end
end

Lastly, Match is merely a handy wrapper around the hashes you're using now

class Match
  attr_reader :result

  # take a hash like the one you're using now, e.g.
  # { home_team: "Algeria", away_team: "Slovenia", home_score: 2, away_score: 1 }
  def initialize(hash = {})
    @result = {
      hash[:home_team] => hash[:home_score],
      hash[:away_team] => hash[:away_score]
    }.freeze
  end

  # get the names of the competing teams
  def teams
    result.keys
  end

  # did the match include 1 or more of the given teams?
  def includes?(*names)
    (teams & names).any?
  end

  # did this match take place between
  # any 2 of the given competitors?
  def between?(*names)
    (teams & names).count == 2
  end

  # All the following methods should be self-explanatory.
  # In all cases, the `team` argument is a team name

  def goals_for(team)
    result[team] || 0
  end

  def goals_against(team)
    return 0 unless includes?(team)
    opponent = teams.detect { |name| name != team }
    result[opponent] || 0
  end

  def points_for(team)
    return 3 if won_by?(team)
    return 1 if includes?(team) && tied?
    0
  end

  def won_by?(team)
    goal_difference_for(team) > 0
  end

  def tied?
    result.values.uniq.one?
  end

  def goal_difference_for(team)
    goals_for(team) - goals_against(team)
  end
end

With the above, and the example data in the question, I get output like:

[
  {:name=>"Algeria",  :rank=>[6, 3, 7, 3, 2, 5, 2]},
  {:name=>"England",  :rank=>[6, 3, 7, 3, -1, 3, 4]},
  {:name=>"USA",      :rank=>[6, 3, 7, 3, -1, 2, 3]},
  {:name=>"Slovenia", :rank=>[0, -9, 2]}
]

---

A note on revisions:

I initially misunderstood the rules, so my first answer had code that didn't correctly resolve ties. So I updated the answer quite a lot to fix that, though it kept most of my original code intact. But it became hard to read, so I've cleaned it up (and refactored my code a little). Previous iterations are in the revision history of course, but be warned: it's mess in there.

Answer 2

As I said in your previous question, a functional approach is a good fit for this kind of problem. That's how I'd handle the tie-break rules:

accumulated_grouped = accumulate(match_results).group_by(&tiebreak_criterion)
initial_table = accumulated_grouped.sort.map { |value, accumulated| accumulated } 

table = initial_table.flat_map do |accumulated|
  if accumulated.size == 1
    accumulated
  else
    tied_teams = accumulated.map(&:team)
    accumulated_tied = accumulate(match_results, :teams => tied_teams)
    ordered_teams = accumulated_tied.sort_by(&tiebreak_criterion_for_group).map(&:team)
    accumulated.sort_by { |r| ordered_teams.index(r.team) }
  end
end

#[#<OpenStruct team="Algeria", points=6, goals_for=7, goals_against=4, goals_diff=11>,
# #<OpenStruct team="England", points=6, goals_for=7, goals_against=4, goals_diff=11>,
# #<OpenStruct team="USA", points=6, goals_for=7, goals_against=4, goals_diff=11>,
# #<OpenStruct team="Slovenia", points=0, goals_for=2, goals_against=11, goals_diff=13>]

accumulate is not shown, but it's basically the function you already have to accumulate values from match results (and optionally taking in account only some given teams).