2a:null 2b:["$","title",null,{"children":"AoC22 - Jour 12 | linard-y | Observable"}] 31:Ta29,## --- Jour 12 : Algorithme d'escalade --- Vous essayez de contacter les Elfes à l'aide de votre appareil portatif , mais la rivière, au fond de la gorge, que vous suivez doit être trop basse pour obtenir un signal suffisant. Vous demandez à l'appareil une carte topographique de la zone environnante. La carte montre la zone locale divisée en une grille ; l'élévation de chaque carré de la grille est donnée par une seule lettre minuscule, où `a` est l'élévation la plus basse, `b` est la suivante la plus basse, et ainsi de suite jusqu'à l'élévation la plus élevée, `z`. La carte topographique comprend également des repères pour votre position actuelle (S) et l'emplacement qui devrait recevoir le meilleur signal (E). Votre position actuelle (S) a une élévation `a`, et l'emplacement qui devrait recevoir le meilleur signal (E) a une élévation `z`. #### _Question 1_ Vous aimeriez atteindre E, mais pour économiser de l'énergie, vous devez le faire en aussi peu d'étapes que possible. À chaque étape, vous pouvez vous déplacer exactement d'une case vers le Nord, le Sud, l'Ouest ou l'Est. Pour éviter d'avoir à sortir votre matériel d'escalade, l'élévation de la case de destination ne peut être supérieure que d'au plus une unité par rapport à l'élévation de votre case actuelle ; c'est-à-dire que si votre élévation actuelle est `m`, vous pouvez passer à l'élévation `n`, mais pas à l'élévation `o`. (Cela signifie également que l'élévation de la case de destination peut être bien inférieure à l'élévation de votre case actuelle.) Par exemple: **S**abqponm abcryxxl accsz**E**xk acctuvwj abdefghi Ici, vous commencez dans le coin supérieur gauche ; votre objectif est proche du milieu. Vous avez la possibilité de vous déplacer vers le Sud ou vers l'Est, mais le plus court chemin sera la case au Sud. De là, vous pourrez continuer vers l'objectif : | v | . | . | v | < | < | < | < | | > |v | . | v | v | < | < | ^ | | . | > | v | v | > | **E** | ^ | ^ | | . | . | v | > | > | > | ^ | ^ | | . | . | > | > | > | > | > | ^ | Dans le diagramme ci-dessus, les symboles indiquent la direction pour sortir de chaque case : vers le Nord (^), vers le Sud (v), vers l'Ouest (<) ou vers l'Est (>). L'emplacement qui devrait recevoir le meilleur signal est toujours E, et `.` marque les places non visitées. Ce chemin atteint le but en 31 étapes, le moins possible. **Quel est le moins d'étapes nécessaires pour passer de votre position actuelle à l'emplacement qui devrait recevoir le meilleur signal ?**32:Tdec,class Grille { constructor(n, m, startIndex, endIndex, values) { this.n = n; this.m = m; this.startIndex = startIndex; this.endIndex = endIndex; this.values = values; } *[Symbol.iterator]() { for (let y = 0, i = 0; y < this.n; ++y) { for (let x = 0; x < this.m; ++x, ++i) { yield [x, y, this.values[i]]; } } } *range() { for (let i = 0, n = this.n * this.m; i < n; ++i) { yield i; } } heightAt(i) { return this.values[i]; } *outgoingEdgesAt(i) { const h = this.heightAt(i) + 1; const [x, y] = this.position(i); if (0 < y && this.heightAt(i - this.m) <= h) yield i - this.m; if (y < this.n - 1 && this.heightAt(i + this.m) <= h) yield i + this.m; if (0 < x && this.heightAt(i - 1) <= h) yield i - 1; if (x < this.m - 1 && this.heightAt(i + 1) <= h) yield i + 1; } *incomingEdgesAt(i) { const h = this.heightAt(i) - 1; const [x, y] = this.position(i); if (0 < y && this.heightAt(i - this.m) >= h) yield i - this.m; if (y < this.n - 1 && this.heightAt(i + this.m) >= h) yield i + this.m; if (0 < x && this.heightAt(i - 1) >= h) yield i - 1; if (x < this.m - 1 && this.heightAt(i + 1) >= h) yield i + 1; } index(x, y) { return this.m * y + x; } x(i) { return i % this.m; } y(i) { return Math.floor(i / this.m); } position(i) { return [this.x(i), this.y(i)]; } visualise(startIndex, endIndex = this.endIndex, paths = this.shortestPaths(endIndex)) { return Plot.plot({ padding: 0, height: this.n * 24 + 20, width: this.m * 24 + 20, margin: 0, axis: null, color: { scheme: "blues" }, marks: [ Plot.cell(this, { fill: "2", inset: 0.5 }), startIndex === undefined ? Plot.arrow(paths, { filter: (j) => j >= 0, x1: (j, i) => this.x(i), y1: (j, i) => this.y(i), x2: (j, i) => this.x(j), y2: (j, i) => this.y(j), stroke: "red", inset: 4 }) : Plot.line(this.shortestPath(startIndex, endIndex, paths), { stroke: "red", strokeWidth: 3 }), Plot.text(this, { text: "2" }) ] }); } shortestPaths(endIndex = this.endIndex) { const visited = new Uint8Array(this.n * this.m); const distance = new Float64Array(this.n * this.m).fill(Infinity); const next = Int32Array.from({length: this.n * this.m}, (_, i) => i); next.distance = distance; let currentIndex = endIndex; distance[currentIndex] = 0; do { const currentDistance = distance[currentIndex] + 1; for (const nextIndex of this.incomingEdgesAt(currentIndex)) { if (currentDistance < distance[nextIndex]) { distance[nextIndex] = currentDistance; next[nextIndex] = currentIndex; } } visited[currentIndex] = 1; currentIndex = d3.minIndex(distance, (d, i) => (visited[i] ? NaN : d)); } while (distance[currentIndex] < Infinity); return next; } shortestPath(startIndex = this.startIndex, endIndex = this.endIndex, paths = this.shortestPaths(endIndex)) { const path = [this.position(startIndex)]; while (startIndex !== endIndex) { const nextIndex = paths[startIndex]; if (nextIndex === startIndex) break; // path not found path.push(this.position(nextIndex)); startIndex = nextIndex; } return path; } }33:T51d,#### _Question 2_ En montant une colline, vous pensez que le trajet que vous suivez pourrait bien devenir un sentier de randonnée pour les Elfes. Le début n'est cependant pas très pittoresque ; peut-être pouvez-vous trouver un meilleur point de départ. Pour maximiser l'exercice physique pendant la randonnée, le sentier doit commencer le plus bas possible : altitude `a`. Le but est toujours la case marqué E. Cependant, la piste doit toujours être directe, en faisant le moins de pas possible pour atteindre son objectif. Ainsi, vous devrez trouver le chemin le plus court depuis n'importe quelle case en altitude a jusqu'à la case marquée E. Considérons à nouveau l'exemple ci-dessus : Sabqponm abcryxxl accszExk acctuvwj abdefghi Maintenant, il y a six choix pour la position de départ (cinq marqués a, plus le carré marqué S qui compte comme étant à l'élévation a). Si vous commencez par la case en bas à gauche, vous pouvez atteindre l'objectif le plus rapidement : ...v<<<< ...vv<<^ ...v>E^^ .>v>>>^^ >^>>>>>^ > Ce chemin atteint le but en seulement 29 étapes, le moins possible. **Quel est le moins de pas requis pour se déplacer à partir de n'importe quelle case avec une élévation ajusqu'à l'emplacement qui devrait recevoir le meilleur signal ?**34:[{"id":"787f83cbc15dc18c42c3f849dbe6403dff9b0012c4d9d6d2a628c14c60d9fd2e559ca4fca697960b1d6371342fb3dbd80429152357f5a1880d955a0ccded77c0","href":"https://static.observableusercontent.com/files/787f83cbc15dc18c42c3f849dbe6403dff9b0012c4d9d6d2a628c14c60d9fd2e559ca4fca697960b1d6371342fb3dbd80429152357f5a1880d955a0ccded77c0","name":"AoC_day12.txt","type":"text/plain","lastModified":1671114724271.799,"size":5904}] 2e:{"id":"a082ed51ec204b4d","slug":"advent-of-code-2022_day12","title":"AoC22 - Jour 12","thumbnail":"3175cdc10c49c5ad89aaa87a14c9ad853845f0e59679f612d0d059754db4fbb8","access_level":"public","create_time":"$D2022-12-15T14:04:44.039Z","update_time":"$D2022-12-15T14:55:11.336Z","view_time":null,"first_public_time":"$D2022-12-15T14:04:44.039Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"9784867a3e59436b","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":"starter_2024"},"version":56,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null}],"members":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"5a7d4476817b0d1c","slug":"advent-of-code-2022","title":"Advent of Code 2022","owner":{"id":"9784867a3e59436b","login":"linard-y","name":""}},"type":"notebook","body":{"title":"AoC22 - Jour 12","cells":[{"id":0,"value":"# AoC22 - Jour 12\n\nhttps://adventofcode.com/2022/day/12","pinned":false,"hidden":false,"mode":"md"},{"id":15,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":26,"value":"input = FileAttachment(\"AoC_day12.txt\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"function Altitude(char) {\n return char === \"S\" ? Altitude(\"a\")\n : char === \"E\" ? Altitude(\"z\")\n : char.charCodeAt(0) - \"a\".charCodeAt(0);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"function Topo(input) {\n const rows = input.trim().split(\"\\n\");\n const n = rows.length;\n const m = rows[0].length;\n const values = rows.flatMap((line) => line.split(\"\"));\n const startIndex = values.indexOf(\"S\");\n const endIndex = values.indexOf(\"E\");\n return new Grille(n, m, startIndex, endIndex, values.map(Altitude));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":43,"value":"carte = Topo(input)","pinned":false,"hidden":false,"mode":"ojs"},{"id":46,"value":"carte.visualise(carte.startIndex)","pinned":true,"hidden":false,"mode":"ojs"},{"id":51,"value":"carte.shortestPath().length - 1","pinned":true,"hidden":false,"mode":"ojs"},{"id":55,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":53,"value":"d3.min(carte.shortestPaths().distance, (d, i) => carte.heightAt(i) === 0 ? d : NaN)","pinned":true,"hidden":false,"mode":"ojs"},{"id":13,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":9,"value":"navigation(12)","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"import {navigation} from \"@linard-y/advent-of-code-2022_day0\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}} 2f:"$2e:body"