Skip to content

Instantly share code, notes, and snippets.

@jakcharlton
Created July 19, 2011 00:45
Show Gist options
  • Save jakcharlton/1091056 to your computer and use it in GitHub Desktop.
Save jakcharlton/1091056 to your computer and use it in GitHub Desktop.
Benchmarking three versions of Ruby Koans scoring algorithm
require 'benchmark'
class Gary
# https://gist.github.com/1089115
def score(dice)
score_counts(dice).inject(0) {|score, pair| score + frequency_score(pair)}
end
def frequency_score(pair)
triple_score(pair) + single_score(pair)
end
def triple_score(pair)
(pair[:count] / 3) * triple_multiplier(pair[:score])
end
def triple_multiplier(score)
score == 1 ? 1000 : score * 100
end
def single_score(pair)
(pair[:count] % 3) * single_multiplier(pair[:score])
end
def single_multiplier(score)
case score
when 1; 100
when 5; 50
else ; 0
end
end
def score_counts(dice)
(1..6).map do |score|
{:score => score, :count => dice.select{|d| d == score}.size}
end
end
end
class Jak
# https://gist.github.com/1088610
def score(dice)
score = 0
return score if dice.empty?
counts = [0,0,0,0,0,0]
dice.each {|d| counts[d-1] += 1 }
ones, twos, threes, fours, fives, sixes = counts
if ones >= 3 then
score += 1000 + ((ones-3) * 100)
else
score += (ones * 100)
end
if fives >= 3 then
score += 500 + ((fives-3) * 50)
else
score += fives * 50
end
score += 200 if twos >= 3
score += 300 if threes >= 3
score += 400 if fours >= 3
score += 600 if sixes >= 3
score
end
end
class Serbrech
# https://gist.github.com/906429
def triple?(dice, val)
dice.count {|die| die == val} >= 3
end
def handle_triples(dice)
return 0 if dice.empty?
return 350 if triple? dice, 5
return 700 if triple? dice, 1
return_value = 0
(2..6).each do |item|
return_value = item * 100 if triple? dice, item
end
return return_value
end
def score(dice)
total = handle_triples dice
dice.each do |die|
total += 50 if die == 5
total += 100 if die == 1
end
total
end
end
class Kevin
# https://gist.github.com/1088913
def score(dice)
# Hash holds values seen in the roll and the number of duplicates for each
h = Hash.new(0)
dice.each { | d | h.store(d, h[d]+1) }
score = 0
score += h[1] * 100
score += 700 if h[1] >= 3 # 1000 bonus points, minus the 3 * 100 points for the 1's in the set
score += 200 if h[2] >= 3
score += 300 if h[3] >= 3
score += 400 if h[4] >= 3
score += h[5] * 50
score += 350 if h[5] >= 3 # 500 bonus points, minus the 3 * 50 points for the 5's in the set
score += 600 if h[6] >= 3
score
end
end
class Glebm
# answer by Glebm at http://codereview.stackexchange.com/questions/423/is-this-good-ruby-ruby-koans-greed-task
def score(dice)
score = 0
# Below is equivalent to:
# counts = dice.inject(Hash.new(0)) { |h, x| h[x] += 1; h }
counts = Hash.new(0)
dice.each do |x|
counts[x] += 1
end
(1..6).each do |i|
if counts[i] >= 3
if i == 1
score += 1000
else
score += 100 * i
end
counts[i] = [counts[i] - 3, 0].max
end
if i == 1
score += 100 * counts[i]
elsif i == 5
score += 50 * counts[i]
end
end
score
end
end
class Felix
# from Felix Alcala http://codereview.stackexchange.com/questions/423/is-this-good-ruby-ruby-koans-greed-task
def score(dice)
patterns = {[1,1,1]=>1000, [2,2,2]=>200, [3,3,3]=>300, [4,4,4]=>400,
[5,5,5]=>500, [6,6,6]=>600, 1=>100, 5=>50}
sorted = dice.sort
triple = patterns[sorted[0..2]]
single = patterns[sorted[0]]
if triple
partial_score = triple
rest = sorted[3..-1]
elsif single
partial_score = single
rest = sorted[1..-1]
else
partial_score = 0
rest = sorted[1..-1]
end
if rest
partial_score + score(rest)
else
partial_score
end
end
end
n = 500000
jak = Jak.new
serbrech = Serbrech.new
gary = Gary.new
kevin = Kevin.new
glebm = Glebm.new
felix = Felix.new
[[], [5], [1], [1,5,5,1], [2,3,4,6], [1,1,1]].each do |to_score|
Benchmark.bm do |x|
puts "Results for: " + to_score.inspect
x.report("jak: ") { for i in 1..n; jak.score(to_score); end }
x.report("serbrech:") { for i in 1..n; serbrech.score(to_score); end }
x.report("gary: ") { for i in 1..n; gary.score(to_score); end }
x.report("kevin: ") { for i in 1..n; kevin.score(to_score); end }
x.report("glebm: ") { for i in 1..n; glebm.score(to_score); end }
x.report("felix: ") { for i in 1..n; felix.score(to_score); end }
puts "-----------------------------------------------------"
end
end
@jakcharlton
Copy link
Author

