CodeIQ「スロットマシン問題」に挑戦したようです

codeiq.jp

問題

n 個のリール（数字が描かれている部分です）を持つスロットマシンを回します。

各リールには、0 から 9 のいずれかの数字がランダムに出ます。

このとき、「最も多く出現した数字の出現回数」に等しいドルが賞金として得られます。

例えば n = 6 のスロットマシンを考えましょう。

各リールに、左から順に 7 7 5 1 0 7 という数字が出たとします。

このとき、7 の数字が最も多く 3 回出現していますので、賞金は 3 ドルです。

このスロットマシンを 1 回まわしたときの賞金の期待値を F(n)  とします。

例えば F(1) = 1，F(2) = 1.1，F(3) = 1.29 となることが確かめられます。


■ 第１問 （Normal）

F(6) の値を求めて下さい（四捨五入は不要です）。

■ 第２問 （Hard）

F(12) の値を求めて下さい（四捨五入は不要です）。

提出したコード

def fact(n)
  result = 1
  1.upto(n){|i| result *= i}
  result
end

def c(n, r)
  fact(n)/(fact(n-r)*fact(r))
end

#配列の値を計算
def calcArray(arr, n)
  sum = 0
  num = 10
  r = n
  result = 1
  count = Array.new(n+1, 0)
  
  #2つ以上ある要素を掛ける
  arr.each do |v|
    if v > 1
      sum += v
      result *= num * c(r, v)
      count[v] += 1
      num -= 1
      r -= v
    end
  end
  
  #1つしかない要素を掛ける
  (sum+1).upto(n) do |i|
    result *= num
    num -= 1
  end

  #重複の排除
  count.each {|v| result /= fact(v)}
  
  result
end

#分割を列挙し、パターンごとに組み合わせの数を計算する
def calcPartition(arr, n, p, index, sum)
  return 0 if arr.size <= index
  
  result = 0
  arr[index] = 2
  sum += 2
  
  while arr[index] <= p && sum <= n
    result += calcArray(arr, n)
    result += calcPartition(arr, n, arr[index], index+1, sum)
    
    arr[index] += 1
    (index+1).upto(arr.size-1){|i| arr[i] = 0}
  end
  result
end

#期待値を求める
def f(n)
  i = 1
  result = 0
  
  while i <= n
    arr = Array.new(n, 0)
    arr[0] = i
    sum = calcArray(arr, n)
    sum += calcPartition(arr, n, i, 1, i)
    result += sum.to_f * i / 10 ** n
    i += 1
  end
  result
end

p f(1)
p f(2)
p f(3)
p f(6)
p f(12)

rubyで。

方針

貰える賞金にはリールの数値や数値の位置は関係ないので、同じ数値が何回出てくるかのパターンを考える。
例えばn=4の時は1:すべて同じ、2:3つ同じ、3:2つ同じの組み合わせが2つ、4:2つだけ同じで残りがバラバラ、5:全て違う、の5通りある。
1桁を1文字で表すと以下のような感じ。

1:AAAA
2:AAAB
3:AABB
4:AABC
5:ABCD

各パターンを同じ数字の個数に注目して以下のように表すと、nを適当な正の整数の足し算で表すパターンの列挙になる。
こういうのを分割と言うらしい。

1:4
2:3+1
3:2+2
4:2+1+1
5:1+1+1+1

これらのパターンの列挙さえ出来れば、あとは単純に期待値を求める問題だけど、このパターン列挙が難しかった。

色々試したらnを分割する際の一番大きい数字(スロットを回した時の得点)をpとして、残りのn-pをp以下の数で分割するパターンを再帰的に探す方法で何とかうまくいった。

他の人の回答

togetter.com
そういえばrubyにはinjectとかそういった便利なメソッドがありましたね…。折角ruby使ってるのに全然使いこなせてないので頑張って使いこなしたい。