CODEWITHSUNDEEP
pythondistancedictionary
Soren Bjornstad
Soren Bjornstad

Reputation: 1412

Find the shortest distance between two squares on a game board

I have the paths on a game board stored in a dictionary formatted something like the following:

{1: [2,3,4], 2: [1,3,5], 3: [1,2,4], ...}

This means if you're on space 1, you can move to spaces 2, 3, or 4, and so on. Every key links to at least two values in the list; many have four or more. There are 199 total spaces on the board. A notable catch is that sometimes you might be able to skip a space, so in...

{1:[2,3,4], 2:[3]}

...you can go 1 -> 2 -> 3, or you can just go 1 -> 3.

I'm looking to create an algorithm to find the shortest distance between any two squares. The obvious thought is to look up the key for the starting space, then take the first number in the list, look up the possible spaces for that, and so on, stopping and returning to the previous list when it hits either a previously seen number or the final square (storing the path and distance if it hits the result square, to be compared after finishing).

I have very little idea about how to start implementing this, though. (If there were only two steps, I'd use nested loops, but obviously that won't work here, since I don't know how many levels deep it might go).

Better solutions or optimizations involving other data structures are welcome; I have the data stored in a CSV file resembling this dictionary, so I can easily convert it to something else if that would work better.

Here's a link to a picture of the board I'm working with: http://goo.gl/Rasq6

EDIT: Okay, I'm trying to implement Dijkstra's algorithm. Here's what I've got:

  1 movedict, transdict = boardstruct.prepare_board()
  2 
  3 source = 87
  4 dest = 88
  5 
  6 dist = {}
  7 prev = {}
  8 for v in movedict.keys():
  9     dist[v] = float('inf')
 10     prev[v] = None
 11 
 12 dist[source] = 0
 13 q = movedict.keys()
 14 
 15 while q:
 16     smallest = float('inf')
 17     for i in q:
 18         dist_to = dist[i]
 19         if dist_to < smallest:
 20             smallest = dist_to
 21     print smallest
 22     u = q.pop(smallest)
 23     print u
 24 
 25     if dist[u] == float('inf'):
 26         break
 27 
 28     for v in movedict[u]:
 29         alt = dist[u] + 1 # distance = flat 1
 30         if alt < dist[v]:
 31             dist[v] = alt
 32             prev[v] = u
 33             # reorder queue?

(21 and 23 are debug statements I forgot to remove)

I'm working off pseudocode from Wikipedia (http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode), as I can't find any existing implementations that match a data format like what I need (every move has a fixed cost, so the distance is not stored anywhere).

I understand I need to reorder the queue at the end, but I'm not sure how. I also don't understand what lines 25 and 26 are for (the comment says "all remaining vertices are inaccessible from source"--does this just keep it from running any further when it's guaranteed to have already found the best path?). I probably messed something else up, too, so if you could look over it I'd appreciate it.

Upvotes: 1

Views: 1955

Answers (2)

tzelleke
tzelleke

Reputation: 15345

Use networkx. Its easily installed.

From the picture of the game board I recognize the Scotland Yard game.
Commenting on your conversation with @Bill the Lizard:
You can indeed precompute all shortest paths ahead. Neither the nodes nor the edges change.
You can reach 46 from 13 either via 5 taxi steps, or 1 underground step.

I would probably use one "big" graph containing all edges (taxi, bus, underground) together and several graphs that combine taxi+bus, taxi+underground and just taxi (I do not quite remember the rules of the game... You have to figure out what makes sense).

I'm not sure how the algorithm in networkx handles ties!

So, precompute all shortest paths ahead.
Then simply look them up whenever needed.

import networkx as nx

# simplified example
# data is in the format as you specified
data = data = {1: [2,3,4],
               2: [1,3,5],
               3: [1,2,4],
               4: [1,3,5],
               5: [2,4]}

# initialize empty graph
G = nx.graph()

# now we're adding all edges
# don't bother about duplicates -- they're ignored
for n1, n in data.items():
    for n2 in n:
        G.add_edge(n1, n2)

# get ALL shortest paths
p = nx.shortest_path(G)

# lookup when needed, e.g. from 1 to 5
p[1][5]
# gives [1, 2, 5]

Upvotes: 2

Bill the Lizard
Bill the Lizard

Reputation: 405735

What you're describing is a shortest path problem. There are several ways to solve it. Dijkstra's algorithm is one of the simplest to implement, but it's overkill for your application. (It finds the shortest path from one node to all other nodes.) There's a related algorithm called A* that's a little more complicated, but it does exactly what you're looking for.

Upvotes: 3

Related Questions