Snakes and Ladders: The Quickest Way Up

  • + 0 comments

    Python Solution

    def quickestWayUp(ladders, snakes):
        n_moves = [-1]*101
        n_moves[1] = 0
        todo = [1]
        ladders_dict = {min(i,j): max(i,j) for i, j in ladders}
        snakes_dict = {max(i,j): min(i,j) for i, j in snakes}
        while todo:
            start = todo.pop()
            for x in range(start + 1, start + 7):
                x = ladders_dict.get(x, snakes_dict.get(x, x))
                if x > 100:
                    break
                if (n_moves[x] == -1) or (n_moves[x] > n_moves[start] + 1):
                    n_moves[x] = n_moves[start] + 1
                    todo.append(x)
        return n_moves[100]