Rails 3 complicated sorting

I need to sort league table in Rails 3, so I have LeagueTable model, Team model and Match model.

Basic sorting is done by points summary, so this is easy part. But when two teams got the same points number, I want to sort them by points won in matches between this two teams.

I got no idea how to do this.

EDIT:

# league_table.rb model
class LeagueTable < ActiveRecord::Base
    belongs_to :team
end


# match.rb model
class Match < ActiveRecord::Base
    belongs_to :team_home, :class_name => "Team"
    belongs_to :team_away, :class_name => "Team"
end


# team.rb model
class Team < ActiveRecord::Base
    has_many :matches
end


# schema.rb
create_table "league_tables", :force => true do |t|
    t.integer  "team_id"
    t.integer  "points"
    t.integer  "wins"
    t.integer  "draws"
    t.integer  "looses"
    t.integer  "goals_won"
    t.integer  "goals_lost开发者_开发问答"
    t.datetime "created_at"
    t.datetime "updated_at"
    t.integer  "matches"
    t.integer  "priority"
  end

  create_table "matches", :force => true do |t|
    t.integer  "team_home_id"
    t.integer  "team_away_id"
    t.integer  "score_home"
    t.integer  "score_away"
    t.datetime "created_at"
    t.datetime "updated_at"
  end

  create_table "teams", :force => true do |t|
    t.string   "name"
    t.datetime "created_at"
    t.datetime "updated_at"
  end

Very interesting question. Here is (more less) how I would handle it, using recursion and the magic of group_by.

1. You would need a class method that, given an array of teams, calculates the number of points (goals for, goals against...) each team has got in the matches between those teams only. Assume you return a hash of hashes: {team_foo => {:points => 10, :goals_for => 33, :goals_against => 6}, team_bar => {:points => 18, :goals_for => 50, :goals_against => 11}...}.
2. The final order of the teams will be put into an array final_order, which is empty now.
3. Take all teams to an array and apply the method mentioned above. You should now have teams and the number of points (goals for, goals against...) all the teams have gained in all the games currently played. Store it somewhere, say under the name all_teams_scores.
4. Take all teams and group them using group_by: teams.group_by {|t| all_teams_scores[t][:points]}. What you get is an OrderedHash, looking like: {10 => [team_foo], 18 => [team_bar, team_xyz]}. The key is what you group by, the value is always an array. Store this hash, e.g. as league_table.
5. Sort the keys of league_table (remember to reverse when needed) and check the values of league_table according to them. If the array has two or more elements, apply points 3.-5. to the teams in that array. If the array has one element, append this element to final_order.
6. Done.

Some remarks:

• Remember that in the worst case you are left with two or more teams that have gained the same number of points (goals...) in the direct games. You need to handle that, or sort by random.
• The above steps group by points only. If you need to first sort by points in all games, then points in direct games, it will work. If you want to sort by points in all games, points in direct games, goals in all games - you need to refine the above algorithm. It should not be hard, though ;)
• You can group_by an array (which helps when you want to sort over a number of things before or after you sort by direct games).
• Unless your site is going to be heavily used, generate the table whenever requested. No need to store it in the dabase - unless the season is over and no changes to the game results are to be made.
• If you decide to store the table in the database, ensure that the fields related to the position of a team in the table are not editable by the user. The best way probably would be to implement the above algorithm as a stored procedure (PostgreSQL supports pl/Ruby, although I never used it), create view based on that and access league table from Rails through it (views are, generally, read only). Of course, removing the access to these fields from the administrative interface is also ok, for 99.99% situations ;)
• This may not (and probably is not) the optimal solution in terms of speed or memory efficiency (although I have not checked it), but I suppose the code produced according to this method should be easy to read, understand and maintain later on.

Hope this helps.

This is how i would do it :

1. First, i would just sort the teams based on their points. As you said, that is kinda trivial.

2. Then, i would traverse the sorted array and check possible teams that have the same points. This would show in a new array of hashes. For each set of teams that i would find that have the same points, i would denote with a hash. Think of 3 competing teams :

{ :TeamA => 3, :TeamB => 2 }
{ :TeamA => 3,  :TeamC => 4 }
{ :TeamB => 1,  :TeamC => 0 }

1. Now, i would sort. To make things easy, you can have a max or min element (representing a team each time).

Traversing with max :

1. max = TeamA
2. max = TeamC

So strongest team is TeamC. Eliminate that team and repeat. The last 2 hashes are now eliminated and we are just left with the first, which shows that TeamA > TeamB. So, the final sorting would be :

TeamC > TeamA > TeamB

NOTICE: TeamC is not better than TeamB when only these two are regarded. This algorithm gives an overall better team, based on the winning points.

Your case is actually simpler. You just want to compare two teams. Therefore, a hash like :

{ :TeamA => 3, :TeamB => 2 }

clearly denotes that TeamA is better than TeamB and should be ranked higher. If you want to compare 3 teams having the same points, you would have to have another criteria, like highest scoring team is better.

EDIT

If the next 2 factors to get the best team is goals scored and then lost difference, you would have another hash like :

{ :TeamA => [3, 2], :TeamA => [2, 1], :TeamC => [1, 1] }

With [3,2] indicating [goals scored, lost difference]. You can now easily identify the best teams based on these two parameters.

I would add an rival_points column to your LeagueTable model and update it only if there are other teams with the same number of points.

