We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Artificial Intelligence
  3. Statistics and Machine Learning
  4. Markov's Snakes And Ladders
  5. Discussions

Markov's Snakes And Ladders

Sort by

recency

|

24 Discussions

|

  • francesco_batto1
     + 0 comments
    import random

def make_dice(prob):

    cum_prob = [0]*6
    sum_prob = 0
    for i,p in enumerate(prob):
        sum_prob += p
        cum_prob[i] = sum_prob
    
    return cum_prob

def roll_dice(cum_prob):

    num = None
    x = random.random() 
    if x > cum_prob[4]:
        num = 6
    elif x > cum_prob[3]:
        num = 5
    elif x > cum_prob[2]:
        num = 4
    elif x > cum_prob[1]:
        num = 3
    elif x > cum_prob[0]:
        num = 2
    else:
        num = 1
    
    return num

def play_game(prob, move):

    cum_prob = make_dice(prob)

    pos = 1
    for count in range(1,1001):

        num = roll_dice(cum_prob)
        pos += num

        if pos==100:
            break
        if pos>100:
            pos -= num
        if move[pos]:
            pos = move[pos]
    
    return count

# read input data
size = 100
n_tests = int(input())
tests = []
for _ in range(n_tests):
    test = {}
    line = input()
    test['prob'] = list(map(float, line.split(',')))

    input()

    test['move'] = [False]*size
    line = input()
    for p in line.split():
        start,end = map(int, p.split(','))
        test['move'][start] = end

    line = input()
    for p in line.split():
        start,end = map(int, p.split(','))
        test['move'][start] = end
    
    tests.append(test)
    
# make simulations
test_results = []

for test in tests:

    prob = test['prob']
    move = test['move']

    sum_counts = 0
    n_counts = 0

    for _ in range(5000):
        count = play_game(prob, move)
        if count <= 1000:
            sum_counts += count
            n_counts += 1

    expected_counts = int(sum_counts/n_counts)
    test_results.append(expected_counts)
    
# print output
print('\n'.join(map(str,test_results)))

  • weijy1994
     + 0 comments

    Be aware that the n_step<1000 condition should be included, otherwise the result of case 0 will be larger than expected.

  • neurocode
     + 0 comments

    Easy way to sample from categorical:

    def sample_cat(dice_probs):
    g = [-log(-log(uniform(0,1))) + log(p) for _, p in zip(range(6), dice_probs)]
    sample = g.index(max(g))
    return sample

    Ref: https://en.wikipedia.org/wiki/Categorical_distribution#Sampling_via_the_Gumbel_distribution

  • ashishaggarwal89
     + 0 comments

    from random import choices

    n=input()

    p=[1,2,3,4,5,6]

    for i in range(0,int(n)):

    w=input()
w = [float(e) for e in w.split(',')]
ls = input().split(',')
ladders=ls[0]
snakes=ls[1]

b=input()
ladder_dict = {}

ladder_pos=b.split()
for i in range(len(ladder_pos)):
    ladder_map = ladder_pos[i].split(',')
    ladder_dict[ladder_map[0]] = [ladder_map[1]]



s=input()


snake_dict = {}
snake_pos=s.split()
for i in range(len(snake_pos)):
    snake_map = snake_pos[i].split(',')
    snake_dict[snake_map[0]] = [snake_map[1]]



def roll(p,w):
    return choices(p,w)

dice_turn = 0
i = 1
counter = 0
while i <= 100 :

    #print(i , dice_turn) #print(counter) if i == 100: break counter += 1 dice_turn = roll(p,w) if (i+int(dice_turn[0])) <= 100: i = i+int(dice_turn[0]) for start,stop in ladder_dict.items(): #print(i , start , stop) if i == int(start): #print("value matched ladder") i = int(stop[0]) for start,stop in snake_dict.items(): #print(i , start , stop) if i == int(start): #print("value matched snake") i = int(stop[0])

                print(counter)

  • ashishaggarwal89
     + 0 comments

    Hi

    I have written the below code and its working fine. Since its taking random values, its not matched with the expected values. Can you please me identify whats wrong in this ?

    from random import choices

    n=input()

    p=[1,2,3,4,5,6]

    for i in range(0,int(n)):

    w=input()
w = [float(e) for e in w.split(',')]
ls = input().split(',')
ladders=ls[0]
snakes=ls[1]

b=input()
ladder_dict = {}

ladder_pos=b.split()
for i in range(len(ladder_pos)):
    ladder_map = ladder_pos[i].split(',')
    ladder_dict[ladder_map[0]] = [ladder_map[1]]

    print(ladder_dict)

    s=input()


snake_dict = {}
snake_pos=s.split()
for i in range(len(snake_pos)):
    snake_map = snake_pos[i].split(',')
    snake_dict[snake_map[0]] = [snake_map[1]]

    print(snake_dict)

    def roll(p,w):
    return choices(p,w)

dice_turn = 0
i = 1
counter = 0
while i <= 100 :

    #print(i , dice_turn) #print(counter) if i == 100: break counter += 1 dice_turn = roll(p,w) if (i+int(dice_turn[0])) <= 100: i = i+int(dice_turn[0]) for start,stop in ladder_dict.items(): #print(i , start , stop) if i == int(start): #print("value matched ladder") i = int(stop[0]) for start,stop in snake_dict.items(): #print(i , start , stop) if i == int(start): #print("value matched snake") i = int(stop[0])

    print(counter)