How can I speed up/fix this shortest path grid traversal?

user_13192151 0
Viewed 271

I'm working on writing a program to traverse a grid from the bottom left to the top right where valid moves are moving to the right by 1, moving up by 1, or jumping up or right by an amount designated in the jump array. The inputs are the grid in a 2D array format, dimensions of the grid: X and Y, and an array of jumps where the jumps have to be completed in order. The output is the shortest path where the length of the path is the sum of all numbers touched including bottom left and top right.
Example input:

Grid: 
    [9 9 1]
    [9 9 1]    
    [3 9 1]

Jumps: [1 1] X:3, Y:3

The output for this would be 5 because we start at (0,0) which is 3 and then use the first 1 block jump to (2, 0) which is 1 and then the second one block jump to (2, 2) which is 1 so 3+1+1 = 5. If the jumps array was only [1] then the output would be 6 since we would have to move from (2,0) to (2,1) to (2,2).

This is my first solution, which seems to work for smaller inputs but just runs forever on larger inputs:

def get(grid, x, y, endX, endY):
    if (x > endX or y > endY):
        return False
    return grid[y][x]

def fly(x, y, grid, jumps, endX, endY):
    if x > endX or y > endY:
        return float('inf')
    if (x == endX and y == endY):
        return get(grid, endX, endY, endX, endY)
    flyup = fly(x, y+1, grid, jumps, endX, endY)
    flyright = fly(x+1, y, grid, jumps, endX, endY)
    if (len(jumps) > 0):
        jumpup = fly(x, y+jumps[0]+1, grid, jumps[1:], endX, endY)
        jumpright = fly(x+jumps[0]+1, y, grid, jumps[1:], endX, endY)
        temp = min(flyup, flyright, jumpup, jumpright)
        return get(grid, x, y, endX, endY) + temp
    else:
        temp = min(flyup, flyright)
        return get(grid, x, y, endX, endY) + temp

fly(0, 0, grid, jumps, X-1, Y-1)

This is another solution I wrote using DP (or whatever my understanding of DP is since I just learned it) but this one seems to only work on certain inputs and I can't identify a pattern.

def fly2(x, y, grid, jumps):
    dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if row == 0 and col == 0:
                dp[row][col] += get2(grid, col, row)
            else:
                flyup = float('inf') if row==0 else dp[row-1][col]
                flyright = float('inf') if col==0 else dp[row][col-1]
                jumpup =  float('inf') if row < jumps[0]+1 else dp[row-jumps[0]-1][col]
                jumpright =  float('inf') if col < jumps[0]+1 else dp[row][col-jumps[0]-1]
                shortest = min(flyup, flyright, jumpup, jumpright)
                if min == jumpup or min == jumpright:
                    jumps = jumps[1:]
                dp[row][col] += get2(grid, col, row) + shortest
    return dp[len(grid)-1][len(grid[0])-1]

I need some help speeding up the first one or figuring out what's wrong with the second one or maybe get some other ideas on how I can write this efficiently. Thanks

dynamic-programming algorithm python
2 Answers

It seems to me that the dp should have another dimension for the current jump index. Generally,

dp[y][x][j] = Grid[y][x] + min(
  dp[y + 1][x][j],
  dp[y][x - 1][j],
  dp[y + jump[j-1] + 1][x][j-1],
  dp[y][x - jump[j-1] - 1][j-1]
)

where j is the current index in the jump array.

(I think the question description uses (x, y) coordinate notation in the example. I used [y][x] as [row][column], common for programming two dimension array access.)

user_20347870

The following implementation uses the grid and the remaining jumps as the state variables:

import numpy as np

def shortest(grid, jumps):
    rows, cols = grid.shape
    if (rows, cols) == (1, 1): # if grid is just a single number
        return float('inf') if jumps else grid[0, 0]
    candidates = [] # store results from deeper calls
    if rows > 1:
        candidates.append(shortest(grid[:-1, :], jumps)) # up by one
        if jumps and rows > jumps[0] + 1: # jump to the above if possible
            candidates.append(shortest(grid[:-(jumps[0] + 1), :], jumps[1:]))
    if cols > 1:
        candidates.append(shortest(grid[:, 1:], jumps)) # right by one
        if jumps and cols > jumps[0] + 1: # jump to the right if possible
            candidates.append(shortest(grid[:, (jumps[0] + 1):], jumps[1:]))
    return grid[-1, 0] + min(candidates)

grid = np.array([[9, 9, 1], [9, 9, 1], [3, 9, 1]])
jumps = [1, 1]
print(shortest(grid, jumps)) # 5

Usage of np.array is just for simplicity of slicing.

user_114508200
Related