test.rb

#---
# Author::  Ian Yang
# Created:: <2010-05-24 16:18:23>
#+++
#
require 'pp'

def optimal_choise(diff)
  optimal_value = 0
  optimal_index = 0

  current_value = 0
  (1..6).each do |i|
    current_value = current_value + diff - (9 * i)
    if current_value > optimal_value
      optimal_index = i
      optimal_value = current_value
    end
  end

  optimal_index
end

M = 8
N = 4
E = [1, 2, 3, 4, 5, 6].reduce(:+) / 6.0

$expectations = Array.new(M + 1) {Array.new(N + 1, -1)}
$choices = Array.new(M + 1) {Array.new(N + 1, -1)}

$expectations.each_with_index do |row, i|
  row[0] = i * E
  if i < row.length
    row[i] = 10 * i * E
  end
end
$choices.each_with_index do |row, i|
  row[0] = 6
  if i < row.length
    row[i] = 0
  end
end

def calculate(m, n)
  calculate(m - 1, n) if $expectations[m - 1][n] < 0
  calculate(m - 1, n - 1) if $expectations[m - 1][n - 1] < 0

  diff = $expectations[m - 1][n] - $expectations[m - 1][n - 1]
  $choices[m][n] = optimal_choise(diff)

  $expectations[m][n] = 0
  if $choices[m][n] > 0
    $expectations[m][n] += $choices[m][n] * diff
    $expectations[m][n] -= 9 * ($choices[m][n] * ($choices[m][n] + 1)) / 2
  end
  $expectations[m][n] /= 6.0
  $expectations[m][n] += 35 + $expectations[m - 1][n - 1]
end

calculate(8, 4)

def get_result(*sequence)
  sequence = sequence.flatten.compact
  m = 8
  n = 4

  result = Array.new(4, 0)
  sequence.each do |i|
    if i <= $choices[m][n]
      result[m - n - 1] += i
    else
      result[n - 1] += i * 10
      n -= 1
    end
    m -= 1
  end
  result
end

pp $expectations
pp $choices

sum = 0
10000.times do |i|
  input = []
  8.times { input << (rand(6) + 1) }
  r = get_result(input)
  if i % 1000 == 0
    p ">>> #{i} <<<"
    p input
    p r
  end
  sum += r.inject(:+)
end

p sum / 10000.0