# A Ruby sorting program for multiple criteria

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

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?

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

teams.each { |team| tied_teams << team }
tied_teams.uniq!
end

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


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

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

# 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

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

• Thank you for this thorough code review. At first glance, it seems that your proposed changes do not account for all the teams involved in the tie? Am I missing something? To clarify, using my example, the tie should be broken based on a table produced by matches from Algeria, USA, and England. That's three games. At first glance, your program seems to rank the teams based on head-to-head only. Am I missing something? – Mohamad May 30 '14 at 14:57
• Also, what if the tie is in the middle of the group? Say England won the group by criteria 1, and the tie was between England and the US only? I will write some tests for these classes with multiple scenarios and report back. – Mohamad May 30 '14 at 15:00
• @Mohamad Ah, I misunderstood the "all tied teams" part. That sort of breaks my answer, I'm afraid. – Flambino May 30 '14 at 15:03
• Ahh! :( - That's a shame. I really like the way you organised the code. To answer your comment re Sorter maintaining state: The only state I need to maintain is if there are ties, hence the @tied_teams = [] in the init. – Mohamad May 30 '14 at 15:12
• @Mohamad I may have a fairly simple way to solve this. I'll get back to you – Flambino May 30 '14 at 15:29

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