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).