31:[] 2f:{"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"},{"id":47,"value":"md`## Output`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":51,"value":"md`## Input`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":72,"value":"start = colRowToId(5, 2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":57,"value":"md`## Algorithm`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"id":61,"value":"function colRowToId(col, row) {\n return col + row * cols;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":63,"value":"function idToCol(id) {\n return id % cols;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":65,"value":"function idToRow(id) {\n return Math.floor(id / cols);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"id":22,"value":"html`

CSS

\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":36,"value":"md`## Size of board`","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"cols = 23","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"rows = 9","pinned":false,"hidden":false,"mode":"ojs"},{"id":41,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":43,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}