Snakes and ladders problem

Snakes and ladders problem


OK so in this video I am going to explain the snakes and ladders problem So Snakes and ladders is a very
classic game you start here start here and you finish here, this is the goal you always start at the fist position, you have to reach the final position so usually this game is played between many people but for this problem actually for the actual game when
one person does is completely independent of the other people
so inspired on that we wrote this
problem, the idea was to know how many turns in expectation do you need to starting in the first
position to reach the goal how many turns that is take. So you start at some point, lets say okay so you for instance start
in the first position if you get two you will advance to
position three will advance here and then you will
climb stairs and go here and if you, at some point
you land in the head of a snake like in the position 27, here then you will have to go to the tail of the snake to all the way down so thats a part of the game and just for
advancing you roll the die and you advance as many positions as the dice tells you and there isn’t something else and you have to take into account if you are near to the goal, let’s
say did you are right now you’re at position 28 here if you get one then you will advance to position 29 you get two then you will go to position 30 if you get three then you have to go back to position 29 if you get four then you will get back to position 28, if get five for instance you land in the head of the snake you
have to go to position 1 so it’s just that when you’re about to
finish you have to come backward also something that you have to consider here in this problem so ok, the solution to this problem it’s a classic expected value with dynamic programming but you have cycles here in the graph you form so you have to be careful about it, so as always you have a base case for any dynamic programming a solution and you have a recusive case the one that you have
here recursion ok the thing here is that this recursion that you have. Is that you have cycles in graphs and if you just implement the recursion like is explain then you will get an infinite recursion problem so of course the idea was not to solve the problem using that and ok so for do recursive step I’m saying
that the expected number of turns that you have to take if you’re at position X it’s equal to 1 plus the sum for all possible values
that you can reach from X, so you will have for all the
possible values that you can reach from X you take the probability of
that action times the expected value of that action that’s actually very classic problem of expected value into the recursion, you have to consider here the D(x) here, this guy here, means the set of all possible squares that can be reached
from X after you roll the die so the solution can’t be implemented
recursively as I told you before because you have loops, you have cycles in this graph, so you will get an infinite loop using that. Basically what we have here is just same equation that we had before but you take sum and you move it to the other side I will show it to you. So you are taking this term here and you’re taking it to the other side with negative sign that’s what I’m showing here and basically what you did when you do
that you know it’s this is an unknown an unknown this is an unknown too, so you have some unknowns you have a system of equations with that and you can then write that system of
equations as a matrix and then solve it with your favorite method to solve system of equations for instance
Gaussian elimination or you can also use matrix exponentiation that’s another way to solve the problem but ok, so one way to do it is just use Gaussian elimination and for this problem the board is at most to 12 times 12 you have at most 144 nodes and it should be very efficient an n cube solution in this case you have big O of n cube solution for each test case that’s fast enough to
solve problem actually pretty fast ok, so some notes, something did you have to take into
account is if you are the end of the board some squares may have probability two sixths instead of one sixths because you can go back and that’s what i shown you here if you start at the position at the position 28 the little guy that I drew in that board if you get for instance one or three you land in
the position 29 so you have twice as much probability to land in position 29 than you have land in the position 30 or 28 or 27 that something did you definitely most
consider to solve this problem and other thing that I told you before is that you can use matrix exponenciation instead of solve the problem with Gaussian elimination if you use matrix exponentiation here then the solution will have a complexity of big O of N cube times log of n that again is fast enough for the size of n that we gave here, so is a perfect valid solution to any of them converge to the right solution which so okay that’s it

2 thoughts on “Snakes and ladders problem

  1. Reto de programación escrito por nuestro equipo de problemsetters de la Red de Programación Competitiva en el marco de la VI Maratón Interna de Programación – UTP Open 2015 División 1.
    El enunciado del problema lo puedes encontrar en: http://redprogramacioncompetitiva.com/forum/viewtopic.php?f=830&t=960&sid=63bc4af39ce488988e87570da2ff2f91#p1670

    El reto puede seguir siendo juzgado en modo pos-maratón en nuestro Juez Boca, en el url: http://www.redprogramacioncompetitiva.com/2015/03_div1/ 

    El reto también puede ser juzgado en el Juez en línea de la Universidad de Valladolid (UVa), en el url: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4775

Leave a Reply

Your email address will not be published. Required fields are marked *