31:T5be,## Reflection This was a satisfying puzzle to complete as at first read it looked complex, but ultimately yields to a relatively simple solution solved in under a millisecond for both parts. Initially it took me quite a while simply to make sense of the question (I think I have problems keeping track of which paragraph in text I am reading, so the similarity between them threw me). For a while I thought there were only two robots. Like, I suspect most people, my first solution to part 1 calculated the actual key-press sequences of the third robot, from which the complexity score was calculated. I've left that code here for part 1 as it more clearly illustrates the process of generating nested sequences. But, like, I suspect for most people, this was infeasible for part 2. When I first tried to model the problem I mistakenly assumed that every robot action always started and ended in position `A` and so the sequence for each code was a simple recursive application of a small set of costs. This was clearly not true (e.g. a robot might go down and then left in order to reach the `v` key without an intermediate `A`). However this did lead to me noting that every _instruction sequence_ will always start and end from `A`. This means the cost of such a sequence is independent of what comes before or after. The key insight here is that therefore we don't need to keep track of the individual sequences, but instead simply a count of the number them.32:[{"id":"1b9f36a9538c90c70457bdc1c8dc42edadd144c2b2f3a9aaf8e34cf48d37dc28166d8a4faedfd0462eab85284c1a2b0f837510228e1f4e0f126a94b7497dbbd7","href":"https://static.observableusercontent.com/files/1b9f36a9538c90c70457bdc1c8dc42edadd144c2b2f3a9aaf8e34cf48d37dc28166d8a4faedfd0462eab85284c1a2b0f837510228e1f4e0f126a94b7497dbbd7","name":"only12.png","type":"image/png","lastModified":1734814837365.18,"size":99693}] 2f:{"title":"Advent of Code: 2024 Day 21","cells":[{"id":0,"value":"# Advent of Code: 2024 Day 21\n\nSee [Keypad Conundrum](https://adventofcode.com/2024/day/21).","pinned":false,"hidden":false,"mode":"md"},{"id":75,"value":"viewof inputChooser = Inputs.file({\n label: \"Puzzle input: \",\n accept: \".txt\",\n required: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"## Part 1\n**What is the sum of the complexities of the five codes on your list?**","pinned":false,"hidden":false,"mode":"md"},{"id":57,"value":"Firstly, we need to encode the spatial relationships between the keys in each type of keypad (e.g. that a `9` is above a `6` and a `6` is to the right of a `5` etc.). We will need to know for a given key (e.g. '`6`' or '`<`'), what is its position in the keypad (e.g. `[1,2]` or `[1,0]`). And because we cannot move a robot over a gap we record the gap position.","pinned":false,"hidden":false,"mode":"md"},{"id":373,"value":"