I was thinking about something like this (haven't tested if it works):

class LeagueTable
  after_save :set_order_of_equals

  def set_order_of_equals
    LeagueTable.all.each do |lt|
      points_against_rivals = 0
      LeagueTable.where('points = ? and matches = ? and team_id <> ?', lt.points, lt.matches, lt.team_id).each do |lt_same_points|
        points_against_rivals += lt.team.points_against(lt_same_points.team)
      end
      lt.rival_points = points_against_rivals
      LeagueTable.after_save.clear # clear the after_save callback to prevent it from running endlessly
      lt.save
    end
  end
end


class Team
  def points_against(opponent)
    points = 0

    # Home games
    matches.where(:team_away => opponent).each do |m|
      if m.score_home == m.score_away
        points += 1
      elsif m.score_home > m.score_away
        points += 3
      end
    end

    # Away games
    matches.where(:team_home => opponent).each do |m|
      if m.score_away == m.score_home
        points += 1
      elsif m.score_away > m.score_home
        points += 3
      end
    end

    points
  end
end

# With this you can get the correct order like this
lt = LeagueTable.order('points desc, matches asc, rival_points desc')

Here is a SQL heavy but efficient solution. Most of difficult logic is executed at the DB.

Add a new column called group_rank to the league_tables table ( should default to 0). Check for points collision during save operation. If there is point collision, calculate the group_rank for colliding teams.

This way, you can get the teams in proper order using a simple order clause.

LeagueTable.all(:order => "points ASC, group_rank ASC")

Add a after_save callback to determine point collision on LeagueTable model.

# league_table.rb model
class LeagueTable < ActiveRecord::Base
  belongs_to :team

  after_save :update_group_rank

  def update_group_rank
    return true unless points_changed?
    # rank the rows with new points and old points
    rank_group(points) and rank_group(points_was) 
  end

# The rank_group method:

  def rank_group(group_points)
    group_count = LeagueTable.count(:conditions =>{:points => group_points})
    return true unless group_count > 1 # nothing to do
    sql = "UPDATE league_tables JOIN
      (
      SELECT c.team_id, SUM(IF(c.score = 0, 1, c.score)) group_rank
      FROM   (
        SELECT ca.team_home_id team_id, (ca.score_home-ca.score_away) score
        FROM   matches ca, 
               (SELECT cba.team_id 
                FROM league_tables cba 
                WHERE cba.points = #{group_points}
               ) cb
        WHERE  ca.team_home_id = cb.team_id  AND ca.score_home >= ca.score_away
        UNION
        SELECT cc.team_away_id team_id, (cc.score_away-cc.score_home) score
        FROM   matches cc, 
               (SELECT cda.team_id 
                FROM league_tables cda 
                WHERE cda.points = #{group_points}
               ) cd
        WHERE  cc.team_away_id = cd.team_id AND cc.score_away >= cc.score_home
               ) c
        GROUP BY c.team_id
      ) b ON league_tables.team_id = b.team_id
      SET league_tables.group_rank = b.group_rank"
      connection.execute(sql)
      return true
  end
end

Make sure to add an index on the points column.

Note: This solution will work in MySQL. It is fairly straight forward to rewrite the SQL to work with other databases.

I think it is hard to do this using database sort. Precalculating a cross table with points between the teams is possible, but how to use it in the search. I imagine the problem is even harder if three teams tie.

Sort the things you can from the database. Then go through the list again to sort out the ties. You must calculate the tie-breaker for the affected teams. Either you put the teams into a new array from top to bottom, or add a tie-break column to the teams, and resort in a second pass.

I would add a method to your model class who resolves the tie breaks and returns a sorted array.

The task is non-trivial, but could be fun.

your problem sounds really interesting. I have played a lot of competition (volleybal) and in case of equal points (where points are earned based on matches won or lost), the team with the most points, and the least counterpoints would be sorted first. So in this case, instead of really looking at the individual matches, just sort on the total goals-won and -lost.

So that would be easy then:

LeagueTable.all.order('points desc, goals_won desc, goals_lost desc')

which i think would be a pretty decent order. The most offensive team overall is then chosen. You also prefer the most defensive team by sorting on order('points desc, goals_lost desc, goals_won desc').

But this is merely a shortcut. I suppose you are not free to change the sorting rules as you wish, and it is really nice problem to crack. Here is some code how i would approach it

all_teams_simple_sort = LeagueTable.all.sort('points desc')
all_teams_sorted = []

teams_equal_points = []
prev_team = all_teams_simple_sort[1]
prev_points = all_teams_simple_sort[1].points

(2..all_teams_simple_sort.size).each do |team_index|
  team = all_teams_simple_sort[team_index]
  if team.points == prev_team.points
    teams_equal_points << prev_team if teams_equal_points.size == 0
    teams_equal_points << team
  else        
    if teams_equal_points.size > 0
      add_equals_sorted_to all_teams_sorted, teams_equal_sorted
      teams_equal_sorted = []
    else
      all_teams_sorted << prev_team
    end
    all_teams_sorted << team
  end
  prev_team = team   
end

This should walk over all teams, combine all teams with equal points and add all other if needed.

Now we only need to write the hardest function add_equals_sorted_to that will add the teams with equal points in the correct order to the result-sort.

def add_equals_sorted_to(result_sorted, equals_unsorted)
  team_ids = equals_unsorted.collect(&:team_id)
  # get all the matches for between those teams
  matches = Match.where('team_home_id in (?) and team_away_id in (?)', team_ids.join(','), team_ids.join(','))

  # create an empty hash for each team
  team_score = {}
  team_ids.each {|id| team_scores[id] = {:won => 0, :lost => 0} }
  matches.each do |match|
    team_scores[match.team_home_id] = {:won => team_scores[match.team_home_id][:won] + match.score_home, :lost => team_scores[match.team_home_id][:lost] + match.score_away }
    team_scores[match.team_away_id] = {:won => team_scores[match.team_away_id][:won] + match.score_away, :lost => team_scores[match.team_home_id][:lost] + match.score_home }
  end

  # get the team with the highest :won and add to result_sorted 
  #   and repeat until no more left   
end

This code is not tested :) But I hope it should get you started.