Fastest path on a snakes and ladders board

Question

I am not looking for a detailed review of this code as I am aware it is very inefficient. The main reason for posting this is to see if there is a better way to achieve my goal (I am certain there must be)

I have created code to find the fewest number of dice rolls that would permit someone to move from the first to last square on a snakes and ladders board. The player wins if they land on or go beyond the final square on the board. They start off the board at position -1.

My approach uses recursion so is OK for small boards. The moment the board reaches a size of 30+ it takes far too long to generate the solution.

Is there a better way to solve this problem

"""Module works out fastest way to traverse a snakes and ladders board"""
def roll_dice(position, roll_number, number_squares, snakes, ladders, list_moves=[]):
    """Roll the dice and then work out if the player can climb a ladder / has won"""
    if position in ladders:
        position = ladders[position]
    if position >= number_squares - 1:
        list_moves.append(roll_number)
        return
    for i in range(1, 7): #For each position roll the dice 6 times
        if position + i in snakes:
            continue  # Forbid a dice-roll that lands on a snake
        roll_dice(position + i, roll_number + 1, number_squares, snakes, ladders)
    return list_moves

def minimum_moves(number_squares, snakes={}, ladders={}):
    """Returns the minimum number of moves starting from position 0 for a board of size n
    snakes and ladders are both dictionaries containing the starting point as the key
    and end point as the value"""
    # Initialise board
    # The player starts off the board at position -1
    list_moves = roll_dice(-1, 0, number_squares, snakes, ladders) 
    print(f"Board is traversable in {min(list_moves)} moves")


if __name__ == "__main__":
    NUMBER_SQUARES = 25
    SNAKES = {21:0, 19:9, 14: 2, 18:5}
    LADDERS = {2: 21, 4:9, 10:20, 17:23}
    minimum_moves(NUMBER_SQUARES, SNAKES, LADDERS)

Answer 1

Don't use mutable default arguments. If you need to default to a list then default to None and then change to an empty list.

Take the following example code:

>>> def example_list_builder(value, list_=[]):
    list_.append(value)
    return list_

>>> example_list_builder(1)
[1]
>>> example_list_builder(2)
[1, 2]

This makes list_ a really poorly defined singleton variable, that can't be accessed globally.

---

Your code looks like it's something like \$O(6^n)\$ where \$n\$ is the size of the board.

You can instead make it \$O(l^2)\$ where \$l\$ is LADDERS and SNAKES.

To improve your code, you should remove the simulation and instead only work with the LADDERS and SNAKES variables.

For each snake and ladder you should traverse it, and then traverse the snake or ladder after this. You should note the distance, there are two ways to do this:

1. Least tiles visited.
2. Least turns taken.

For the latter, you'll have to check for collisions with other snakes and ladders.

You should take snakes into account, as the fastest path for the following is 4 turns:

NUMBER_SQUARES = 1000
LADDERS = {1: 502, 501: 999}
SNAKES = {503: 500}

Answer 2

        continue  # Forbid a dice-roll that lands on a snake

This may prevent finding the shortest path - it's possible to imagine a board with two long ladders, where the first ladder passes the bottom of the second ladder, but a snake descends from after the top of the first ladder to before the bottom of the second ladder. Be careful: if you do follow snakes, you'll need some logic to get you out of loops.

---

if __name__ == "__main__":

This is great - good work!

---

What you probably want to do is to convert the board to a directed graph whose edges are straight runs of board and whose nodes are the destinations of the snakes and ladders.

It might be possible to work with a map of the board, with all the squares containing the number of moves until the end:

• Initially, all squares contain None.
• Now work backwards from the end position, marking how many die throws are necessary to reach the end from there (the first few squares will be 1, for example). But don't write anything at the top of a snake or bottom of a ladder.
• Whenever you reach a square that's already marked, check to see if it's already the same or less than you're about to write to it; if so, then stop exploring that branch.
• If you reach the top of a ladder, you can mark the bottom square with the same number as the top square.
• If you reach the bottom of a snake, the converse applies - mark the top of it with the same number as the bottom.
• When you've completed exploring all branches, the number in the beginning square will be the minimum number of turns needed to reach the top.

It should become obvious that the distinction between snakes and ladders is unimportant here - they just have beginnings and ends, so can be combined into a single list, or just be properties of their beginning and end squares.