2b:null 2c:["$","title",null,{"children":"The Trapped Knight | Otávio Vasques | Observable"}] 31:T43f,svg` `32:[] 2f:{"id":"cc4412f8af519807","slug":"the-trapped-knight","title":"The Trapped Knight","thumbnail":"7f77c861191dfaaa2b1b526e0e863357620541fcb719680973c0612b3fd1df6e","access_level":"public","create_time":"$D2020-04-26T01:47:20.996Z","update_time":"$D2021-10-12T20:44:31.402Z","view_time":null,"first_public_time":"$D2020-04-28T23:35:53.819Z","fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"5e8d11e509318570","login":"otaviocv","name":"Otávio Vasques","avatar_url":"https://avatars-next.observableusercontent.com/21aa1d096ad0538e8d296d94b9560d33bcd6c2c7a3046310d200f7467de1e103","tier":"starter_2024"},"version":458,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"67f6bc0db63009d0","login":"otaviocv","name":"Otávio Vasques","avatar_url":"https://avatars-next.observableusercontent.com/21aa1d096ad0538e8d296d94b9560d33bcd6c2c7a3046310d200f7467de1e103","tier":null}],"members":[{"type":"individual","id":"67f6bc0db63009d0","login":"otaviocv","name":"Otávio Vasques","avatar_url":"https://avatars-next.observableusercontent.com/21aa1d096ad0538e8d296d94b9560d33bcd6c2c7a3046310d200f7467de1e103","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"3b5e5f486b2972b1","slug":"numberphile","title":"Numberphile","owner":{"id":"5e8d11e509318570","login":"otaviocv","name":"Otávio Vasques"}},"type":"notebook","body":{"title":"The Trapped Knight","cells":[{"id":0,"value":"md`# The Trapped Knight\n\nThe Trapped Knight is a simple toy problem where a chess Knight moves in an infinite chess board. I got in touch with the problem through the amazing [Numberphile video](https://www.youtube.com/watch?v=RGQe8waGJ4w). By labeling the chess board with integer numbers in a spiral structure and restricting the Knight moves to the smallest number available, and not visited before, we get a path. But this path is not an infinite path, after 2016 moves the Knight gets trapped. The image below shows the trajectory of the Knight.\n\nThe red circle in the center shows the initial square, the black circle in the bottom shows the last square and the color of the path shows the distance from the initial square.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"numbers = svg`${squaresCoordinates.map(coords => {\n return svg`\n ${ulamSpiral(coords[0], coords[1])}\n `;\n })}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":429,"value":"md`---\n## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"margin = ({top: 30, bottom: 30, left: 30, right: 30})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"squaresCount = maxSquares","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"linearScale = d3.scaleLinear()\n .domain([-squaresCount, squaresCount])\n .range([margin.top, width - margin.bottom])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"squaresIndex = d3.range(-squaresCount, squaresCount+1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"squaresCoordinates = squaresIndex.flatMap(x => {\n return squaresIndex.map(y => {\n return [x,y]\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"fullKnightPath = knightPath(2020)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":328,"value":"maxSquares = Math.max(...fullKnightPath.map(d => Math.max(Math.abs(d[0]), Math.max(d[1]))))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":373,"value":"zip = (arr, ...arrs) => {\n return arr.map((val, i) => arrs.reduce((a, arr) => [...a, arr[i]], [val]));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"function knightPath(steps) {\n var pos = [0, 0];\n var path = [pos];\n var visited = ({});\n visited[pos] = true\n var nextMove = []\n console.log(\"initialPath\", path)\n for (var i=0; i < steps; i++) {\n let nextSquares = knightMoves(pos[0], pos[1]);\n let notVisitedSquares = nextSquares.filter(x => !visited[x]);\n if (notVisitedSquares.length == 0) return path;\n var nextValues = notVisitedSquares.map(c => ulamSpiral(c[0], c[1]));\n var minValue = Math.min(...nextValues);\n nextMove = notVisitedSquares[nextValues.indexOf(minValue)];\n path.push(nextMove);\n visited[nextMove] = true\n pos = nextMove;\n }\n return path;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"function ulamFunction(b, c) {\n return n => 4*n**2 + b*n + c\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"function ulamSpiral(x, y) {\n const n = Math.max(Math.abs(x), Math.abs(y))\n if (x == 0 && y == 0) {\n return 1;\n } else if (-x < y && y <= x) {\n return ulamFunction(-2, 1)(n) - n + y;\n } else if (-y <= x && x < y) {\n return ulamFunction(0, 1)(n) - n - x;\n } else if (x <= y && y < -x) {\n return ulamFunction(1, 1)(n) - y;\n } else if (y < x && x <= -y) {\n return ulamFunction(3, 1)(n) + x;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":446,"value":"ulamSpiral(1,0)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":151,"value":"function knightMoves(x, y) {\n return [[x+2, y-1],\n [x+2, y+1],\n [x+1, y+2],\n [x-1, y+2],\n [x-2, y+1],\n [x-2, y-1],\n [x-1, y-2],\n [x+1, y-2],\n ]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"