class Object

# File lib/systems/baldwin.rb, line 1
def baldwin votes
  votes, options = normalize votes
  while true
    # calculate scores using Borda counts
    scores = borda_counts votes, options
    # group and sort the options by score
    groups = options.group_by {|option| scores[option]}
    sorted = groups.sort_by {|score, tied| -score}
    # puts
    # sorted.each {|score, tied| puts "#{score.to_f} #{tied}"}
    # find the options with the lowest score
    leasts = sorted.last[1]
    # if all remaining options are tied, they are the winners
    return leasts if leasts.size == options.size
    # remove the options with the lowest score
    votes.collect! {|count, ranking|
      [count, ranking.collect {|tied| tied - leasts}]
    }
    options -= leasts
  end
end

# File lib/systems/borda.rb, line 1
def borda votes
  votes, options = normalize votes
  # calculate scores using Borda counts
  scores = borda_counts votes, options
  # sort the results and return the winner/s
  groups = options.group_by {|option| scores[option]}
  sorted = groups.sort_by {|score, tied| -score}
  # sorted.each {|score, tied| puts "#{score.to_f} #{tied}"}
  sorted.first[1]
end

# File lib/util.rb, line 1
def borda_counts votes, options
  # calculate the Borda count of each option
  scores = Hash.new 0
  votes.each {|count, ranking|
    # add to the scores
    remaining = options.size
    ranking.each_with_index {|tied, i|
      # each tied option gets the average of their possible ranks
      average = remaining - (tied.size - 1) / 2r
      tied.each {|option| scores[option] += count * average}
      remaining -= tied.size
    }
    raise unless remaining == 0 # sanity check
  }
  scores
end

# File lib/systems/bucklin.rb, line 23
def bucklin votes
  votes, options = normalize votes
  sum_of_counts = votes.transpose[0].inject 0, :+
  (1..options.size).each {|places|
    # count the votes up to places
    scores = scores_for_places votes, places
    # find the winners
    groups = options.group_by {|option| scores[option]}
    # p groups
    best = groups.max_by {|score, tied| score}
    # if the best group has a majority, it is the winner
    return best[1] if best[0] > sum_of_counts / 2r
  }
  raise # should never get here, by the pigeonhole principle
end

# File lib/util.rb, line 18
def convert_legrand legrand
  # format from https://www.cse.wustl.edu/~legrand/rbvote/calc.html
  legrand.each_line.collect {|line|
    comment = line.index '#'
    line = line[0...comment] if comment
    fields = line.strip.split ':'
    case fields.size
      when 0 then next
      when 1
        # no count provided, so default to 1
        count = 1
        ranks = fields[0]
      when 2
        count = fields[0].to_i
        ranks = fields[1]
      else raise 'only one colon allowed per line'
    end
    groups = ranks.split '>'
    ranking = groups.collect {|group| group.split '='}
    [count, ranking]
  }.compact
end

# File lib/systems/coombs.rb, line 1
def coombs votes
  # this implements the version of Coombs in which elimination proceeds
  # regardless of whether a candidate is ranked first by a majority of voters
  votes, remaining = normalize votes
  while true
    votes.each {|count, ranking| ranking.delete []}
    # p votes

    # see how many times each option was ranked last
    scores = Hash.new 0
    votes.each {|count, ranking|
      tied = ranking.last
      tied.each {|option| scores[option] += count.quo tied.size}
    }

    # find the options which were ranked last the most
    groups = remaining.group_by {|option| scores[option]}
    # p groups
    mosts = groups.max_by {|score, tied| score}[1]

    # if all remaining options are tied, they are the winners
    return mosts if mosts.size == remaining.size

    # remove options which were ranked last the most
    votes.collect! {|count, ranking|
      [count, ranking.collect {|tied| tied - mosts}]
    }
    remaining -= mosts
  end
end

# File lib/systems/copeland.rb, line 1
def copeland votes
  # implements standard Copeland (pairwise victories minus pairwise defeats)
  votes, options = normalize votes
  scores = winning_votes votes # how many times each option beat each other option
  # puts "scores: #{scores}"
  # calculate pairwise victories and pairwise defeats
  victories, defeats = {}, {}
  options.each {|option1|
    victories[option1] = options.select {|option2|
      scores[[option1, option2]] > scores[[option2, option1]]
    }
    defeats[option1] = options.select {|option2|
      scores[[option1, option2]] < scores[[option2, option1]]
    }
  }
  # puts "victories: #{victories}"
  # puts "defeats: #{defeats}"
  # calculate results
  groups = options.group_by {|option|
    victories[option].size - defeats[option].size
  }
  sorted = groups.sort_by {|margin, tied| -margin}
  # puts 'results:'
  # sorted.each {|margin, tied| puts "  #{tied} --> #{margin}"}
  sorted.first[1]