Added version by Kevin Pang from https://gist.github.com/1088913

Latest benchmarks are

          user     system      total        real
    jak:       0.093000   0.000000   0.093000 (  0.092009)
    serbrech:  0.141000   0.000000   0.141000 (  0.151015)
    gary:      5.117000   0.000000   5.117000 (  5.110511)
    kevin:     0.873000   0.000000   0.873000 (  0.872087)
          user     system      total        real
    jak:       0.437000   0.000000   0.437000 (  0.444044)
    serbrech:  1.170000   0.000000   1.170000 (  1.160116)
    gary:      5.538000   0.000000   5.538000 (  5.537554)
    kevin:     1.014000   0.000000   1.014000 (  1.019102)
          user     system      total        real
    jak:       0.452000   0.000000   0.452000 (  0.445044)
    serbrech:  1.155000   0.000000   1.155000 (  1.162116)
    gary:      5.429000   0.000000   5.429000 (  5.425543)
    kevin:     1.014000   0.000000   1.014000 (  1.014101)
          user     system      total        real
    jak:       0.686000   0.000000   0.686000 (  0.681068)
    serbrech:  2.168000   0.000000   2.168000 (  2.175218)
    gary:      6.537000   0.000000   6.537000 (  6.557655)
    kevin:     1.373000   0.000000   1.373000 (  1.364137)
          user     system      total        real
    jak:       0.671000   0.000000   0.671000 (  0.676067)
    serbrech:  2.137000   0.000000   2.137000 (  2.130213)
    gary:      6.505000   0.000000   6.505000 (  6.534653)
    kevin:     1.482000   0.015000   1.497000 (  1.498150)
          user     system      total        real
    jak:       0.608000   0.000000   0.608000 (  0.618062)
    serbrech:  0.702000   0.000000   0.702000 (  0.698069)
    gary:      5.944000   0.000000   5.944000 (  5.946595)
    kevin:     1.232000   0.000000   1.232000 (  1.231123)

@jakcharlton
Copy link
Author

Added two more versions, all I could find on Google, from http://codereview.stackexchange.com/questions/423/is-this-good-ruby-ruby-koans-greed-task

@ragesoss
Copy link

Thanks for posting this! Here's my version (not particularly fast). The one tiny improvement over the jak version is to put the guard clause at the very top, which shaves off a fraction for the empty case.

class Sage
  def score(dice)
    return 0 if dice.empty?
    score = 0
    # ones
    ones = dice.find_all { |x| x == 1 }
    ones_score = [0, 100, 200, 1000, 1100, 1200]
    score += ones_score[ones.count]
    # fives
    fives = dice.find_all { |x| x == 5 }
    fives_score = [0, 50, 100, 500, 550, 600]
    score += fives_score[fives.count]
    # others
    [2, 3, 4, 6].each do |y|
      y_array = dice.find_all { |x| x == y }
      if y_array.count >= 3
        score += y * 100
      end
    end
    score
  end
end

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment