Sumatosoft task.

dicebility.rb

# Sumatosoft task:
#   Find probability of sum of thrown dice.
# Input:
#   M - dice count (positive integer)
#   N - sum (positive integer)
# Output:
#   probability (rounded)
#
# Solution:
#   Probability equals to count valid permutations of dice values for
#   sum divided by all possible permutations of dice values.
#
#   All possible permutations is 6 in dice count factor (6**dice_count).
#
#   Count of dice values permutations for sum is binomial coefficient.
#   Dice count and sum is diagonal and row in Passcal's triangle - it is
#   parameters to calculate binomial coefficient.
#
#   But because of limits for dice value (from 1 to 6), there are sum
#   values which cannot be created with every dice value for each dice.
#   For example with 3 dice, and sum 9; when the first dice has value 1
#   and the second dice has value 1, the third dice should have value 7.
#   And this is impossible. So count of permutations is not correct
#   binomial coefficient. It is correct only for first 6 smallest
#   possible sum (e.g. above it is 3, 4, 5, 6, 7, 8). The next 6
#   sum will have less count of permutations. We need to subtract from
#   result values of binomial coefficient for all lower sum with step 6
#   multiplied by values of sum starting with second possible.
#
#   Formula looks like:
#     F(sum) = BK - S(k=1..last) [ F(f_p_sum + k) * F(sum - 6*k) ) ]
#   Where:
#     F(sum) - is function to find correct count of permutations for sum
#     BK - is binomial coefficient
#     S(k=1..last) [ ... ] - is sum of 'k' values in []
#     last - is last time calculating value in []. which is
#            when (sum - 6*last) give one of first smallest sum
#     f_p_sum - is first possible sum which equals dice count
#
#   Example 1: dice count is 3, sum is 11
#   F(11) = BK - (F(3+1)*F(11-6)) = BK - (F(4)*F(5))
#
#   Example 2: dice count is 10, sum is 31
#   F(31) = BK - (F(11)*F(25) + F(12)*F(19) + F(13)*F(13))
#
#   NOTE: Cause there is a lot of F(sum) calculations, it is good idea
#         to cache result of those to be used next time it is needed!!
#         With caching there will be something like O(k) calculations
#         of F(sum), instead of something like O(2^k) calculations of
#         F(sum) without cache. 'k' is parameter from previous formula.
#         E.g. when dice count is 10 and sum is 31, with cache there
#         are O(3) calculations, instead of 0(2^3) = O(8) without cache.
#         And with dice count is 100 and sum is 345, with cache there
#         are O(40) calculations, instead of without cache
#         O(2^40) ~ O(1_000_000_000_000) calculations.
#
#   Solution performance for cpu is O(k) and for memory O(k). Yey!! :)
#

DICE_MAX_VALUE = 6
PERMUT_CACHE = {}

def binomial_coefficient(n, m)
  ((n - m + 1)..n).inject(&:*) / (1..m).inject(&:*)
end

def valid_permutations_count(dice_count, sum)
  return PERMUT_CACHE[[dice_count, sum]] if PERMUT_CACHE[[dice_count, sum]]
  original_sum = sum
  result = binomial_coefficient(sum - 1, dice_count - 1)

  # correct result
  correction_count = (sum - dice_count) / DICE_MAX_VALUE
  (1..correction_count).each do |k|
    sum -= DICE_MAX_VALUE
    result -= valid_permutations_count(dice_count,  k + dice_count) * valid_permutations_count(dice_count, sum)
  end

  PERMUT_CACHE[[dice_count, original_sum]] = result
end

def calculate_probability(dice_count, sum)
  # not real variants
  return 0 if (sum < dice_count) || (sum > (DICE_MAX_VALUE * dice_count))

  # use symmetry for sum value
  temp = dice_count * (DICE_MAX_VALUE + 1)
  sum = temp - sum if sum > temp / 2

  # do not count valid permutations with one dice
  permutations_count = (dice_count == 1 || sum == dice_count) ? 1 : valid_permutations_count(dice_count, sum)
  permutations_count / (DICE_MAX_VALUE**dice_count).to_f
end

puts "Give me dice count (M)"
dice_count = gets.to_i
while dice_count < 1
  puts "Try again. Dice count (M) should be positive integer"
  dice_count = gets.to_i
end

puts "Give me sum (N)"
sum = gets.to_i
while sum < 1
  puts "Try again. Sum (N) should be positive integer"
  sum = gets.to_i
end

puts "Probability: #{calculate_probability(dice_count, sum)}"