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)