probabilities.rb in games_dice-0.2.4

- old
+ new

@@ -19,56 +19,70 @@
 #  probs.p_ge( 10 ) # => 0.16666666666666669
 #
 class GamesDice::Probabilities
 
   # Creates new instance of GamesDice::Probabilities.
-  # @param [Hash] prob_hash A hash representation of the distribution, each key is an integer result,
-  #   and the matching value is probability of getting that result
+  # @param [Array<Float>] probs Each entry in the array is the probability of getting a result
+  # @param [Integer] offset The result associated with index of 0 in the array
   # @return [GamesDice::Probabilities]
-  def initialize( prob_hash = { 0 => 1.0 } )
+  def initialize( probs = [1.0], offset = 0 )
     # This should *probably* be validated in future, but that would impact performance
-    @ph = prob_hash
+    @probs = probs
+    @offset = offset
   end
 
   # @!visibility private
-  # the Hash representation of probabilities.
-  attr_reader :ph
+  # the Array, Offset representation of probabilities.
+  def to_ao
+    [ @probs, @offset ]
+  end
 
+  # Iterates through value, probability pairs
+  # @yieldparam [Integer] result A result that may be possible in the dice scheme
+  # @yieldparam [Float] probability Probability of result, in range 0.0..1.0
+  # @return [GamesDice::Probabilities] this object
+  def each
+    @probs.each_with_index { |p,i| yield( i+@offset, p ) }
+    return self
+  end
+
   # A hash representation of the distribution. Each key is an integer result,
   # and the matching value is probability of getting that result. A new hash is generated on each
   # call to this method.
   # @return [Hash]
   def to_h
-    @ph.clone
+    GamesDice::Probabilities.prob_ao_to_h( @probs, @offset )
   end
 
   # @!attribute [r] min
   # Minimum result in the distribution
   # @return [Integer]
   def min
-    (@minmax ||= @ph.keys.minmax )[0]
+    @offset
   end
 
   # @!attribute [r] max
   # Maximum result in the distribution
   # @return [Integer]
   def max
-    (@minmax ||= @ph.keys.minmax )[1]
+    @offset + @probs.count() - 1
   end
 
   # @!attribute [r] expected
   # Expected value of distribution.
   # @return [Float]
   def expected
-    @expected ||= @ph.inject(0.0) { |accumulate,p| accumulate + p[0] * p[1] }
+    @expected ||= calc_expected
   end
 
   # Probability of result equalling specific target
   # @param [Integer] target
   # @return [Float] in range (0.0..1.0)
   def p_eql target
-    @ph[ Integer(target) ] || 0.0
+    i = Integer(target) - @offset
+    return 0.0 if i < 0 || i >= @probs.count
+    @probs[ i ]
   end
 
   # Probability of result being greater than specific target
   # @param [Integer] target
   # @return [Float] in range (0.0..1.0)
@@ -84,11 +98,11 @@
     return @prob_ge[target] if @prob_ge && @prob_ge[target]
     @prob_ge = {} unless @prob_ge
 
     return 1.0 if target <= min
     return 0.0 if target > max
-    @prob_ge[target] = @ph.select {|k,v| target <= k}.inject(0.0) {|so_far,pv| so_far + pv[1] }
+    @prob_ge[target] = @probs[target-@offset,@probs.count-1].inject(0.0) {|so_far,p| so_far + p }
   end
 
   # Probability of result being equal to or less than specific target
   # @param [Integer] target
   # @return [Float] in range (0.0..1.0)
@@ -97,64 +111,162 @@
     return @prob_le[target] if @prob_le && @prob_le[target]
     @prob_le = {} unless @prob_le
 
     return 1.0 if target >= max
     return 0.0 if target < min
-    @prob_le[target] = @ph.select {|k,v| target >= k}.inject(0.0) {|so_far,pv| so_far + pv[1] }
+    @prob_le[target] = @probs[0,1+target-@offset].inject(0.0) {|so_far,p| so_far + p }
   end
 
   # Probability of result being less than specific target
   # @param [Integer] target
   # @return [Float] in range (0.0..1.0)
   def p_lt target
     p_le( Integer(target) - 1 )
   end
 
+  # Probability distribution derived from this one, where we know (or are only interested in
+  # situations where) the result is greater than or equal to target.
+  # @param [Integer] target
+  # @return [GamesDice::Probabilities] new distribution.
+  def given_ge target
+    target = Integer(target)
+    target = min if min > target
+    p = p_ge(target)
+    raise "There is no valid distribution given a result >= #{target}" unless p > 0.0
+    mult = 1.0/p
+    new_probs = @probs[target-@offset,@probs.count-1].map { |x| x * mult }
+    GamesDice::Probabilities.new( new_probs, target )
+  end
+
+  # Probability distribution derived from this one, where we know (or are only interested in
+  # situations where) the result is less than or equal to target.
+  # @param [Integer] target
+  # @return [GamesDice::Probabilities] new distribution.
+  def given_le target
+    target = Integer(target)
+    target = max if max < target
+    p = p_le(target)
+    raise "There is no valid distribution given a result <= #{target}" unless p > 0.0
+    mult = 1.0/p
+    new_probs = @probs[0..target-@offset].map { |x| x * mult }
+    GamesDice::Probabilities.new( new_probs, @offset )
+  end
+
+  # Creates new instance of GamesDice::Probabilities.
+  # @param [Hash] prob_hash A hash representation of the distribution, each key is an integer result,
+  #   and the matching value is probability of getting that result
+  # @return [GamesDice::Probabilities]
+  def self.from_h prob_hash
+    probs, offset = prob_h_to_ao( prob_hash )
+    GamesDice::Probabilities.new( probs, offset )
+  end
+
   # Distribution for a die with equal chance of rolling 1..N
   # @param [Integer] sides Number of sides on die
   # @return [GamesDice::Probabilities]
   def self.for_fair_die sides
     sides = Integer(sides)
     raise ArgumentError, "sides must be at least 1" unless sides > 0
