Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Expected Dice by Kurush
# migrated from python 2.7
# My solution is based on absorbing discrete Markov chains.
# First of all I calculate transition matrix.
# Then I calculate the submatrix Q with transient states by elimination target absorbing state.
# The required expectation is (I - Q)^(-1) * || 1 ... 1 ||.
# For calculation of inverse matrix standard Gauss method was used.
import copy
def expected(dice_number, sides, target, board):
probabilities = []
get_probabilities(dice_number, sides, board, probabilities)
eliminate_absorbing_state(probabilities, target)
identity_matrix = [[1 if j == i else 0 for j in range(len(probabilities))] for i in range(len(probabilities))]
fundamental_matrix = subtract_matrix_from_matrix(identity_matrix, probabilities)
inverse_matrix = find_inverse_matrix(fundamental_matrix)
one_vector = [1 for i in range(len(inverse_matrix))]
res_vector = mult_matrix_vector(inverse_matrix, one_vector)
return res_vector[0]
# calculate probability to move from i to j in one move
def get_probabilities(dice_number, sides, board, probabilities):
for i in range(len(board)):
probabilities.append([])
res_moves = [0 for k in range(len(board))]
sum_list = []
fill_list(dice_number, sides, 1, 0, sum_list)
for l in sum_list:
current = (i + l) % len(board)
while board[current] != 0:
current = (current + board[current]) % len(board)
res_moves[current] += 1
for j in range(len(board)):
probabilities[i].append((res_moves[j] * 1.0) / (sides**dice_number))
def fill_list(dice_number, sides, current_dice, sum, sum_list):
for i in range(1, sides + 1):
if current_dice + 1 <= dice_number:
fill_list(dice_number, sides, current_dice + 1, sum + i, sum_list)
else:
sum_list.append(sum + i)
def eliminate_absorbing_state(matrix, index):
matrix.pop(index)
for i in range(len(matrix)):
matrix[i].pop(index)
def find_inverse_matrix(matrix):
identity_matrix = [[1 if j == i else 0 for j in range(len(matrix))] for i in range(len(matrix))]
new_matrix = [sum(list(i), []) for i in zip(matrix, identity_matrix)]
for l in range(len(new_matrix)):
if new_matrix[l][l] == 0:
for i in range(l, len(new_matrix)):
if new_matrix[i][l] != 0:
swap_rows(new_matrix, i, l)
break
value = new_matrix[l][l]
multiply_row_factor(value, new_matrix[l])
subtract_current_row(l, new_matrix[l], new_matrix)
return [new_matrix[i][len(new_matrix):] for i in range(len(new_matrix))]
def multiply_row_factor(factor, row):
for i in range(len(row)):
row[i] = row[i] / factor
def subtract_current_row(index, row, matrix):
for i in range(len(matrix)):
if i != index:
factor = matrix[i][index] / row[index]
for j in range(len(matrix[i])):
matrix[i][j] -= factor * row[j]
def swap_rows(matrix, i, l):
c = matrix[i]
matrix[i] = matrix[l]
matrix[l] = c
def mult_matrix_vector(matrix, vector):
res_vector = []
for i in range(len(matrix)):
sum = 0
for j in range(len(matrix[i])):
sum += matrix[i][j] * vector[j]
res_vector.append(sum)
return res_vector
def subtract_matrix_from_matrix(m1, m2):
new_matrix = copy.deepcopy(m1)
for i in range(len(m1)):
for j in range(len(m1[0])):
new_matrix[i][j] = m1[i][j] - m2[i][j]
return new_matrix
if __name__ == '__main__':
#These are only used for self-checking and are not necessary for auto-testing
def almost_equal(checked, correct, significant_digits=1):
precision = 0.1 ** significant_digits
return correct - precision < checked < correct + precision
assert(almost_equal(expected(1, 4, 3, [0, 0, 0, 0]), 4.0))
assert(almost_equal(expected(1, 4, 1, [0, 0, 0, 0]), 4.0))
assert(almost_equal(expected(1, 4, 3, [0, 2, 1, 0]), 1.3))
assert(almost_equal(expected(1, 4, 3, [0, -1, -2, 0]), 4.0))
assert(almost_equal(expected(1, 6, 1, [0] * 10), 8.6))
assert(almost_equal(expected(2, 6, 1, [0] * 10), 10.2))
June 24, 2014
Comments:
