30:T5a6,graph = { const rows = input.trim().split("\n").map(s => s.trim().split("")); const nodes = {}; const edges = {}; function getId(y, x) { return `${x},${y},${rows[y][x].toLowerCase()}`; } function addEdge(sourceId, y, x) { // tolerate wonky grids with holes or uneven numbers of rows for now if (rows[y][x]) { const targetId = getId(y, x); edges[sourceId].push(targetId); } } for (let y = 0; y < rows.length; y ++) { const row = rows[y]; for (let x = 0; x < row.length; x ++) { const value = row[x].toLowerCase(); const id = getId(y, x); nodes[id] = value; if (!edges[id]) { edges[id] = []; } if (x > 0) { // left addEdge(id, y, x - 1); if (y > 0) { // up left addEdge(id, y - 1, x - 1); } if (y < rows.length - 1) { // down left addEdge(id, y + 1, x - 1); } } if (x < row.length - 1) { // right addEdge(id, y, x + 1); if (y > 0) { // up right addEdge(id, y - 1, x + 1); } if (y < rows.length - 1) { // down right addEdge(id, y + 1, x + 1); } } if (y > 0) { addEdge(id, y - 1, x); } if (y < rows.length - 1) { addEdge(id, y + 1, x) } } } return { nodes, edges }; }31:[] 2e:{"title":"Solving Boggle","cells":[{"id":0,"value":"md`# Solving Boggle\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"viewof input = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"md`\n${/* TODO: can I embed a `viewof` textarea here? */\"\"}\n### I found __${result.length}__ words, scoring __${score(result)}__:\n\n

${result.map(w => `${w} (${(score([w]))})`).join(\"\\n\")}

\n\nThe dictionary had ${words.length} words.\n\n\n### TODO:\n* UI\n* Generate input from cube distribution\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":139,"value":"test = t.hasPrefix(\"arse\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"result = {\n const { nodes, edges } = graph;\n let words = new Set();\n \n \n function visit(id, idStack, letterStack) {\n if (idStack.includes(id)) {\n return;\n };\n \n idStack.push(id);\n letterStack.push(nodes[id]);\n \n if (letterStack.length >= MIN_LENGTH && t.hasWord(letterStack)) {\n words.add(letterStack.join(\"\"));\n }\n \n if (t.hasPrefix(letterStack)) {\n edges[id].forEach(neighbourId => {\n visit(neighbourId, idStack, letterStack);\n })\n }\n \n idStack.pop();\n letterStack.pop();\n }\n \n const idStack = [];\n const letterStack = [];\n Object.keys(nodes).forEach(id => {\n \tvisit(id, idStack, letterStack);\n })\n \n return [...words].sort((a, b) => b.length - a.length || a.charCodeAt(0) - b.charCodeAt(0));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":204,"value":"score = (words) => words.reduce((sum, word) => sum + word.length - (MIN_LENGTH - 1), 0)","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"t = {\n const t = trie()\n console.log(\"starting...\");\n for (let i = 0; i < words.length; i ++) {\n t.add(words[i]); \n }\n console.log(\"done!\");\n return t;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"words = {\n // 480k words: too much noise\n //const url = \"https://raw.githubusercontent.com/dwyl/english-words/master/words.txt\";\n \n // 235k words: still too much noise\n // \"https://raw.githubusercontent.com/dolph/dictionary/master/unix-words\"\n \n // most common 20k words: contains many real nouns\n // const url = \"https://raw.githubusercontent.com/first20hours/google-10000-english/master/20k.txt\"\n \n // Wiktionary's top 23k words: nice!\n const url = \"https://raw.githubusercontent.com/dolph/dictionary/master/popular.txt\";\n return (await d3.text(url)).split(\"\\n\").map(w => w.trim().toLowerCase());\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"MIN_LENGTH = 3","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"function trie() {\n const root = {};\n const isWord = Symbol(\"isWord\");\n \n return {\n \tadd([...chars]) {\n \tlet node = root;\n \twhile (chars.length > 0) {\n const c = chars.shift();\n if (!node[c]) {\n \tnode[c] = chars.length === 0 ? { [isWord]: true } : {};\n }\n \n node = node[c];\n }\n \n return root;\n },\n \n hasWord([...chars]) {\n \tlet node = root;\n let c;\n \twhile (chars.length > 0) {\n \tc = chars.shift();\n if (!node.hasOwnProperty(c)) {\n \treturn false;\n }\n \n node = node[c];\n }\n \n return node.hasOwnProperty(isWord);\n },\n \n hasPrefix([...chars]) {\n \tlet node = root;\n \twhile (chars.length > 0) {\n \tconst c = chars.shift();\n if (!node.hasOwnProperty(c)) {\n \treturn false;\n }\n \n node = node[c];\n }\n \n return Object.keys(node).length > 0;\n },\n \n root\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"d3 = require(\"d3-fetch@1\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}