end

# File lib/systems/instant_runoff.rb, line 1
def instant_runoff votes
  votes, remaining = normalize votes
  while true
    votes.each {|count, ranking| ranking.delete []}
    # p votes

    # see how many times each option was ranked first
    scores = Hash.new 0
    votes.each {|count, ranking|
      tied = ranking.first
      tied.each {|option| scores[option] += count.quo tied.size}
    }

    # find the options which were ranked first the least
    groups = remaining.group_by {|option| scores[option]}
    # p groups
    leasts = groups.min_by {|score, tied| score}[1]

    # if all remaining options are tied, they are the winners
    return leasts if leasts.size == remaining.size

    # remove options which were ranked first the least
    votes.collect! {|count, ranking|
      [count, ranking.collect {|tied| tied - leasts}]
    }
    remaining -= leasts
  end
end

# File lib/util.rb, line 41
def normalize votes
  # normalize votes and return along with all options that appeared
  votes = convert_legrand votes if votes.is_a? String
  raise 'votes must contain at least one option' if votes.empty?
  raise 'each vote must have the form [count, ranking]' if votes.find {|vote| vote.size != 2}
  options = votes.transpose[1].flatten.uniq
  votes = votes.collect {|count, ranking|
    raise 'ranking must be an array' unless ranking.is_a? Array
    # treat missing options as tied for last place
    missing = options - ranking.flatten
    ranking = ranking + [missing] unless missing.empty?
    # make sure no options appear twice
    raise 'duplicate option in ranking' unless ranking.flatten.size == options.size
    # normalize single ranks as singleton ties
    ranking = ranking.collect {|x| x.is_a?(Array) ? x : [x]}
    # remove empty ties
    ranking = ranking.select {|tied| not tied.empty?}
    [count, ranking]
  }
  [votes, options]
end

# File lib/systems/ranked_pairs.rb, line 48
def ranked_pairs votes
  votes, options = normalize votes
        scores = winning_votes votes # how many times each option beat each other option
        return options if scores.empty? # every vote ranked all the options the same
  # group and sort the pairs by winning votes
  groups = scores.keys.group_by {|key| scores[key]}
  sorted = groups.sort_by {|winning_votes, pairs| -winning_votes}
        # puts
  # p sorted
  sorted_pairs = sorted.transpose[1]
  # puts
        # puts 'sorted pairs:'
  # sorted_pairs.each {|tied| p tied}
  # puts
        # puts 'calculating results...'
        results = results_from_pairs sorted_pairs
        results.first.to_a
end

# File lib/systems/ranked_pairs.rb, line 19
def results_from_pairs sorted_pairs
        graph = RGL::DirectedAdjacencyGraph.new
        sorted_pairs.each {|tied|
                # puts
                # puts "graph is: "
                # puts graph
                # puts "tied is #{tied}"
                keep = tied.select {|winner, loser|
                        # keep if there is no path from loser to winner, meaning that this edge
                        # will not create a cycle
                        next true if not graph.has_vertex? loser
                        not graph.bfs_iterator(loser).include? winner
                }
                # puts "keep is #{keep}"
                keep.each {|winner, loser| graph.add_edge winner, loser}
        }
        # puts "final graph is: "
        # puts graph
        # puts
        condensed = graph.condensation_graph
        # puts "condensed is "
        # condensed.edges.each {|edge| p edge.to_a}
        # puts
        results = condensed.topsort_iterator.to_a # should be unique
        # puts "results is "
        # p results
        results
end

# File lib/systems/bucklin.rb, line 1
def scores_for_places votes, places
  # Add up votes for each option, including 1st-place votes, 2nd-place votes,
  # and so on up to k-place votes, where k = places.
  scores = Hash.new 0
  votes.each {|count, ranking|
    remaining = places
    ranking.each {|tied|
      if remaining > tied.size
        # each tied option uses up one "place"
        tied.each {|option| scores[option] += count}
        remaining -= tied.size
      else
        # not enough remaining "places" to go around, so give each tied option
        # an equal fraction of what there is
        tied.each {|option| scores[option] += count * (remaining.quo tied.size)}
        break
      end
    }
  }
  scores
end

# File lib/util.rb, line 63
def winning_votes votes
  # see how many times each option beat each other option
  scores = Hash.new 0
  votes.each {|count, ranking|
    (0...ranking.size).each {|i|
      (i+1...ranking.size).each {|j|
        ranking[i].each {|option1|
          ranking[j].each {|option2|
            scores[[option1, option2]] += count
          }
        }
      }
    }
  }
  scores
end