HiveBrain v1.2.0
Get Started
← Back to all entries
patternrubyMinor

A Ruby sorting program for multiple criteria

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
sortingcriteriaprogramformultipleruby

Problem

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

  • Greatest number of points



  • Greatest goal diff



  • Greatest goals for



  • IF two or more teams are still tied, the following is used:



  • Greatest number of points from matches between tied teams



  • Greatest goal diff from matches between tied teams



  • Greatest goals scored from matches between tied teams



  • IF two or more teams are still tied, the following is used:



  • 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:

Solution

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

Code Snippets

class Sorter
  def self.sort(matches)
    self.new(matches).sort
  end
  # ...
end
class Match; end                    # a played match
class MatchAggregator; end          # a set of matches
class Group < MatchAggregator; end  # a World Cup group
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
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
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

Context

StackExchange Code Review Q#52062, answer score: 2

Revisions (0)

No revisions yet.