2c:null 2d:["$","title",null,{"children":"AOC day 12, hello graphology | Etienne Côme | Observable"}] 32:[{"id":"17e11ee978d67470793889d1ad7baad5689af4a34cc90e85b8afd887edcf676288af099257f50c215a7b3afdd585a5afac8e3845881c6565479fdffffd1c3dad","href":"https://static.observableusercontent.com/files/17e11ee978d67470793889d1ad7baad5689af4a34cc90e85b8afd887edcf676288af099257f50c215a7b3afdd585a5afac8e3845881c6565479fdffffd1c3dad","name":"input_day12_test.txt","type":"text/plain","lastModified":1670839498141.817,"size":45},{"id":"4168a5d0552a23ed76dc781543ddc655aa1a63709d8553b0475c36a5205db6684fda16e4cb2e01ad48685a8d4477d6282ca90e8d14652c27263bcdcf28719d7f","href":"https://static.observableusercontent.com/files/4168a5d0552a23ed76dc781543ddc655aa1a63709d8553b0475c36a5205db6684fda16e4cb2e01ad48685a8d4477d6282ca90e8d14652c27263bcdcf28719d7f","name":"input_day12.txt","type":"text/plain","lastModified":1670844508138.26,"size":7093}] 30:{"id":"ebd8c9a62f1f22f3","slug":null,"title":"AOC day 12, hello graphology","thumbnail":"3db53e8748f4ecf034022d9e8331a696bd0f45008bd05389d412ecf2ee1f59bc","access_level":"public","create_time":"$D2022-12-12T09:58:54.948Z","update_time":"$D2022-12-12T14:54:33.190Z","view_time":null,"first_public_time":"$D2022-12-12T09:58:54.948Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"03f6575ff4fb45fd","login":"comeetie","name":"Etienne Côme","avatar_url":"https://avatars-next.observableusercontent.com/0c3db57846fd0e9ca9ec93f7af6b05bf25598b0b73f102907d6712762c0730fb","tier":"starter_2024"},"version":165,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"bb6334b2e599bc5a","login":"comeetie","name":"Etienne Côme","avatar_url":"https://avatars-next.observableusercontent.com/0c3db57846fd0e9ca9ec93f7af6b05bf25598b0b73f102907d6712762c0730fb","tier":null}],"members":[{"type":"individual","id":"bb6334b2e599bc5a","login":"comeetie","name":"Etienne Côme","avatar_url":"https://avatars-next.observableusercontent.com/0c3db57846fd0e9ca9ec93f7af6b05bf25598b0b73f102907d6712762c0730fb","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"AOC day 12, hello graphology","cells":[{"id":0,"value":"# AOC day 12, hello graphology","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":110,"value":"input_day12 = FileAttachment(\"input_day12.txt\").text()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"graphology = require('graphology')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"GraphologyLibrary = require('graphology-library@0.7.1/dist/graphology-library.min.js')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"elevations=input.replace(\"S\",\"a\").replace(\"E\",\"z\").split(\"\\n\").map(r=>r.split(\"\").map(l=>letter_map[l]))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"nbr = elevations.length","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"nbc = elevations[0].length;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"E = `${Math.floor(input.search(\"E\")/(nbc+1))}-${input.search(\"E\")%(nbc+1)}`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"S = `${Math.floor(input.search(\"S\")/(nbc+1))}-${input.search(\"S\")%(nbc+1)}`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"GraphologyLibrary.shortestPath.unweighted. bidirectional(graph,S,E).length-1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"graph={\n const graph = new graphology.Graph()\n for(let row=0;row=1 && (elevations[row][col]-elevations[row-1][col])>=-1){\n graph.addEdge(`${row}-${col}`,`${row-1}-${col}`);\n }\n \n if(row<=(nbr-2) && (elevations[row][col]-elevations[row+1][col])>=-1){\n graph.addEdge(`${row}-${col}`,`${row+1}-${col}`);\n }\n\n \n if(col>=1 && (elevations[row][col]-elevations[row][col-1])>=-1){\n graph.addEdge(`${row}-${col}`,`${row}-${col-1}`);\n }\n \n if(col<=(nbc-2) && (elevations[row][col]-elevations[row][col+1])>=-1){\n graph.addEdge(`${row}-${col}`,`${row}-${col+1}`);\n }\n }\n }\n return graph\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"graph","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"letter_map={\n let letter_map={}\n \"abcdefghijklmnopqrstuvwxyz\".split(\"\").forEach((elem, i) => {\n letter_map[elem] = i\n })\n return letter_map\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"input=input_day12.slice(0,-1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"input_day12_test = FileAttachment(\"input_day12_test.txt\").text()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"# part 2","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":126,"value":"graph2={\n const graph = new graphology.Graph()\n for(let row=0;row=1 && (elevations[row][col]-elevations[row-1][col])>=-1){\n graph.addEdge(`${row-1}-${col}`,`${row}-${col}`);\n }\n \n if(row<=(nbr-2) && (elevations[row][col]-elevations[row+1][col])>=-1){\n graph.addEdge(`${row+1}-${col}`,`${row}-${col}`);\n }\n\n \n if(col>=1 && (elevations[row][col]-elevations[row][col-1])>=-1){\n graph.addEdge(`${row}-${col-1}`,`${row}-${col}`);\n }\n\n \n if(col<=(nbc-2) && (elevations[row][col]-elevations[row][col+1])>=-1){\n graph.addEdge(`${row}-${col+1}`,`${row}-${col}`);\n }\n }\n }\n return graph\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"{\n const paths = GraphologyLibrary.shortestPath.unweighted.singleSource(graph2,E)\n const ijs = Object.keys(paths).map(k=> k.split(\"-\").map(v=>+v))\n const trek_lengths= ijs.filter( ij=> elevations[ij[0]][ij[1]]==0).map(ij=>paths[ij.join(\"-\")].length-1)\n return trek_lengths.sort((a,b)=>a-b)[0]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"positions = GraphologyLibrary.layoutForceAtlas2()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 31:"$30:body"