","pinned":false,"hidden":false,"mode":"html"},{"id":317,"value":"numericPad = padLookup([\"789\", \"456\", \"123\", \" 0A\"])","pinned":true,"hidden":false,"mode":"ojs"},{"id":370,"value":"

⌃

⌄

","pinned":false,"hidden":false,"mode":"html"},{"id":322,"value":"dirPad = padLookup([\" ^A\", \"\"])","pinned":true,"hidden":false,"mode":"ojs"},{"id":194,"value":"function padLookup(padRows) {\n const coords = {};\n const gap = padRows.length === 2 ? `0,0` : `3,0`;\n padRows.forEach((keys, row) => {\n [...keys].forEach((key, col) => {\n if (key !== \" \") {\n coords[key] = [row, col];\n }\n });\n });\n return { coords, gap };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":349,"value":"When transitioning from one key location to another, we need to find the optimal path that minimises the number of instructions issued by the 'parent' robot. Such optimal instructions have several characteristics:\n\n1. The instruction sequence must terminate with an '`A`' (to get the next robot to actually do the thing we want it to)\n\n2. Any given instruction sequence that transitions from one key to another may contain '`<`' or '`>`' instructions but never both (that would be inefficient). And similarly, vertical movement may contain '`v`' or '`^`' instructions, but never both.\n\n3. Since the cheapest transition is one that stays in the same location, the optimal path will be the one that groups repeated direction instructions. For example from '`A`' to '`<`' it is cheaper to be instructed to go '`v<<`' than it is to go '` r1 ? \"v\".repeat(r2 - r1) : \"^\".repeat(r1 - r2);\n const lr = c2 > c1 ? \">\".repeat(c2 - c1) : \"<\".repeat(c1 - c2);\n\n if (c2 > c1 && `${r2},${c1}` !== pad.gap) {\n // Safe to move vertically first if heading right and corner point isn't the gap\n return `${ud}${lr}A`;\n }\n if (`${r1},${c2}` !== pad.gap) {\n // Safe to move horizontally first if corner point isn't the gap\n return `${lr}${ud}A`;\n }\n // Must be safe to move vertically first because we can't be in same column as gap.\n return `${ud}${lr}A`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":671,"value":"To generate the instructions for any given sequence we just iterate over the keys in the sequence finding the shortest path from the previous position to the current one in the sequence.","pinned":false,"hidden":false,"mode":"md"},{"id":601,"value":"function sequences(seq, pad) {\n const keys = [];\n let prevKey = \"A\";\n for (let key of seq) {\n keys.push(shortestPath(prevKey, key, pad));\n prevKey = key;\n }\n return keys;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":154,"value":"We can pass the sequence instructions from one robot to the next, noting we start with the numeric key pad but the subsequent two robots use the direction pad.\n\nOnce we have the full sequence we calculate its complexity score.\n\n(Part 2 provides a modified way of calculating this score, but I've left this approach here as the code is a little simpler.)","pinned":false,"hidden":false,"mode":"md"},{"id":9,"value":"function part1(input) {\n const codes = input.split(\"\\n\");\n const r1Seqs = codes.map((code) => sequences(code, numericPad).join(\"\"));\n const r2Seqs = r1Seqs.map((d) => sequences(d, dirPad).join(\"\"));\n const r3Seqs = r2Seqs.map((d) => sequences(d, dirPad).join(\"\"));\n\n return d3.sum(r3Seqs, (d, i) => d.length * Number(codes[i].slice(0, -1)));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":52,"value":"**${AOC.timer(part1,puzzleInput,100)}**","pinned":false,"hidden":false,"mode":"md"},{"id":16,"value":"## Part 2\n**What is the sum of the complexities of the five codes on your list?**","pinned":false,"hidden":false,"mode":"md"},{"id":59,"value":"While in theory we could apply the part 1 solution to this variation, supplying the sequences from each robot to the next, the sequence length expands exponentially so isn't practical beyond a small number of robots.\n\nInstead we can recognise two further characteristics of the process:\n\n- There is a relatively small set of possible optimal sequences for any instruction issued to a robot. For the direction pad robots, **there are only 12**. With 5 possible states, there are 25 theoretical transitions, but 8 of them result in the same sequence as other transitions (grey in the figure below); 4 of them would be pointless reverse transitions (left followed by a right etc.) and one (`^<`) is can only be made when in the bottom-right position, where it has the equivalent cost of `<^`","pinned":false,"hidden":false,"mode":"md"},{"id":876,"value":"only12 = FileAttachment(\"only12.png\").image({ width: 500 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":882,"value":"- Any given instruction sequence starts and ends in position '`A`'. This means that the content of the instruction sequences are **independent of where they are applied**.\n\nTogether this means we don't need to store the full sequence of sequence of sequences... Instead, we can just keep a running total of how many sequences we have of each type (a dictionary with at most 12 entries for the direction keypad robots). Each time we transfer sequences to the next robot, we just scale the frequencies of each sequence type by the number of subsequences associated with that sequence.\n\nWith only 12 possible types and 25 levels of direction robots, this can be computed rapidly.","pinned":false,"hidden":false,"mode":"md"},{"id":452,"value":"function complexity(codes, numDirRobots = 25) {\n // Frequency table of sub-sequences\n const seqCounts = (seq) =>\n sequences(seq, dirPad).reduce(\n (fTable, s) => AOC.addToFreqTable(fTable, s),\n new Map()\n );\n\n // Start with the numeric keypad sequences\n let fTables = codes.map(\n (code) => new Map([[sequences(code, numericPad).join(\"\"), 1]])\n );\n\n // Expand sequences for each robot\n for (let i = 0; i < numDirRobots; i++) {\n fTables = fTables.map((fTable) => {\n const subFTable = new Map();\n fTable.forEach((freq, seq) =>\n seqCounts(seq).forEach((subFreq, subSeq) =>\n subFTable.set(subSeq, (subFTable.get(subSeq) || 0) + subFreq * freq)\n )\n );\n return subFTable;\n });\n }\n\n // Calculate the final complexity from each code's sequence frequencies\n const cmplx = (seq) =>\n d3.sum([...seq.entries()], ([key, freq]) => key.length * freq);\n\n return d3.sum(\n fTables,\n (seq, i) => cmplx(seq) * Number(codes[i].slice(0, -1))\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"function part2(input) {\n return complexity(input.split(\"\\n\"));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":34,"value":"**${AOC.timer(part2,puzzleInput,100)}**","pinned":false,"hidden":false,"mode":"md"},{"id":61,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":20,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":22,"value":"import { AOC } from \"@jwolondon/aoc-utilities\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"## Data","pinned":false,"hidden":false,"mode":"md"},{"id":29,"value":"testData = `029A\n980A\n179A\n456A\n379A`","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"puzzleInput = inputChooser.text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":368,"value":"_For keypad display:_","pinned":false,"hidden":false,"mode":"md"},{"id":364,"value":"","pinned":false,"hidden":false,"mode":"html"}],"files":"$W32","stdlib":"1","titling":"auto"}