-    h = {}
-    p = 1.0/sides
-    (1..sides).each { |x| h[x] = p }
-    GamesDice::Probabilities.new( h )
+    GamesDice::Probabilities.new( Array.new( sides, 1.0/sides ), 1 )
   end
 
   # Combines two distributions to create a third, that represents the distribution created when adding
   # results together.
   # @param [GamesDice::Probabilities] pd_a First distribution
   # @param [GamesDice::Probabilities] pd_b Second distribution
   # @return [GamesDice::Probabilities]
   def self.add_distributions pd_a, pd_b
-    h = {}
-    pd_a.ph.each do |ka,pa|
-      pd_b.ph.each do |kb,pb|
-        kc = ka + kb
+    combined_min = pd_a.min + pd_b.min
+    combined_max = pd_a.max + pd_b.max
+    new_probs = Array.new( 1 + combined_max - combined_min, 0.0 )
+    probs_a, offset_a = pd_a.to_ao
+    probs_b, offset_b = pd_b.to_ao
+
+    probs_a.each_with_index do |pa,i|
+      probs_b.each_with_index do |pb,j|
+        k = i + j
         pc = pa * pb
-        h[kc] = h[kc] ? h[kc] + pc : pc
+        new_probs[ k ] += pc
       end
     end
-    GamesDice::Probabilities.new( h )
+    GamesDice::Probabilities.new( new_probs, combined_min )
   end
 
   # Combines two distributions with multipliers to create a third, that represents the distribution
   # created when adding weighted results together.
   # @param [Integer] m_a Weighting for first distribution
   # @param [GamesDice::Probabilities] pd_a First distribution
   # @param [Integer] m_b Weighting for second distribution
   # @param [GamesDice::Probabilities] pd_b Second distribution
   # @return [GamesDice::Probabilities]
   def self.add_distributions_mult m_a, pd_a, m_b, pd_b
-    h = {}
-    pd_a.ph.each do |ka,pa|
-      pd_b.ph.each do |kb,pb|
-        kc = m_a * ka + m_b * kb
+    combined_min, combined_max = [
+      m_a * pd_a.min + m_b * pd_b.min, m_a * pd_a.max + m_b * pd_b.min,
+      m_a * pd_a.min + m_b * pd_b.max, m_a * pd_a.max + m_b * pd_b.max,
+      ].minmax
+
+    new_probs = Array.new( 1 + combined_max - combined_min, 0.0 )
+    probs_a, offset_a = pd_a.to_ao
+    probs_b, offset_b = pd_b.to_ao
+
+    probs_a.each_with_index do |pa,i|
+      probs_b.each_with_index do |pb,j|
+        k = m_a * (i + offset_a) + m_b * (j + offset_b) - combined_min
         pc = pa * pb
-        h[kc] = h[kc] ? h[kc] + pc : pc
+        new_probs[ k ] += pc
       end
     end
-    GamesDice::Probabilities.new( h )
+    GamesDice::Probabilities.new( new_probs, combined_min )
+  end
+
+
+  # Adds a distribution to itself repeatedly, to simulate a number of dice
+  # results being summed.
+  # @param [GamesDice::Probabilities] pd Distribution to repeat
+  # @param [Integer] n Number of repetitions, must be at least 1
+  # @return [GamesDice::Probabilities]
+  def self.repeat_distribution pd, n
+    n = Integer( n )
+    raise "Cannot combine probabilities less than once" if n < 1
+    revbin = n.to_s(2).reverse.each_char.to_a.map { |c| c == '1' }
+    pd_power = pd
+    pd_result = nil
+    max_power = revbin.count - 1
+
+    revbin.each_with_index do |use_power, i|
+      if use_power
+        if pd_result
+          pd_result = add_distributions( pd_result, pd_power )
+        else
+          pd_result = pd_power
+        end
+      end
+      pd_power = add_distributions( pd_power, pd_power ) unless i == max_power
+    end
+    pd_result
+  end
+
+  private
+
+  # Convert hash to array,offset notation
+  def self.prob_h_to_ao h
+    rmin,rmax = h.keys.minmax
+    o = rmin
+    a = Array.new( 1 + rmax - rmin, 0.0 )
+    h.each { |k,v| a[k-rmin] = v }
+    [a,o]
+  end
+
+  # Convert array,offset notation to hash
+  def self.prob_ao_to_h a, o
+    h = Hash.new
+    a.each_with_index { |v,i| h[i+o] = v if v > 0.0 }
+    h
+  end
+
+  def calc_expected
+    total = 0.0
+    @probs.each_with_index { |v,i| total += (i+@offset)*v }
+    total
   end
 
 end # class GamesDice::Probabilities