Finding the cost of travel on the route closest to the specified value
I recently got stuck with a problem. I need to find the cost of the path from the top left corner to the bottom right corner of a multidimensional array of integers. This path cost should be the highest cost that does not exceed some of the provided cost.
The cost of a path is defined as the sum of the array index values that the path passes through. The beginning of each path is always in the upper left corner, and the end of each path is always in the lower right corner. Also, you can only move to the right or right.
Let's say it is a multidimensional array that I have to use for this problem and the value provided is 12.
+---+---+---+
| 0 | 2 | 5 |
+---+---+---+
| 1 | 1 | 3 |
+---+---+---+
| 2 | 1 | 1 |
+---+---+---+
This is the correct path that I must find. The cost of this path is 11, which is the highest cost of any path that is less than or equal to the specified value.
+---+---+---+
| X | X | X |
+---+---+---+
| 1 | 1 | X |
+---+---+---+
| 2 | 1 | X |
+---+---+---+
I have tried to solve this problem in Python, but I cannot see where I am going wrong. Below is a snippet of my code below.
def answer (food, grid):
# Grid is N*N in size
n = len(grid)
# Memoize a given function
def memoize (f):
memo = {}
def helper (r, c, k):
i = c + (r * n)
if i not in memo:
memo[i] = f(r, c, k)
return memo[i]
return helper
# Get cost function
def get_cost (r, c, k):
if r >= n or c >= n:
return -1
if k < grid[r][c]:
return -1
if r == n - 1 and c == n - 1:
return grid[r][c]
down = get_cost(r + 1, c, k - grid[r][c])
right = get_cost(r, c + 1, k - grid[r][c])
if down < 0 and right < 0:
return -1
return grid[r][c] + max(down, right)
# Memoize the get cost function
get_cost = memoize(get_cost)
return get_cost(0, 0, food)
print answer (12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
I always get an answer of 16, where should I get an answer of 11. Can anyone help me with this?
Edit:
I modified the memoize code to include the specified value in the index. And I got the right answer. However, there are other cases where this does not work. (I am not provided with data in these cases, so I cannot see where it went wrong).
Here is my updated code.
# Memoize a given function
def memoize (f):
memo = {}
def helper (r, c, k):
i = (k * food) + (c + (r * n))
if i not in memo:
memo[i] = f(r, c, k)
return memo[i]
return helper
source to share
You can update the memoize function like this:
def memoize (f):
memo = {}
def helper(*args):
if args not in memo:
memo[args] = f(*args)
return memo[args]
return helper
grid = [[0,2,5],[1,1,3],[2,1,1]]
answer(12, grid)
# 11
As long as your arguments are hashed, you can use it *args
as an argument to your function and args
as a key to the memoization cache. This is the same as using a tuple of arguments as a key.
def fn(*args):
print(args)
fn(1,2,3)
(1, 2, 3)
The original memoization cache keys, composed i = c + (r * n)
, are excluded with consideration k
, and possible collisions are also allowed for different combinations of c and r.
source to share
I would like to take a different approach using reverse traffic:
def find_path(food, grid):
n = len(grid)
def worker(cost, path):
row, col = path[-1]
if row == n - 1 and col == n - 1:
# we reached the bottom right corner, exit now
return cost, path
possible_paths = []
if row < n - 1:
# we can go down
cost_down = cost + grid[row+1][col]
path_down = list(path)
path_down.append((row+1, col))
possible_paths.append(worker(cost_down, path_down))
if col < n - 1:
# we can go to the right
cost_right = cost + grid[row][col+1]
path_right = list(path)
path_right.append((row, col+1))
possible_paths.append(worker(cost_right, path_right))
# a path is valid, if its cost is
# less or equal to the food available
valid_paths = [item for item in possible_paths
if item is not None
and item[0] <= food]
if valid_paths:
return max(valid_paths, key=lambda x: x[0])
return None
return worker(grid[0][0], [(0, 0)])
The algorithm recursively walks through the array and continues to look for all possible paths. If the path cost is higher than the limit ( food
), it is discarded; otherwise, all possible subsequent steps are checked. When the lower right corner is reached, the work function ends and the different paths are compared.
This way can also be discovered using arrays without any possible path:
print(find_path(12, [[0, 2, 5],
[1, 1, 3],
[2, 1, 1]]))
# (11, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])
print(find_path(12, [[0, 2, 5],
[1, 1, 3],
[2, 1, 10]]))
# None
print(find_path(42, [[3, 8, 6, 5],
[1, 5, 3, 9],
[1, 5, 8, 1],
[2, 1, 9, 4]]))
# (42, [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)])
source to share