5
\$\begingroup\$

Earlier I posted a fairly inefficient recursive solution to the problem of getting across a snakes and ladders board in the smallest number of moves.

I have created a much faster solution to this using Dijkstra's algorithm and I believe it is correct.

Each square on the board is linked to any square that is between 1-6 larger than it with a weight of one (equivalent of rolling a 1-6 on a dice). All snakes and ladders link squares with a weight of 1. The aim was to have the smallest total cost for the pathway between 1 and 100 (0 and 99 here as I have used list indexes).

This is the first time I have implemented Dijkstra's algorithm and the first time I have used namedtuples. I am not sure if using namedtuples was appropriate, but it made it clearer in my head.

I think I have massively over-complicated bits of code especially within the for loop under the condition if edge.start == next_item:. I seem to be using list comprehensions far too much and I know this makes the solution slower than it could be. Please could someone help me work out better ways to access the variables in my queue of named-tuples.

"""Calculate the shortest path across a snakes and ladders board using Dijkstra's shortest path"""
from collections import namedtuple

Edge = namedtuple("Edge", ("start", "end", "cost"))
Stack = namedtuple("Stack", ("start", "pathcost", "totalcost"))


class Graph:
    """Class generates graph and calculates shortest path"""
    def __init__(self, edges):
        """Generate edges in graph"""
        self.edges = [Edge(*edge) for edge in edges]

    def dijkstra_path(self, start, end):
        """Function that calculates the shortest path"""
        if start >= end or start < 0 or end > 99:
            return -1
        queue = sorted(
            (
                Stack(edge.end, edge.cost, edge.cost)
                for edge in self.edges
                if edge.start == start
            ),
            key=lambda x: x[2],
        )
        while queue:
            next_item, _, current_total = queue.pop(0)
            if next_item == end:
                return current_total
            for edge in self.edges:
                if edge.start == next_item:
                    if edge.end in [item.start for item in queue]:
                        current_cost = [
                            item.totalcost for item in queue if item.start == edge.end
                        ][0]
                        if not current_cost < edge.cost + current_total:
                            queue = [item for item in queue if item.start != edge.end]
                            queue.append(
                                Stack(edge.end, edge.cost, edge.cost + current_total)
                            )
                    else:
                        queue.append(
                            Stack(edge.end, edge.cost, edge.cost + current_total)
                        )
            queue = sorted(queue, key=lambda x: x[2])


def build_graph():
    """Chess Board"""
    list_board = [[i, i + j, 1] for i in range(100) for j in range(1, 7)]
    # Ladders
    list_board.append([1, 37, 1])
    list_board.append([19, 59, 1])
    list_board.append([28, 63, 1])
    list_board.append([55, 99, 1])
    # Snakes
    list_board.append([91, 13, 1])
    list_board.append([86, 11, 1])
    list_board.append([53, 2, 1])
    list_board.append([41, 13, 1])
    return list_board

if __name__ == "__main__":
    GRAPH = Graph(build_graph())
    FROM = 0
    TO = 100
    NUMBER_STEPS = GRAPH.dijkstra_path(FROM, TO)
    if not NUMBER_STEPS == -1:
        print(f"Can complete game in a minimum of {NUMBER_STEPS} rolls")
    else:
        print("Error. Make sure the starting point is between 0 and 99 and less than the end point",
              "which itself must be than or equal to 99")

\$\endgroup\$
  • \$\begingroup\$ As Peilonrayz said in response to your first version, you can make a graph without the blank squares on it. You just need to check distances to and between different snakes and ladders (and the start and end square.) The distance between any two special squares is the difference between their numbers, divided by six, and rounded up. \$\endgroup\$ – Josiah Jun 13 at 22:04
  • 2
    \$\begingroup\$ Nice I hadn't thought about dijkstra's. I see you've included one test, does this example use a snake? Also as @Josiah said you should be able to compute the distance that way, but you'll have to check if it is actually traversable. Say if you have 6 snakes in a row you can't really go that way, or if you're at pos 1, there's a snake at pos 7 and the ladder is at pos 13. \$\endgroup\$ – Peilonrayz Jun 13 at 22:11
  • \$\begingroup\$ Thanks. Yes. I thought that would be far less interesting a coding challenge though as that is basically a mathematical problem. I agree that the aim is in part to compute the outcome as quickly as possible but as I only started getting back into coding a month a go or so, I am very keen to try new techniques and get feedback on them. I hope @Peilonrazy you aren't upset I chose a different technique for my follow-up post.l \$\endgroup\$ – EML Jun 13 at 22:12
  • \$\begingroup\$ @Peilonrayz. I actualy initially tested the code on a very small graph that I wrote by hand and entered the nodes manually. The aim was first to see if the code worked on that before trying it on the snakes and ladders board. \$\endgroup\$ – EML Jun 13 at 22:15
  • 1
    \$\begingroup\$ I'll have you know I'm very upset @EML - that I didn't think of using Dijkstra's before reading this question. This is definitely better than what I was thinking \$\endgroup\$ – Peilonrayz Jun 13 at 22:34
2
\$\begingroup\$
  • Named tuples are a good idea here. If you need to mutate the data you should instead use dataclasses.dataclass. But as there is no need here it's good.

  • I'd suggest changing your nodes to contain snakes, ladders, and the start and end of the board. This is as you don't need to build the empty spaces as they are only used as distances.

    Since you need the distance between two nodes, then you need to calculate the distance at creation, not during the calculations.

  • I've simplified calculating the distance between each node. You should take into account the following special cases:

    • If the distance between two nodes is 12, and there is a snake or ladder halfway between them, it takes 3 rather than 2 turns to travel between the nodes.
    • If there are 6 snakes or ladders after a node it's impossible to pass them without visiting those nodes.
  • Currently you have Edge with a start, end and cost. I would suggest you instead split this into a Node with a start, end and edges. And an Edge that has a distance and a node.

    It should be noted that the start and end should only be used when creating the graph. The node will then just turn into glorified list.

  • It should be noted that Node should be called Vertex if you want to keep with 'pure' graph theory naming.

  • Please ignore my implementation of Dijkstra's algorithm, it's not great. And half way I came across some hashing problems, hence the path[node[:2]] ickyness. I don't recommend you take inspiration from it - unless it's how not to code.

    This means if the graph is setup, incorrectly, to have two ladders over the same space, then some bugs may appear.

All of this together can look like:

from collections import namedtuple
from dataclasses import dataclass, field
from typing import *  # Against best-practice but shhh
import math

Edge = namedtuple('Edge', 'distance node'.split())


class Node(namedtuple('Node', 'start end edges'.split())):
    def __str__(self):
        return f'{self.start} -> {self.end}'


@dataclass(order=True)
class Path:
    distance: int
    current: Node=field(compare=False)
    previous: Node=field(compare=False)


@dataclass
class Graph:
    nodes: List[Node]

    def shortest_paths(self, start: Node) -> Dict[Node, Path]:
        if start not in self.nodes:
            raise ValueError("Graph doesn't contain start node.")
        paths = {}
        queue = []
        for node in self.nodes:
            path = Path(float('inf'), node, None)
            paths[node[:2]] = path
            queue.append(path)

        paths[start[:2]].distance = 0
        queue.sort(reverse=True)
        while queue:
            node = queue.pop()
            for neighbor in node.current.edges:
                alt = node.distance + neighbor.distance
                path = paths[neighbor.node[:2]]
                if alt < path.distance:
                    path.distance = alt
                    path.previous = node
            queue.sort(reverse=True)
        return paths

    def shortest_path(self, start: Node, end: Node) -> List[Tuple[int, Node]]:
        if end not in self.nodes:
            raise ValueError("Graph doesn't contain end node.")
        paths = self.shortest_paths(start)
        node = paths[end[:2]]
        output = []
        while node is not None:
            output.append((node.distance, node.current))
            node = node.previous
        return list(reversed(output))


def build_nodes(snakes: List[Tuple[int, int]], size: int) -> List[Node]:
    return [
        Node(1, 1, []),
        Node(size, size, [])
    ] + [
        Node(start, end, [])
        for start, end in snakes
    ]


# There are some edgecases that will need to be handled.
def calculate_distance(start: Node, end: Node, nodes: List[Node]):
    distance = int(math.ceil((end.start - start.end) / 6))
    start.edges.append(Edge(distance, end))


def add_edges(nodes: List[Node]):
    for start in nodes:
        for end in nodes:
            if end.start > start.end:
                calculate_distance(start, end, nodes)


def build_graph(edges: List[Tuple[int, int]], size: int):
    nodes = build_nodes(edges, size)
    add_edges(nodes)
    start, end = nodes[:2]
    return Graph(nodes), start, end


if __name__ == '__main__':
    graph, start, end = build_graph(
        [
            (  2, 520),
            (530, 500),
            (510, 999)
        ],
        1000,
    )
    for dist, node in graph.shortest_path(start, end):
        print(dist, node)

This outputs:

0 1 -> 1
1 2 -> 520
3 530 -> 500
5 510 -> 999
6 1000 -> 1000
\$\endgroup\$
  • \$\begingroup\$ Wow, a downvote within 5 minutes. I must have really messed something up. If it's fixable it'd be great to know what, so I can improve my answer. Thank you. \$\endgroup\$ – Peilonrayz Jun 14 at 2:43
  • \$\begingroup\$ There's actually quite a few edge cases to handle, like, say, nodes that are 16-18 steps apart with snakes or ladders at 5, 6 and 10 steps from the first node. Writing a reliable distance calculation is not a trivial exercise. I would actually recommend including empty spaces in the search graph, at least at first, just for that reason: it may slow down the search a bit, but it also frees you from having to explicitly consider all those edge cases. If it's too slow, you can later optimize it. But aim for correctness before speed. \$\endgroup\$ – Ilmari Karonen Jun 14 at 8:21
  • \$\begingroup\$ Wow thanks. It's really great to get such detailed feedback on this. I'm learning so many new concepts so I really appreciate. Never even heard of dataclasses before! Thanks \$\endgroup\$ – EML Jun 14 at 9:08
  • \$\begingroup\$ @IlmariKaronen I'm not sure having white space in the graph makes it correct. Also it seems pretty trivial to me. \$\endgroup\$ – Peilonrayz Jun 14 at 11:30
  • 1
    \$\begingroup\$ @EML If you see the line above that Edge = namedtuple(...). Following PEP 8 we know Edge is a class, and type(Edge) is type also shows it is. And so we can do class MyClass(Edge). You should be able to see now that all I've done is removed the need to define a class _Node - the named tuple - that Node inherits from. \$\endgroup\$ – Peilonrayz Jun 15 at 16:33

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.