How can a global variable go back to an un-updated state?

I am doing a leetcode question using backtracking: https://leetcode.com/contest/weekly-contest-212/problems/path-with-minimum-effort/ and found output I can’t explain. Maybe there’s something lacking with my understanding of global variables when used with recursion?

My reproducible solution (Time Limit Exceeded, but that’s a separate discussion if you want to start) :

import numpy as np
import math

min_effort = math.inf

def valid(r,c,visited):
    return r < visited.shape[0] and r >= 0 and c < visited.shape[1] and c >= 0 and visited[r,c] == 0

def find_path(heights_arr,visited,r,c,effort,max_row, max_col):
    global min_effort
    
    if r == max_row and c == max_col: 
        print(f'-------------------Found end: effort is {effort}')
        return effort
    
    for row,col in ((r+1,c),(r,c+1),(r-1,c),(r,c-1)):
        if valid(row,col,visited):
            print(f'going from {r},{c} to {row},{col}')
            print(f'effort before recurse: {effort}')
            visited[row,col] = 1 
            updated_effort = max(effort, abs(heights_arr[row,col]-heights_arr[r,c]))  # possibly update current max effort along path
            #recursion_res = find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col)
            #print(f'min_effort:{min_effort} recursion_res:{recursion_res}')
            #min_effort = min(min_effort,recursion_res)
            
            min_effort = min(min_effort,find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col))   # problem
            #min_effort = min(find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col),min_effort)
            
            visited[row,col] = 0
            
            print(f'global min_effort after recurse: {min_effort}')
            
    return math.inf
    #return min_effort
    
def minimumEffortPath(heights):
    heights_arr = np.array(heights) 
    rows, cols = heights_arr.shape
    max_row, max_col = rows-1, cols-1
    
    r,c = 0,0
    visited = np.zeros((rows, cols))
    visited[r,c]=1
    
    effort = 0
    find_path(heights_arr,visited,r,c,effort,max_row, max_col)


#heights = [[1,2,2],[3,8,2],[5,3,5]]
heights = [[1,2,3],[3,8,4],[5,3,5]]
minimumEffortPath(heights)
print(min_effort)


The strange phenomena happens when the destination is reached through path of 1,3,5,3,8,2,3,4,5, after backtracking 5 steps, the global variable went back from 2 to inf (with a wrong inf as final answer).

How can this happen? Shouldn’t the global variable min_effort be capped at 2 throughout the rest of the program run?

This problem can be resolved if the commented code is used instead, to run the find_path recursion first and save into recursion_res before min() comparison rather than directly using the recursion call in min().

It will also be resolved if the order of arguments in min() is switched (i see this as the most important thing to sort out).

It will also be fixed if i replace return math.inf with return min_effort. Also, totally avoiding global variables and passing min_effort along the function parameters and return statements fixes this, but I still want to understand why this is happening.

Below is the proper output, with the correct final answer.

I suspect this has something to do with local scopes I’m not aware of yet.

Edit

I thought through it and understand now. Python evaluates left to right. By doing min(min_effort,recurse()), the value of min_effort was already evaluated and saved in the local stack of that level of call before the recursion had a chance to update the global min_effort to a smaller value than inf. Extracting the recursion out and assigning to a var before doing min() allows the recursion to run first to update the global before min() operation.

The pattern of 2,2,2,2,2,inf,inf appeared because moving backwards from the destination through the numbers 5,4,3,2,8,3,5,3,1, at the scope of 6th and 7th number 3 and 5, min_effort had not seen the destination yet and was inf, so min() was comparing the initialized inf with the returned math.inf.

The 1st five 2s were not inf because according to my defined recursion order of down,right,up,left, the recursions seeing 5,4,3,2,8 and already had min_effort updated to 2 from the 1st successful path of 1,3,5,3,5. So the 1st give 2s were printing min(2, recurse()).

Replacing return math.inf with return min_effort gives correct result while allowing min(min_effort,recurse()) because the return gives back the updated global, so even if the 1st argument min_effort was evaluated before recursion had a chance to update, the 2nd argument recursing would have returned the updated global to give correct min(). return min_effort is compulsary when not using globals so the most updated value always is passed back for future loop iterations (directions) to compare. This is not compulsary and return math.inf can be used if globals are used with running recursion before min() described above to avoid the “un-updated min_effort problem” and let the recursion do it’s magic first before min(), making the return value of math.inf or min_effort not important because the caller will handle both return values and give correct min().

This was a good lesson in being really careful with globals. I still can’t debug why Leetcode doesn’t like globals. Something is not being refreshed across test case runs so giving wrong answer, but running the wrong test case as custom input alone gives correct answer.

Summary

Global variable pros:

  1. Convenient coding
  2. Less parameter passing and simpler recursive functions
  3. More immediate value updating and lax return value allowed

Global variable cons:

  1. Don’t gel with online coding platforms (risky for job interview automated coding assessments)

Local parameter passing pros:

  1. Easier debugging/tracing focusing on local problem space
  2. Less side effect

Local parameter passing cons:

  1. More verbose function signature

Any opinions on moving def find_path into def minimumEffortPath and using nonlocal? I didn’t do that because following the zen of python: flat better than nested.

1 Like