2c:null 2d:["$","title",null,{"children":"Breadth first search demo | Amit Patel | Observable"}] 32:[] 30:{"id":"b62f719d42128c80","slug":"breadth-first-search-demo","title":"Breadth first search demo","thumbnail":"76dd7482cb2e863ecf0ca9c74516d3e3f14a2bd3ca6a40435e6f6ceb8831086c","access_level":"public","create_time":"$D2020-03-29T22:10:10.178Z","update_time":"$D2021-05-18T21:18:35.098Z","view_time":null,"first_public_time":"$D2020-03-29T22:16:08.503Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"468ec444dc0eb0ae","login":"redblobgames","name":"Amit Patel","avatar_url":"https://avatars-next.observableusercontent.com/e8ff190af9193a0b08dfdadf3fb2e93a0519966417f0c9a2063aae07a171e6b2","tier":"starter_2024"},"version":142,"publish_version":142,"role":null,"authored":false,"authors":[{"type":"individual","id":"c7764e85dbcadc6d","login":"redblobgames","name":"Amit Patel","avatar_url":"https://avatars-next.observableusercontent.com/e8ff190af9193a0b08dfdadf3fb2e93a0519966417f0c9a2063aae07a171e6b2","tier":null}],"members":[{"type":"individual","id":"c7764e85dbcadc6d","login":"redblobgames","name":"Amit Patel","avatar_url":"https://avatars-next.observableusercontent.com/e8ff190af9193a0b08dfdadf3fb2e93a0519966417f0c9a2063aae07a171e6b2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Breadth first search demo","cells":[{"id":0,"value":"md`# Breadth first search demo\n\nThis is part of my [starter page](https://www.redblobgames.com/x/2014-starter-page/) where I show how to make this type of diagram with React, Vue, etc. It's meant to be a starting point for people making their own interactive articles.\n\n**Status**: There are four components: slider input (timeline), algorithm (breadth first search), grid output (showing what the algorithm has explored), and grid input (click on cells to turn them into walls). I don't know how to implement grid input. I haven't figured out out how to make \"viewof\" work for this kind of interaction, or whether I need something else.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"md`## Output`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"{\n let cells = ``;\n for (let col = 0; col < cols; col++) {\n for (let row = 0; row < rows; row++) {\n let id = colRowToId(col, row);\n let state = breadthFirstSearch.frontier.indexOf(id) >= 0? 'frontier' \n : breadthFirstSearch.explored.indexOf(id) >= 0? 'explored'\n : \"\";\n cells += ``;\n }\n }\n\n return svg`\n `\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"md`## Input`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"viewof step = slider({\n min: 0, \n max: cols * rows, \n step: 1, \n value: 10, \n title: \"Step\", \n description: \"Step through the execution\",\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"start = colRowToId(5, 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"md`## Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"breadthFirstSearch = {\n let count = 0;\n let frontier = [start];\n let explored = [start];\n while (frontier.length > 0 && count++ < step) {\n let current = frontier.shift();\n for (let next of neighbors(current)) {\n if (explored.indexOf(next) < 0) {\n frontier.push(next);\n explored.push(next);\n }\n }\n }\n return {frontier, explored};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"md`## Grid representation\n\nJavascript's data types are nowhere near as nice as Python's, \nand we don't have tuples, so I encode them as an integer id.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"function colRowToId(col, row) {\n return col + row * cols;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"function idToCol(id) {\n return id % cols;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"function idToRow(id) {\n return Math.floor(id / cols);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"function inGridRange(col, row) {\n return 0 <= col && col < cols \n && 0 <= row && row < rows;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"function neighbors(id) {\n let col = idToCol(id), \n row = idToRow(id);\n let neighbors = [];\n let candidates = [[col+1, row], [col-1, row], [col, row+1], [col, row-1]];\n for (let candidate of candidates) {\n if (inGridRange(candidate[0], candidate[1])) {\n neighbors.push(colRowToId(candidate[0], candidate[1]));\n }\n }\n return neighbors;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"html`

CSS

\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"md`## Size of board`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"cols = 23","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"rows = 9","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1"}} 31:"$30:body"