Skip to content

Instantly share code, notes, and snippets.

@gitgithan

gitgithan/gist:d7b8d0b5ec27081cc0391c8b03bd192b

Created October 31, 2020 08:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gitgithan/d7b8d0b5ec27081cc0391c8b03bd192b to your computer and use it in GitHub Desktop.
Save gitgithan/d7b8d0b5ec27081cc0391c8b03bd192b to your computer and use it in GitHub Desktop.
Download ZIP
Recursion with global variable gotcha
Raw
gistfile1.txt
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# global no bounding "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2020-10-31T08:21:01.762847Z",
"start_time": "2020-10-31T08:21:01.738897Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"going from 0,0 to 1,0\n",
"effort before recurse: 0\n",
"going from 1,0 to 2,0\n",
"effort before recurse: 2\n",
"going from 2,0 to 2,1\n",
"effort before recurse: 2\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 2\n",
"-------------------Found end: effort is 2\n",
"global min_effort after recurse: 2\n",
"going from 2,1 to 1,1\n",
"effort before recurse: 2\n",
"going from 1,1 to 1,2\n",
"effort before recurse: 5\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 2\n",
"going from 1,2 to 0,2\n",
"effort before recurse: 5\n",
"going from 0,2 to 0,1\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,1 to 0,1\n",
"effort before recurse: 5\n",
"going from 0,1 to 0,2\n",
"effort before recurse: 6\n",
"going from 0,2 to 1,2\n",
"effort before recurse: 6\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"going from 1,0 to 1,1\n",
"effort before recurse: 2\n",
"going from 1,1 to 2,1\n",
"effort before recurse: 5\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 5\n",
"going from 2,1 to 2,0\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 5\n",
"global min_effort after recurse: inf\n",
"going from 1,1 to 1,2\n",
"effort before recurse: 5\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 5\n",
"going from 1,2 to 0,2\n",
"effort before recurse: 5\n",
"going from 0,2 to 0,1\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 5\n",
"global min_effort after recurse: 5\n",
"global min_effort after recurse: inf\n",
"going from 1,1 to 0,1\n",
"effort before recurse: 5\n",
"going from 0,1 to 0,2\n",
"effort before recurse: 6\n",
"going from 0,2 to 1,2\n",
"effort before recurse: 6\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 6\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"going from 0,0 to 0,1\n",
"effort before recurse: 0\n",
"going from 0,1 to 1,1\n",
"effort before recurse: 1\n",
"going from 1,1 to 2,1\n",
"effort before recurse: 6\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 6\n",
"going from 2,1 to 2,0\n",
"effort before recurse: 6\n",
"going from 2,0 to 1,0\n",
"effort before recurse: 6\n",
"global min_effort after recurse: 6\n",
"global min_effort after recurse: 6\n",
"global min_effort after recurse: inf\n",
"going from 1,1 to 1,2\n",
"effort before recurse: 6\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 6\n",
"going from 1,2 to 0,2\n",
"effort before recurse: 6\n",
"global min_effort after recurse: 6\n",
"global min_effort after recurse: inf\n",
"going from 1,1 to 1,0\n",
"effort before recurse: 6\n",
"going from 1,0 to 2,0\n",
"effort before recurse: 6\n",
"going from 2,0 to 2,1\n",
"effort before recurse: 6\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 6\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"going from 0,1 to 0,2\n",
"effort before recurse: 1\n",
"going from 0,2 to 1,2\n",
"effort before recurse: 1\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 1\n",
"-------------------Found end: effort is 1\n",
"global min_effort after recurse: 1\n",
"going from 1,2 to 1,1\n",
"effort before recurse: 1\n",
"going from 1,1 to 2,1\n",
"effort before recurse: 4\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 1\n",
"going from 2,1 to 2,0\n",
"effort before recurse: 5\n",
"going from 2,0 to 1,0\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"going from 1,1 to 1,0\n",
"effort before recurse: 4\n",
"going from 1,0 to 2,0\n",
"effort before recurse: 5\n",
"going from 2,0 to 2,1\n",
"effort before recurse: 5\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"global min_effort after recurse: inf\n",
"inf\n"
]
}
],
"source": [
"import numpy as np\n",
"import math\n",
"\n",
"min_effort = math.inf\n",
"\n",
"def valid(r,c,visited):\n",
" return 0 <= r < visited.shape[0] and 0 <= c < visited.shape[1] and visited[r,c] == 0\n",
"\n",
"def find_path(heights_arr,visited,r,c,effort,max_row, max_col):\n",
" global min_effort\n",
" \n",
" if r == max_row and c == max_col: \n",
" print(f'-------------------Found end: effort is {effort}')\n",
" return effort\n",
" \n",
" for row,col in ((r+1,c),(r,c+1),(r-1,c),(r,c-1)):\n",
" if valid(row,col,visited):\n",
" print(f'going from {r},{c} to {row},{col}')\n",
" print(f'effort before recurse: {effort}')\n",
" visited[row,col] = 1 \n",
" updated_effort = max(effort, abs(heights_arr[row,col]-heights_arr[r,c])) # possibly update current max effort along path\n",
" \n",
" #recursion_res = find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col)\n",
" #print(f'min_effort:{min_effort} recursion_res:{recursion_res}')\n",
" #min_effort = min(min_effort,recursion_res)\n",
" \n",
" min_effort = min(min_effort,find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col)) # problem\n",
" #min_effort = min(find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col),min_effort)\n",
" \n",
" visited[row,col] = 0\n",
" \n",
" print(f'global min_effort after recurse: {min_effort}')\n",
" \n",
" return math.inf\n",
" #return min_effort\n",
" \n",
"def minimumEffortPath(heights):\n",
" heights_arr = np.array(heights) \n",
" rows, cols = heights_arr.shape\n",
" max_row, max_col = rows-1, cols-1\n",
" \n",
" r,c = 0,0\n",
" visited = np.zeros((rows, cols))\n",
" visited[r,c]=1\n",
" \n",
" effort = 0\n",
" find_path(heights_arr,visited,r,c,effort,max_row, max_col)\n",
"\n",
"\n",
"heights = [[1,2,3],[3,8,4],[5,3,5]]\n",
"minimumEffortPath(heights)\n",
"print(min_effort)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# No global no bounding "
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"ExecuteTime": {
"end_time": "2020-10-31T08:20:39.982800Z",
"start_time": "2020-10-31T08:20:39.961879Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"going from 0,0 to 1,0\n",
"effort before recurse: 0\n",
"going from 1,0 to 2,0\n",
"effort before recurse: 2\n",
"going from 2,0 to 2,1\n",
"effort before recurse: 2\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 2\n",
"-------------------Found end: effort is 2\n",
"global min_effort after recurse: 2\n",
"going from 2,1 to 1,1\n",
"effort before recurse: 2\n",
"going from 1,1 to 1,2\n",
"effort before recurse: 5\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 2\n",
"going from 1,2 to 0,2\n",
"effort before recurse: 5\n",
"going from 0,2 to 0,1\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,1 to 0,1\n",
"effort before recurse: 5\n",
"going from 0,1 to 0,2\n",
"effort before recurse: 6\n",
"going from 0,2 to 1,2\n",
"effort before recurse: 6\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,0 to 1,1\n",
"effort before recurse: 2\n",
"going from 1,1 to 2,1\n",
"effort before recurse: 5\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 2\n",
"going from 2,1 to 2,0\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,1 to 1,2\n",
"effort before recurse: 5\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 2\n",
"going from 1,2 to 0,2\n",
"effort before recurse: 5\n",
"going from 0,2 to 0,1\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,1 to 0,1\n",
"effort before recurse: 5\n",
"going from 0,1 to 0,2\n",
"effort before recurse: 6\n",
"going from 0,2 to 1,2\n",
"effort before recurse: 6\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 0,0 to 0,1\n",
"effort before recurse: 0\n",
"going from 0,1 to 1,1\n",
"effort before recurse: 1\n",
"going from 1,1 to 2,1\n",
"effort before recurse: 6\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 2\n",
"going from 2,1 to 2,0\n",
"effort before recurse: 6\n",
"going from 2,0 to 1,0\n",
"effort before recurse: 6\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,1 to 1,2\n",
"effort before recurse: 6\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 2\n",
"going from 1,2 to 0,2\n",
"effort before recurse: 6\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 1,1 to 1,0\n",
"effort before recurse: 6\n",
"going from 1,0 to 2,0\n",
"effort before recurse: 6\n",
"going from 2,0 to 2,1\n",
"effort before recurse: 6\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 6\n",
"-------------------Found end: effort is 6\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"global min_effort after recurse: 2\n",
"going from 0,1 to 0,2\n",
"effort before recurse: 1\n",
"going from 0,2 to 1,2\n",
"effort before recurse: 1\n",
"going from 1,2 to 2,2\n",
"effort before recurse: 1\n",
"-------------------Found end: effort is 1\n",
"global min_effort after recurse: 1\n",
"going from 1,2 to 1,1\n",
"effort before recurse: 1\n",
"going from 1,1 to 2,1\n",
"effort before recurse: 4\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 1\n",
"going from 2,1 to 2,0\n",
"effort before recurse: 5\n",
"going from 2,0 to 1,0\n",
"effort before recurse: 5\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"going from 1,1 to 1,0\n",
"effort before recurse: 4\n",
"going from 1,0 to 2,0\n",
"effort before recurse: 5\n",
"going from 2,0 to 2,1\n",
"effort before recurse: 5\n",
"going from 2,1 to 2,2\n",
"effort before recurse: 5\n",
"-------------------Found end: effort is 5\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"global min_effort after recurse: 1\n",
"1\n"
]
}
],
"source": [
"import numpy as np\n",
"import math\n",
"\n",
"def valid(r,c,visited):\n",
" return 0 <= r < visited.shape[0] and 0 <= c < visited.shape[1] and visited[r,c] == 0\n",
"\n",
"def find_path(heights_arr,visited,r,c,effort,max_row, max_col,min_effort):\n",
" \n",
" if r == max_row and c == max_col: \n",
" print(f'-------------------Found end: effort is {effort}')\n",
" return effort\n",
" \n",
" for row,col in ((r+1,c),(r,c+1),(r-1,c),(r,c-1)):\n",
" if valid(row,col,visited):\n",
" print(f'going from {r},{c} to {row},{col}')\n",
" print(f'effort before recurse: {effort}')\n",
" \n",
" updated_effort = max(effort, abs(heights_arr[row,col]-heights_arr[r,c])) # possibly update current max effort along path\n",
" \n",
" visited[row,col] = 1\n",
"\n",
" #recursion_res = find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col,min_effort)\n",
" #print(f'min_effort:{min_effort} recursion_res:{recursion_res}')\n",
" \n",
" #min_effort = min(min_effort,find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col,min_effort))\n",
" min_effort = min(find_path(heights_arr,visited,row,col,updated_effort,max_row,max_col,min_effort),min_effort)\n",
"\n",
" visited[row,col] = 0\n",
" print(f'global min_effort after recurse: {min_effort}')\n",
" \n",
" return min_effort\n",
" #return math.inf\n",
" \n",
"def minimumEffortPath(heights):\n",
" min_effort = math.inf\n",
" \n",
" heights_arr = np.array(heights) \n",
" rows, cols = heights_arr.shape\n",
" max_row, max_col = rows-1, cols-1\n",
" \n",
" r,c = 0,0\n",
" visited = np.zeros((rows, cols))\n",
" visited[r,c]=1\n",
" \n",
" effort = 0\n",
" return find_path(heights_arr,visited,r,c,effort,max_row, max_col,min_effort)\n",
"\n",
"#heights = [[1,2,2],[3,8,2],[5,3,5]]\n",
"heights = [[1,2,3],[3,8,4],[5,3,5]]\n",
"#heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]\n",
"#heights = [[1,10,6,7,9,10,4,9]]\n",
"#heights = [[4,3,4,10,5,5,9,2],[10,8,2,10,9,7,5,6],[5,8,10,10,10,7,4,2],[5,1,3,1,1,3,1,9],[6,4,10,6,10,9,4,6]]\n",
"print(minimumEffortPath(heights))\n",
"#print(min_effort)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.3"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment