Snakes and Ladders

snakes_and_ladders.py

from Queue import Queue

# Convert a list of prev nodes into a forward path
def backtrace( prev ):
    current = 100
    path = []
    while current > 0:
        path.insert( 0, current )
        current = prev[ current ]
    return path

# BFS can be used to find shortest path on unweighted graph
def BFS( graph, v1, v2 ):
    queue = Queue()
    queue.put( v1 )
    prev = [ -1 for i in xrange( 0, 100 + 1 ) ]
    
    while queue.qsize() > 0:
        v = queue.get()
        for i in xrange( 1, 100 + 1 ):
            if graph[ v ][ i ] == 1 and v < i: # forward edge
                if prev[ i ] == -1:
                    prev[ i ] = v
                else:
                    continue
                if i == v2:
                    return backtrace( prev )
                else:
                    queue.put( i )
    print "no path"

# Handle input
test_cases = int( raw_input() )

for case in xrange( 0, test_cases ):
    ( num_ladders, num_snakes ) = [ int( i ) for i in raw_input().split( "," ) ]
    ladders = [ [ int( j ) for j in i.split( "," ) ] for i in raw_input().split( " ") ]
    snakes = [ [ int( j ) for j in i.split( "," ) ] for i in raw_input().split() ]

    # initialize and populatate graph
    graph = [ [ 0 for j in xrange( 0, 100 + 1 ) ] for i in xrange( 0, 100 + 1 ) ]
    
    # normal path
    for i in xrange( 1, 100 ):
        for j in xrange( 1, 6 + 1 ):
            if i + j <= 100:
                graph[ i ][ i + j ] = 1

    # shortcuts
    for pair in ladders:
        graph[ pair[ 0 ] ][ pair[ 1 ] ] = 1 # because the graph is directed, we implicitly capture whether an edge is a snake or ladder
    for pair in snakes:
        graph[ pair[ 0 ] ][ pair[ 1 ] ] = 1

    # calculate shortest path between node 1 and 100
    path = BFS( graph, 1, 100 )

    print len( path ) - 2