2b:null 2c:["$","title",null,{"children":"Dynamic Programming Notes | Philippe Rigovanov | Observable"}] 31:T5fa,min_max_path_general_brute_force = { mode let min_max_path = []; let min_max_path_choices = []; for (let y = 0; y < n; y++) { let row = []; let choice_row = []; min_max_path.push(row); min_max_path_choices.push(choice_row); for (let x = 0; x < n; x++) { row.push(null); choice_row.push(null); } } function* min_max_path_recursive(y, x) { if (y < 0 || x < 0 || y >=n || x >= n) { return 1; } else if (x == 0 && y == 0) { min_max_path[y][x] = grid[y][x]; } else { let choice_values = []; for(let i = 0; i < move_choices.length; i++) { let choice = move_choices[i]; let yp = y + choice.dy; let xp = x + choice.dx; min_max_path_choices[y][x] = {'choice': i, 'confirmed': false}; yield Promises.delay(config.step_time, {values: min_max_path, choices: min_max_path_choices}); let choice_value = yield* min_max_path_recursive(yp, xp); min_max_path_choices[y][x] = null; choice_values.push(choice_value); }; let minMaxPrev = Math.min(...choice_values); let choice_index = choice_values.indexOf(minMaxPrev); if (minMaxPrev < 1) { min_max_path_choices[y][x] = {'choice': choice_index, 'confirmed': true}; } min_max_path[y][x] = Math.max(grid[y][x], minMaxPrev); } yield Promises.delay(config.step_time, {values: min_max_path, choices: min_max_path_choices}); return min_max_path[y][x]; } yield* min_max_path_recursive(n-1, n-1) }32:T55e,function* explore(y, x, n, min_max_path) { console.log("Calling:", y, x); if (y < 0 || x < 0 || y >=n || x >= n) { // Out of bounds set to "max" value that will never be selected return 1; } else if (x == 0 && y == 0) { // Base case min_max_path.values[y][x] = grid[y][x]; } else if (min_max_path.values[y][x] != null) { // Do not explore already-set values. ; }else { // Explore // Get value of each choice. let choice_values = []; let choice_states = move_choices.map(choice => ({'y': y + choice.dy, 'x': x + choice.dx})) for(let i = 0; i < choice_states.length; i++) { let choice_state = choice_states[i] min_max_path.choices[y][x] = {'choice': i, 'confirmed': false}; yield Promises.delay(config.step_time, min_max_path); let choice_value = yield* explore(choice_state.y, choice_state.x, n, min_max_path); min_max_path.choices[y][x] = null; choice_values.push(choice_value); }; // Select optimal choice. let minMaxPrev = Math.min(...choice_values); let choice_index = choice_values.indexOf(minMaxPrev); if (minMaxPrev < 1) { min_max_path.choices[y][x] = {'choice': choice_index, 'confirmed': true}; } min_max_path.values[y][x] = Math.max(grid[y][x], minMaxPrev); } yield Promises.delay(config.step_time, min_max_path); return min_max_path.values[y][x]; }33:[] 2f:{"id":"71a03a407ea7f18f","slug":null,"title":"Dynamic Programming Notes","thumbnail":"36b4baadcf4b7ce8a27c70c92d49ecc706ff47166a02f0ef7a65e8df188c86a2","access_level":"public","create_time":"$D2022-12-30T20:28:54.859Z","update_time":"$D2022-12-30T20:28:54.859Z","view_time":null,"first_public_time":"$D2022-12-30T20:28:54.859Z","fork":{"id":"ad6a747e2d9666ab","slug":"dynamic-programming-notes","title":"Dynamic Programming Notes","owner":{"id":"8489e49d3b4f5a95","login":"2timesjay","name":""}},"stars":0,"starred":false,"owner":{"type":"team","id":"b5ee25cc13065361","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":"starter_2024"},"version":1184,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"968f76daa2a26d11","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":null}],"members":[{"type":"individual","id":"968f76daa2a26d11","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"f12a3f64915c0078","slug":"informatics","title":"Informatics","owner":{"id":"b5ee25cc13065361","login":"a1ip","name":"Philippe Rigovanov"}},"type":"notebook","body":{"title":"Dynamic Programming Notes","cells":[{"id":0,"value":"md`# Dynamic Programming Notes`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":695,"value":"md`Consider a problem where your objective is to minimize the cost of a sequence of actions that reach a target state.\n\nNote that minimizing and maximize can be interchanged, but we select minimization here as a convention.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":717,"value":"md`Let ${tex`c_\\varnothing`} be the cost of the base state.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":19,"value":"tex`f(\\varnothing) = c_\\varnothing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":700,"value":"md`Let ${tex`T`} be the target state.\n\nLet ${tex`T_{-a}`} be the state from which selecting action ${tex`a`} will induce state ${tex`T`}.\n\nLet ${tex`c_a`} be the cost of action ${tex`a`}. \n\n${tex`a`} comes from set ${tex`A_T`}, the set of actions that can lead immediately from other states to T.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11,"value":"md`Finally,\n\nLet ${tex`f(T) = min_{a \\in A_T} f(T_{-a}) + c_a`}\n\n${tex`f(T)`} is the optimal value of the optimal action choice function defined recursively. \n\nAssuming some sequence of actions can bring us from ${tex`\\varnothing`} to ${tex`T`}, the minimizing a at each step yields our solution.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"md`Three ways to explore this.\n* Brute force recursive calls compute the value of ${tex`f(T)`}. We enumerates every valid sequence of actions and compares cost.\n* Memoization is the same as brute force recursive search except it caches discovered costs of any intermediate state ${tex`I`} in a lookup table of ${tex`f(I)`} value. This results in the lookup table being populated in postorder traversal of the depth-first-search tree formed by the recursive exploration.\n* Dynamic programming populates values starting from the base cost and systematically filling out a table of intermediate state costs.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1179,"value":"md`## Takeaway\n\nDynamic programming and memoization are very nearly the same, except the order they make certain calculations.\n\nI personally favor recursion as simpler and having a slightly more universal formulation (and saving us from the bookkeeping of choosing how to fill in the values) but dynamic programming is often more efficient and won't create a stack overflow by recursing too deeply.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":47,"value":"md`## Demo: Lowest Peak Path\n\nFind the path from upper left to lower right of a grid that has the lowest max value along its path, like a path through a mountain range that has the lowest peak altitude.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":787,"value":"tex`f(T) = min_{a \\in A_T} max(f(T_{-a}), c_a)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":793,"value":"md`In the case of grid-like movement where we can only move right or down:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":791,"value":"tex`f(T_{n,n}) = min(max(f(T_{n-1, n}), c_{n, n}), max(f(T_{n, n-1}), c_{n, n}))`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":809,"value":"md`I recommend runnning the demo below with Iterative/Grid and Recursive/Grid settings, to see the two algorithms behaving very similarly, then with Iterative/Knight and Recursive/Knight to see them behaving differently. Then Run brute force when you have a good chunk of spare time!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":568,"value":"viewof mode = radio({\n title: 'Select Algorithm Type',\n description: 'Please select your preferred algorithmic approach',\n options: [\n { label: 'Brute Force (aka Naive)', value: 'brute_force' },\n { label: 'Recursive (aka Memoization)', value: 'recursive' },\n { label: 'Iterative (aka Dynamic Programming)', value: 'iterative' },\n ],\n value: 'recursive'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":648,"value":"viewof movement = radio({\n title: 'Movements available',\n description: 'Please select your preferred movement type, or create your own (but do nott allow cycles!)',\n options: [\n { label: 'Grid: Move down or right', value: 'grid' },\n { label: 'Knight: Jump 2 spaces down and 1 right or 2 right and 1 down', value: 'knight' },\n { label: 'Crazy: will not work with iterative', value: 'crazy' },\n ],\n value: 'grid'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":780,"value":"movement_options = ({\n 'grid': [{'dy': -1, 'dx': 0}, {'dy': 0, 'dx': -1}],\n 'knight': [{'dy': -1, 'dx': -2}, {'dy': -2, 'dx': -1}],\n // 'crazy': [{'dy': -4, 'dx': -3}, {'dy': -2, 'dx': -2}, {'dy': 2, 'dx': -1}, {'dy': 1, 'dx': -2}],\n 'crazy': [{'dy': 1, 'dx': -1}, {'dy': -3, 'dx': -1}, {'dy': -1, 'dx': -1}, {'dy': 1, 'dx': -2}],\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":104,"value":"viewof gridDisplay = {\n const canvas = DOM.canvas(n*size, n*size);\n const context = canvas.getContext(\"2d\");\n context.canvas.value = context;\n return context.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":472,"value":"config = ({\n 'size': 60,\n 'n': 10,\n 'step_time': 100,\n 'show_other_choices': false,\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":659,"value":"md`## Utilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":215,"value":"grid = {\n let d = n\n let grid = [] \n for (let y = 0; y < d; y++) {\n let row = [];\n grid.push(row);\n for (let x = 0; x < d; x++) {\n row.push(Math.random());\n }\n }\n return grid\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":121,"value":"redraw = {\n // VIEW\n const gridContext = gridDisplay;\n redrawGridDisplay(\n gridContext, \n grid,\n 'blue',\n true\n )\n redrawGridDisplay(\n gridContext, \n min_max_path_program.values,\n 'red',\n false\n )\n redrawLineDisplay(\n gridContext, \n min_max_path_program.choices,\n 'black',\n false\n )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":666,"value":"md`## Core Algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":603,"value":"md`### Brute Force`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":607,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":286,"value":"md`### Recursive`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":955,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":299,"value":"min_max_path_general_recursive = {\n mode\n let min_max_path = initialize_min_max_path(n);\n yield* explore(n-1, n-1, n, min_max_path);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":292,"value":"md`### Iterative`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":898,"value":"min_max_path_general_iterative = {\n mode\n let min_max_path = initialize_min_max_path(n)\n for (let y = 0; y < n; y++) {\n for (let x = 0; x < n; x++) {\n yield* explore(y, x, n, min_max_path);\n yield Promises.delay(config.step_time, {values: min_max_path.values, choices: min_max_path.choices});\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":854,"value":"md`## Utilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":853,"value":"function initialize_min_max_path(n) {\n let min_max_path = {values: [], choices: []};\n for (let y = 0; y < n; y++) {\n let row = [];\n let choice_row = [];\n min_max_path.values.push(row);\n min_max_path.choices.push(choice_row);\n for (let x = 0; x < n; x++) {\n row.push(null);\n choice_row.push(null);\n }\n }\n return min_max_path\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":847,"value":"md`## Animation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":223,"value":"tick = {\n while (true) {\n yield Promises.delay(1000);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":125,"value":"function redrawGridDisplay(context, grid, clr, clear) {\n if (clear) { context.clearRect(0, 0, n*size, n*size); }\n const canvas = context.canvas;\n \n function showGrid(grid){\n for (let x = 0; x < grid.length; x++) {\n let row = grid[x];\n for (let y = 0; y < row.length; y++) {\n let val = row[y];\n if (val > 0) {\n let square = new SquareDisplay(val, y, x);\n square.render(context, clr);\n }\n }\n }\n } \n showGrid(grid);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":368,"value":"function redrawLineDisplay(context, lines, clr, clear) {\n if (clear) { context.clearRect(0, 0, n*size, n*size); }\n const canvas = context.canvas;\n function showLines(lines){\n for (let x = 0; x < lines.length; x++) {\n let row = lines[x];\n for (let y = 0; y < row.length; y++) {\n let chosen = row[y];\n if (chosen != null) {\n let choice = move_choices[chosen.choice];\n let confirmed = chosen.confirmed;\n let line = new LineDisplay(y, x, choice.dx, choice.dy);\n let color = confirmed ? clr : 'yellow';\n line.render(context, color);\n for (let i = 0; i < move_choices.length; i++) {\n if (i != chosen && config.show_other_choices) {\n let choice = move_choices[i];\n let unchosen_line = new LineDisplay(y, x, choice.dx, choice.dy);\n unchosen_line.render(context, 'yellow');\n }\n }\n }\n }\n }\n } \n showLines(lines);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":362,"value":"class LineDisplay {\n constructor(y, x, dy, dx) {\n this.dy = dy * size;\n this.dx = dx * size;\n this.y = y * size + 0.5 * size;\n this.x = x * size + 0.5 * size;\n }\n \n render(context, clr) {\n makeLine(this.y, this.x, this.dy, this.dx, context, size, clr, 1.0)\n }\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":127,"value":"class SquareDisplay {\n constructor(value, x, y) {\n const ratio = 1.0;\n this.value = value;\n this.x = x;\n this.y = y;\n this.xOffset = this.x * size + (1.0 - ratio)/2.0 * size;\n this.yOffset = this.y * size + (1.0 - ratio)/2.0 * size;\n this.size = size * ratio;\n this.width = size * ratio;\n this.height = size * ratio;\n }\n \n render(context, clr) {\n if (this.value == 0) { return; }\n makeRect(this.xOffset, this.yOffset, context, this.size, clr, this.value*this.value);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":129,"value":"function makeRect(x, y, context, size, clr, lfa){\n const alpha = lfa == undefined ? 1.0 : lfa;\n const color = clr == undefined ? \"#000000\" : clr;\n context.globalAlpha = alpha;\n context.beginPath();\n context.clearRect(x, y, size, size);\n context.rect(x, y, size, size);\n context.fillStyle = color;\n context.fill();\n // context.lineWidth = 4;\n // context.strokeStyle = 'black';\n // context.stroke();\n context.globalAlpha = 1.0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":357,"value":"function makeLine(y, x, dy, dx, context, size, clr, lfa){\n const alpha = lfa == undefined ? 1.0 : lfa;\n const color = clr == undefined ? \"#000000\" : clr;\n context.globalAlpha = alpha;\n context.beginPath();\n context.moveTo(y, x);\n context.lineTo(y + dy, x + dx);\n context.lineWidth = size/5.0;\n context.strokeStyle = color;\n context.stroke();\n context.globalAlpha = 1.0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":506,"value":"md`### Config Setup`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":482,"value":"size = config.size","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":508,"value":"n = config.n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":515,"value":"move_choices = {\n return movement_options[movement]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":525,"value":"min_max_path_program = {\n const options = {\n 'brute_force': min_max_path_general_brute_force,\n 'recursive': min_max_path_general_recursive,\n 'iterative': min_max_path_general_iterative,\n }\n return options[mode]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":580,"value":"import {radio} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"