In preparation for a coding interview, I found this question but am struggling to solve it. I'm very sure recursion needs to be used, but I can't seem to get it right.

A 2D array represents a map of cities, where the value at the index represents the number of treasures in that city. Some values in the array are zeros (indicating that they can't be crossed)

Goal: Given a 2D array, return an integer representing the maximum amount of treasures you can collect by travelling from city to city.

Rules:

1. Can start anywhere in the array
2. Avoid zeroes (ie. can't be crossed)
3. You can travel up, down, left, right at 1 index at a time
4. Possible for different paths to yield same amount of treasures
5. An empty map should return 0
6. If the map contains anything other than positive integers, the function should return -1

Eg. Map 1:
[[ 3, 0, 0, 1, 2],
[ 0, 1, 4, 0, 0],
[ 5, 0, 0, 3, 3]]

The maximum reward would be 6 items (3,3)

What I've tried:
I tried creating two for loops to access each index: First, I check that the current Index is not zero or -1. If not, then I add value at the current index to an empty array where each path indicated a different position. ie. left = arr[0], right = arr[1], etc. Then found the possible paths and repeat the same processes until my array index value is zero (for all paths).

If someone could provide a solution in python, it would be very much appreciated.

CodePudding user response：

The following is a naive approach that uses simple recursion to solve this problem. However, I wouldn't be surprised if there was a smarter solution to the task, preferably without recursion.

import numpy as np

reward_map = np.array(
    [[ 3, 0, 0, 1, 2],
     [ 0, 1, 4, 0, 0],
     [ 5, 0, 0, 3, 3]])

print("Reward map:")
print(reward_map)

# This function checks if [i,j] are valid indices for the matrix "mat"
def are_valid_idcs(mat, i, j):
    return i >= 0 and j >= 0 and i < mat.shape[0] and j < mat.shape[1]

# This is the recursive function that computes the value given a starting point
def get_cell_value(reward_map, i, j):
    if ( not are_valid_idcs(reward_map, i, j) ) or reward_map[i,j] == 0.:
        return 0.
    else:
        # If we are in a "city", we want to check the connected squares. 
        # However, from there, we do not want to walk back.
        # That's why I copy the whole map and set [i,j] = 0, meaning this coordinate has already been handled.
        # This is important. If we do not do this, the recursion will not stop.
        submap = np.array(reward_map)
        submap[i,j] = 0.
        
        # Now we compute the value of our neighbors
        value_left = get_cell_value(submap, i-1, j)
        value_right = get_cell_value(submap, i 1, j)
        value_top = get_cell_value(submap, i, j-1)
        value_bottom = get_cell_value(submap, i, j 1)
        
        # And add everything together
        return value_left   value_right   value_top   value_bottom   reward_map[i,j]


# Here, we will remember the value and the coordinates where we started
values_per_idcs = []

# Loop over all cells and compute which value we can get if we start at that point
for i in range(reward_map.shape[0]):
    for j in range(reward_map.shape[1]):
        values_per_idcs  = [ [ get_cell_value(reward_map, i, j), i, j] ]

# Now we build a numpy [n,3]-array over the results, where n is the total amount of elements in the map
# The 3 components in the 1-axis correspond to [value, i, j].
values_per_idcs = np.array(values_per_idcs, dtype=np.int64)

# Check if there are negative values in the map
if np.any(reward_map < 0):
    print(f" Value is -1 (due to negative values in reward map)")
# Check if all values are integer
elif not issubclass(reward_map.dtype.type, np.integer):
    print(f" Value is -1 (due to non-integer values in reward map)")
# If the input is OK, we can output the actual results
else:
    # in the [n,3]-result-array, find the n which has the maximum value (i.e. at position 0 on axis 1)
    best = np.argmax( values_per_idcs[...,0], axis=0 )
    
    # Print the best coordinate
    print(f"Maximum value is {values_per_idcs[best,0]} at indices {values_per_idcs[best,1], values_per_idcs[best,2]}")
    
    # Plot the suggested starting point which is easier for humans to read than the coordinates
    print("Suggested start-point:")
    starter = np.zeros_like(reward_map, dtype=np.int8)
    starter[values_per_idcs[best,1], values_per_idcs[best,2]] = 1
    print(starter)

Output:

Reward map:
[[3 0 0 1 2]
 [0 1 4 0 0]
 [5 0 0 3 3]]
Maximum value is 6 at indices (2, 3)
Suggested start-point:
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 1 0]]

Good practice task for you:

Note that this approach is sub-optimal, since it recomputes the value of a cluster of cities for every city in that cluster. Thus, if our reward_map is a [n,m] matrix of only 1's, it would start the full recursion for all n*m coordinates, which is pretty bad. A good practice for you would be to fix this problem by updating the reward_map inside the recursion, such that reward_map[i,j]=0. for every [i,j] that was ever processed in the recursion.

If you are happy with this answer, please do not forget to accept it.