2a:null 2b:["$","title",null,{"children":"AoC22 - Jour 9 | linard-y | Observable"}] 31:T1343,## --- Neuvième jour : Pont de singe --- Le pont de cordes que vous empruntez grince à chacun de vos pas. Vous ne savez pas quel âge ce pont peut avoir ou s'il peut vraiment supporter votre poids. Il semble cependant avoir bien supporté le poids des Elfes qui vous précédaient. Le pont enjambe une gorge profonde qui a été creusée par une rivière torrentielle qui s'écoule en dessous de vous. Vous marchez prudemment; pendant que vous le faites, les cordes s'étirent et se tordent. Vous décidez d'extirper vos pensées de l'angoisse de la corde qui casse en distrayant votre esprit : en modélisant la physique des cordes ! Peut-être que cela vous permettra de comprendre où ne pas marcher. #### _Question 1_ Considérez une corde avec un nœud à chaque extrémité ; ces nœuds marquent la tête et la queue de la corde. Si la tête s'éloigne suffisamment de la queue, la queue est tirée vers la tête. En raison d'un raisonnement nébuleux impliquant des longueurs de Planck vous devriez pouvoir modéliser les positions des nœuds sur une grille à deux dimensions. Ensuite, en suivant une série hypothétique de mouvements pour la tête, vous pouvez déterminer comment la queue se déplacera. En raison des longueurs de Planck susmentionnées, la corde doit être assez courte ; en fait, la tête (H) et la queue (T) doivent toujours se toucher (diagonalement adjacents et même se chevauchant, les deux comptent comme se touchant) : .... .TH. .... .... .H.. ..T. .... ... .H. (H covers T) ... Si la tête est à deux pas directement vers le Nord, le Sud, l'Ouest ou l'Est de la queue, la queue doit également se déplacer d'un pas dans cette direction pour rester suffisamment proche : ..... ..... ..... .TH.. -> .T.H. -> ..TH. ..... ..... ..... ... ... ... .T. .T. ... .H. -> ... -> .T. ... .H. .H. ... ... ... Sinon, si la tête et la queue ne se touchent pas et ne sont pas dans la même ligne ou colonne, la queue se déplace toujours d'un pas en diagonale pour suivre : ..... ..... ..... ..... ..H.. ..H.. ..H.. -> ..... -> ..T.. .T... .T... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..H.. -> ...H. -> ..TH. .T... .T... ..... ..... ..... ..... Vous avez juste besoin de déterminer où va la queue pendant que la tête suit une série de mouvements. Supposons que la tête et la queue commencent toutes les deux à la même position, se chevauchant. Par exemple: R 4 U 4 L 3 D 1 R 4 D 1 L 5 R 2 Cette série de mouvements déplace la tête vers l'Est de quatre pas , puis vers le Nord de quatre pas, puis vers l'Ouest de trois pas, puis vers le Sud d'un pas, et ainsi de suite. Après chaque étape, vous devrez mettre à jour la position de la queue si l'étape signifie que la tête n'est plus adjacente à la queue. Visuellement, ces mouvements se produisent comme suit ( `s` marque la position de départ) : == État initiale == ...... ...... ...... ...... H..... (H chevauche T et s) == R 4 == ...... ...... ...... ...... TH.... (T chevauche s) ...... ...... ...... ...... sTH... ...... ...... ...... ...... s.TH.. ...... ...... ...... ...... s..TH. == U 4 == ...... ...... ...... ....H. s..T.. ...... ...... ....H. ....T. s..... ...... ....H. ....T. ...... s..... ....H. ....T. ...... ...... s..... == L 3 == ...H.. ....T. ...... ...... s..... ..HT.. ...... ...... ...... s..... .HT... ...... ...... ...... s..... == D 1 == ..T... .H.... ...... ...... s..... == R 4 == ..T... ..H... ...... ...... s..... ..T... ...H.. ...... ...... s..... ...... ...TH. ...... ...... s..... ...... ....TH ...... ...... s..... == D 1 == ...... ....T. .....H ...... s..... == L 5 == ...... ....T. ....H. ...... s..... ...... ....T. ...H.. ...... s..... ...... ...... ..HT.. ...... s..... ...... ...... .HT... ...... s..... ...... ...... HT.... ...... s..... == R 2 == ...... ...... .H.... (H cchevauche T) ...... s..... ...... ...... .TH... ...... s..... Après avoir simulé la corde, vous pouvez compter toutes les positions que la queue a visitées au moins une fois . Dans ce schéma, `s` marque à nouveau la position de départ (que la queue a également visitée) et `#` marque d'autres positions que la queue a visitées : ..##.. ...##. .####. ....#. s###.. Alors il y a 13 positions que la queue a visité au moins une fois. **Simulez votre série hypothétique complète de mouvements. Combien de positions la queue de la corde visite-t-elle au moins une fois ?**32:T27f0,#### -Question 2_ Une corde casse ! Soudain, la rivière se rapproche beaucoup plus que vous ne vous en souvenez. Le pont est toujours là, mais certaines des cordes qui se sont cassées fouettent maintenant vers vous alors que vous tombez dans les airs ! Les cordes se déplacent trop rapidement pour être saisies ; vous n'avez que quelques secondes pour choisir comment cambrer votre corps pour éviter d'être touché. Heureusement, votre simulation peut être étendue pour supporter des cordes plus longues. Plutôt que deux nœuds, vous devez maintenant simuler une corde composée de dix nœuds. Un nœud est toujours la tête de la corde et se déplace selon la série de mouvements. Chaque nœud plus bas sur la corde suit le nœud devant lui en utilisant les mêmes règles qu'auparavant. En utilisant la même série de mouvements que dans l'exemple ci-dessus, mais avec les nœuds marqués H, 1, 2, ..., 9, les mouvements se produisent maintenant comme suit : == Etat initiale == ...... ...... ...... ...... H..... (H chevauche 1, 2, 3, 4, 5, 6, 7, 8, 9, s) == R 4 == ...... ...... ...... ...... 1H.... (1 chevauche 2, 3, 4, 5, 6, 7, 8, 9, s) ...... ...... ...... ...... 21H... (2 chevauche 3, 4, 5, 6, 7, 8, 9, s) ...... ...... ...... ...... 321H.. (3 chevauche 4, 5, 6, 7, 8, 9, s) ...... ...... ...... ...... 4321H. (4 chevauche 5, 6, 7, 8, 9, s) == U 4 == ...... ...... ...... ....H. 4321.. (4 chevauche 5, 6, 7, 8, 9, s) ...... ...... ....H. .4321. 5..... (5 chevauche 6, 7, 8, 9, s) ...... ....H. ....1. .432.. 5..... (5 chevauche 6, 7, 8, 9, s) ....H. ....1. ..432. .5.... 6..... (6 chevauche 7, 8, 9, s) == L 3 == ...H.. ....1. ..432. .5.... 6..... (6 chevauche 7, 8, 9, s) ..H1.. ...2.. ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) .H1... ...2.. ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) == D 1 == ..1... .H.2.. ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) == R 4 == ..1... ..H2.. ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) ..1... ...H.. (H chevauche 2) ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...1H. (1 covers 2) ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...21H ..43.. .5.... 6..... (6 chevauche 7, 8, 9, s) == D 1 == ...... ...21. ..43.H .5.... 6..... (6 chevauche 7, 8, 9, s) == L 5 == ...... ...21. ..43H. .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...21. ..4H.. (H chevauche 3) .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...2.. ..H1.. (H chevauche 4; 1 chevauche 3) .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...2.. .H13.. (1 chevauche 4) .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...... H123.. (2 chevauche 4) .5.... 6..... (6 chevauche 7, 8, 9, s) == R 2 == ...... ...... .H23.. (H chevauche 1; 2 chevauche 4) .5.... 6..... (6 chevauche 7, 8, 9, s) ...... ...... .1H3.. (H chevauche 2, 4) .5.... 6..... (6 chevauche 7, 8, 9, s) Maintenant, vous devez garder une trace des positions de la nouvelle queue, 9, visites. Dans cet exemple, la queue ne bouge jamais et ne visite donc que 1position. Cependant, soyez prudent : plus de types de mouvement sont possibles qu'auparavant, vous voudrez peut-être comparer visuellement votre corde simulée à celle ci-dessus. Voici un exemple plus grand : R 5 U 8 L 8 D 3 R 17 D 10 L 25 U 20 Ces mouvements se produisent comme suit (les étapes individuelles ne sont pas représentées) : == Etat initiale == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........H.............. (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s) .......................... .......................... .......................... .......................... .......................... == R 5 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........54321H......... (5 covers 6, 7, 8, 9, s) .......................... .......................... .......................... .......................... .......................... == U 8 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... ................H......... ................1......... ................2......... ................3......... ...............54......... ..............6........... .............7............ ............8............. ...........9.............. (9 covers s) .......................... .......................... .......................... .......................... .......................... == L 8 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... ........H1234............. ............5............. ............6............. ............7............. ............8............. ............9............. .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... == D 3 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .........2345............. ........1...6............. ........H...7............. ............8............. ............9............. .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... == R 17 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ................987654321H .......................... .......................... .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... == D 10 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........s.........98765 .........................4 .........................3 .........................2 .........................1 .........................H == L 25 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... H123456789................ == U 20 == H......................... 1......................... 2......................... 3......................... 4......................... 5......................... 6......................... 7......................... 8......................... 9......................... .......................... .......................... .......................... .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... Maintenant, la queue ( 9) visites 36postes (y compris s) au moins une fois: .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... #......................... #.............###......... #............#...#........ .#..........#.....#....... ..#..........#.....#...... ...#........#.......#..... ....#......s.........#.... .....#..............#..... ......#............#...... .......#..........#....... ........#........#........ .........########......... Simulez votre série complète de mouvements sur une corde plus grande avec dix nœuds. **Combien de positions la queue de la corde visite-t-elle au moins une fois ?** 33:[{"id":"d9d619911bf640e0ae3c9ffb89cbba0e56336d29e6765c2a6af9753741826f3714c4b4650e890e2e965d44ad60fb44d19b3dfed64fec299a0cb876e179a6ad44","href":"https://static.observableusercontent.com/files/d9d619911bf640e0ae3c9ffb89cbba0e56336d29e6765c2a6af9753741826f3714c4b4650e890e2e965d44ad60fb44d19b3dfed64fec299a0cb876e179a6ad44","name":"AoC_day9.txt","type":"text/plain","lastModified":1671010600215.233,"size":8389}] 2e:{"id":"02f98abbfcc30860","slug":"advent-of-code-2022_day9","title":"AoC22 - Jour 9","thumbnail":"220b5d2edacfa3741bede87d3d22a882f63e6172e376076ff03bb803cf5614f3","access_level":"public","create_time":"$D2022-12-11T13:47:02.102Z","update_time":"$D2022-12-14T09:58:55.536Z","view_time":null,"first_public_time":"$D2022-12-11T13:47:02.102Z","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":100,"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 9","cells":[{"id":0,"value":"# AoC22 - Jour 9\n\nhttps://adventofcode.com/2022/day/9","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":24,"value":"..##.. \n...##. \n.####. \n....#. \ns###.. \n\nAlors il y a 13 positions que la queue a visité au moins une fois.\n\n**Simulez votre série hypothétique complète de mouvements. Combien de positions la queue de la corde visite-t-elle au moins une fois ?**","pinned":false,"hidden":false,"mode":"md"},{"id":51,"value":"input = FileAttachment(\"AoC_day9.txt\").text()","pinned":true,"hidden":false,"mode":"ojs"},{"id":33,"value":"function interprèteDéplacement(input) {\n let [direction, length] = input.split(/\\s+/);\n if (!/^[RULD]$/.test(direction)) throw new Error(`direction invalide : ${input}`);\n if (!Number.isInteger(length = +length)) throw new Error(`longueur invalide: ${input}`);\n return {direction, length};\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"function interprèteDéplacements(input) {\n return input.trim().split(\"\\n\").map(interprèteDéplacement);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"déplacements = interprèteDéplacements(input)","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"function* parcours(d) {\n let x = 0;\n let y = 0;\n yield [x, y];\n for (const {direction, length} of d) {\n switch (direction) {\n case \"L\": for (let i = 0; i < length; ++i) yield [--x, y]; break;\n case \"R\": for (let i = 0; i < length; ++i) yield [++x, y]; break;\n case \"U\": for (let i = 0; i < length; ++i) yield [x, ++y]; break;\n case \"D\": for (let i = 0; i < length; ++i) yield [x, --y]; break;\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":62,"value":"[...parcours(déplacements)]","pinned":true,"hidden":false,"mode":"ojs"},{"id":44,"value":"function mouvementQueue(tx, ty, hx, hy) {\n if (tx < hx - 2 || tx > hx + 2 || ty < hy - 2 || ty > hy + 2) throw new Error(`La tête est trop éloignée !`);\n if (!(hx - 1 <= tx && tx <= hx + 1 && hy - 1 <= ty && ty <= hy + 1)) {\n tx += hx > tx ? 1 : hx < tx ? -1 : 0;\n ty += hy > ty ? 1 : hy < ty ? -1 : 0;\n }\n return [tx, ty];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":41,"value":"function* décritMouvementsDeQueue(déplacements) {\n let tx = 0;\n let ty = 0;\n yield [tx, ty];\n for (const [hx, hy] of parcours(déplacements)) {\n [tx, ty] = mouvementQueue(tx, ty, hx, hy);\n yield [tx, ty];\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":48,"value":"function comptePositions(positions) {\n return d3.union(Array.from(positions, (mouvement) => mouvement.join())).size;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":53,"value":"comptePositions(décritMouvementsDeQueue(déplacements))","pinned":true,"hidden":false,"mode":"ojs"},{"id":68,"value":"function* visualise(déplacements) {\n const positions = Array.from(parcours(déplacements));\n const tailPositions = Array.from(décritMouvementsDeQueue(déplacements));\n for (let i = 0; i < tailPositions.length; ++i) {\n yield Plot.plot({\n grid: true,\n height: 640,\n x: {domain: d3.extent(positions, ([x]) => x)},\n y: {domain: d3.extent(positions, ([, y]) => y)},\n marks: [\n Plot.line(tailPositions.slice(0, i + 1), {}),\n Plot.line([tailPositions[i], positions[i]], {stroke: \"red\"})\n ]\n });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"visualise(déplacements)","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":76,"value":"function* mouvementsCorde(d) {\n const RX = new Float64Array(10);\n const RY = new Float64Array(10);\n yield Array.from({length: 10}, (_, i) => [RX[i], RY[i]]);\n for ([RX[0], RY[0]] of parcours(d)) {\n for (let i = 1; i < 10; ++i) {\n [RX[i], RY[i]] = mouvementQueue(RX[i], RY[i], RX[i - 1], RY[i - 1]);\n }\n yield Array.from({length: 10}, (_, i) => [RX[i], RY[i]]);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":80,"value":"{\n const set = new Set();\n for (const cordePosition of mouvementsCorde(déplacements)) {\n set.add(cordePosition[10 - 1].join());\n }\n return set;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":84,"value":"function* visualiseCorde(d) {\n const positions = Array.from(parcours(d));\n const cordePositions = Array.from(mouvementsCorde(d));\n const queuePositions = cordePositions.map((corde) => corde[9]);\n for (let i = 0; i < positions.length; ++i) {\n yield Plot.plot({\n grid: true,\n height: 640,\n x: {domain: d3.extent(positions, ([x]) => x)},\n y: {domain: d3.extent(positions, ([, y]) => y)},\n marks: [\n Plot.line(queuePositions.slice(0, i)),\n Plot.line(cordePositions[i], {stroke: \"red\"})\n ]\n });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":87,"value":"visualiseCorde(déplacements)","pinned":true,"hidden":false,"mode":"ojs"},{"id":91,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":93,"value":"navigation(9)","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":97,"value":"import {navigation} from \"@linard-y/advent-of-code-2022_day0\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}} 2f:"$2e:body"