5
\$\begingroup\$

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)

\$\endgroup\$
  • 2
    \$\begingroup\$ Here is my solution if need be - repl.it/repls/StainedMonthlyOutput. (By the way, nice question!) \$\endgroup\$ – Justin Jun 13 at 16:18
  • \$\begingroup\$ It's okay. I have provided a link to my first solution above if need be. I'm glad it helped you! \$\endgroup\$ – Justin Jun 13 at 16:24
  • \$\begingroup\$ Follow-up question \$\endgroup\$ – 200_success Jun 13 at 21:55
7
\$\begingroup\$

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}
\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for the suggestions. I will see if I can come up with a faster solution using these ideas. \$\endgroup\$ – EML Jun 13 at 16:05
  • \$\begingroup\$ How would you code the list_moves then so it isn't mutable but still returns all the values to the minimum_moves function? Thanks \$\endgroup\$ – EML Jun 13 at 16:35
  • 2
    \$\begingroup\$ @EML def fn(value=None): if value is None: value = []; ... or def fn(value=None): value = value or []; .... \$\endgroup\$ – Peilonrayz Jun 13 at 16:37
  • \$\begingroup\$ After implementing this, I got ValueError: min() arg is an empty sequence. I pass the list_moves between stacks \$\endgroup\$ – EML Jun 13 at 16:43
5
\$\begingroup\$
        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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Yes that was one of the reasons I avoided snakes all together. I could imagine an infinite loop developing and had no idea how I would avoid this \$\endgroup\$ – EML Jun 13 at 20:35
  • \$\begingroup\$ Having said this, I think the above method is very bad. I agree that a directed graph is actually a really smart idea and I have, in fact, been trying to build one as I realised this would be a really smart way to solve the problem. Thanks for suggesting this too as it supports my hypothesis \$\endgroup\$ – EML Jun 13 at 20:36
  • 1
    \$\begingroup\$ To be honest, I mentioned the directed graph and then realised that just labelling the squares is going to be easier, given that we need to deal with moves that skip over the starts of shortcuts. I'd go with the latter option. \$\endgroup\$ – Toby Speight Jun 13 at 20:43
  • \$\begingroup\$ Thanks for this. I had basically finished my directed graph code and as this is actually something I am not used to writing, I think getting feedback on this would be most helpful \$\endgroup\$ – EML Jun 13 at 21:29
  • 2
    \$\begingroup\$ @muru: In a word: mistakenly :-( I've edited to remove my error! \$\endgroup\$ – Toby Speight Jun 14 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.