2f:T68a,// add block, let'em fall as far as possible and finally freeze it in cave // (cave captured inside state object) dropBlock = (state, block) => { let idx = state.idx; // index to current jet character let offset = state.offset; // offset of already removed lines of cave array // add new block to cave let newCave = addBlock(state.cave, block); // maintain only the topmost 100 lines of the cave in memory (optimization) if (newCave.length > 100) { offset += newCave.length - 100; // offset contains the number of already removed lines newCave = newCave.slice(-100); } // actual positions let y = newCave.length - block.length; let x = 2; // assumed new positions, might be rejected let newy = y; let newx = x; // 1st check new position directly below while (checkFree(newCave, block, newx, newy)) { // yes, free -> accept new positions (lower y and moved x from previous loop) x = newx; y = newy; // 2nd check new position moved left/right according to stream character newx = x + (jets[idx] == "<" ? -1 : 1); if (!checkFree(newCave, block, newx, newy)) { // no, not free -> reset to previous x position newx = x; } else { // yes, free -> accept new x position x = newx; } // assume next lower y position newy--; // prepare next jet from stream array idx = (idx + 1) % jets.length; } // no more dropping possible -> freeze block at current position freezeBlock(newCave, block, x, y); // return the resulting cave with added, dropped & freeezed block return { idx: idx, cave: newCave, offset: offset }; }30:T445,dropBlocks = function* (caveState, blocks, maxBlocks) { let nextState = caveState; // start with given cave (captured by state object) let b = 0; // start with template block #0 let done = false; // trigger to stop let keys = []; // take care of all keys to recognize cycles let key; let idx; // loop as long as ... while (!done && (b < maxBlocks || maxBlocks == 0)) { // drop next block (iterating through template blocks) nextState = dropBlock(nextState, blocks[b++ % blocks.length]); // build key from block index and stream index to recognize cycles key = (b % blocks.length) + "-" + nextState.idx; idx = keys.indexOf(key); if (maxBlocks == 0 && b % blocks.length == 0 && idx >= 0) { // cycle found -> we can stop here done = true; } keys.push(key); // show progress yield { blocks: b - 1, key: key, cycle: idx, keys: keys, nextState: nextState }; } // return final result yield { blocks: b - 1, key: key, cycle: idx, keys: keys, nextState: nextState }; }31:[{"id":"8552661774250079d782b6444ffa6671213d2e9d85117daa8817585d76914bd1ce03027ea58ba49d1b5b91906b9c94492ce4faf81c1fcddb99f385037b23a8f8","href":"https://static.observableusercontent.com/files/8552661774250079d782b6444ffa6671213d2e9d85117daa8817585d76914bd1ce03027ea58ba49d1b5b91906b9c94492ce4faf81c1fcddb99f385037b23a8f8","name":"input.txt","type":"text/plain","lastModified":1672357421322.641,"size":10092}] 2d:{"title":"Day 17 - Pyroclastic Flow","cells":[{"id":0,"value":"# Day 17 - [Pyroclastic Flow](https://adventofcode.com/2022/day/17)","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"block = `####\n\n.#.\n###\n.#.\n\n..#\n..#\n###\n\n#\n#\n#\n#\n\n##\n##\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":140,"value":"// split by empty line into blocks and map each block as an 2d array\nblocks = block.split(\"\\n\\n\").map((b) =>\n b\n .split(\"\\n\")\n .filter((line) => line.length > 0)\n .map((line) => line.split(\"\"))\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"inputs0 = `>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>`","pinned":true,"hidden":false,"mode":"ojs"},{"id":173,"value":"inputs = FileAttachment(\"input.txt\").text()","pinned":true,"hidden":false,"mode":"ojs"},{"id":9,"value":"// split jet streams as array of chars (< or >)\njets = inputs.split(\"\\n\")[0].split(\"\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":15,"value":"// start with an empty cave, just the baseline\ncave = [\"-------\".split(\"\")]","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"// add a new block at topmost position\naddBlock = (cave, block) => {\n // create a copy of the cave first to alter it\n let newCave = cave.map((line) => line.map((el) => el));\n\n // remove all empty lines at the top (top position is at end of array!)\n let y = newCave.length - 1;\n let empty = newCave[y].filter((el) => el == \".\").length == newCave[y].length;\n while (y >= 0 && empty) {\n y--;\n empty = newCave[y].filter((el) => el == \".\").length == newCave[y].length;\n }\n\n // add suitable number of empty line to contain the new block (depends on it's size of course)\n for (let n = 1; n <= 3 + block.length; n++) {\n newCave[y + n] = new Array(7).fill(\".\");\n }\n\n // take care of not expanding too much ... still needed (???)\n if (newCave.length > y + block.length + 4) {\n newCave = newCave.slice(0, y + block.length + 4);\n }\n\n // return cave with new block added\n return newCave;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"// freeze block at position x/y\nfunction freezeBlock(cave, block, x, y) {\n block\n .map((b) => b) // copy first, to allow reserving without side effects\n .reverse() // reverse block (top-down flip), according to placement in cave\n .forEach((line, by) =>\n line.forEach(\n (el, bx) =>\n // update cave with block, where block is defined (\"#\")\n (cave[y + by][x + bx] = el == \"#\" ? el : cave[y + by][x + bx])\n )\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":36,"value":"// check if at position x/y is enough free space to contain the block\ncheckFree = (cave, block, x, y) => {\n return (\n // check for valid coordinates first (i.e. left<0 or right>cave, top<0 or bottom>ground)\n x >= 0 &&\n x + block[0].length - 1 < cave[0].length &&\n y > 0 &&\n y + block.length - 1 < cave.length &&\n block\n .map((b) => b) // copy first, to allow reserving without side effects\n .reverse() // reverse block (top-down flip), according to placement in cave\n // all non-empty block cells (\"#\") only allowed on empty cave cells (\".\") -> no mismatch found\n .filter(\n (line, by) =>\n line.filter((el, bx) => el != \".\" && cave[y + by][x + bx] != \".\")\n .length > 0\n ).length == 0\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":25,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs"},{"id":127,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":166,"value":"// evaluate height of all blocks from bottom to topmost one\nblockHeight = function (caveState) {\n return (\n caveState.nextState.cave.filter(\n // line in cave must contain at least one non-empty cell (i.e. !=\".\")\n (line) => line.filter((el) => el == \".\").length != line.length\n ).length -\n 1 +\n // keep track of already removed lines of cave due to memory optimization\n caveState.nextState.offset\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":689,"value":"// show (intermediate) result of cave (clipped to 100 topmost lines)\nprintCave = (caveSate) => {\n return html`

height: ${result1}

${caveSate.nextState.cave\n    .map((c) => c) // copy first to allow reserving without side-effects\n    .reverse() // reverse array (topmost is at end of array)\n    .map(\n      // output with line number and cave walls around\n      (line, y) =>\n        caveSate.nextState.offset -\n        y +\n        caveSate.nextState.cave.length -\n        1 +\n        \" |\" +\n        line.join(\"\") +\n        \"|\"\n    )\n    .join(\"\\n\")}`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":598,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":182,"value":"// create initial cave state\ncaveState = {\n  return {\n    idx: 0,\n    offset: 0,\n    cave: cave\n  };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":511,"value":"// drop exactly 2022 blocks ...\nresultState1 = dropBlocks(caveState, blocks, 2022)","pinned":true,"hidden":false,"mode":"ojs"},{"id":534,"value":"// ... and evaluate their height\nresult1 = blockHeight(resultState1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":188,"value":"printCave(resultState1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":591,"value":"## Part 2","pinned":true,"hidden":false,"mode":"md"},{"id":245,"value":"// maximum number of drops to drop\nmaxBlocks = 1000000000000","pinned":true,"hidden":false,"mode":"ojs"},{"id":516,"value":"// drop until a cycle is detected\ndetectCycle = dropBlocks(caveState, blocks, 0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":611,"value":"// start of cycle at position inside keys array, where current key was located\ncycleStart = detectCycle.cycle","pinned":true,"hidden":false,"mode":"ojs"},{"id":613,"value":"// end of cycle at current block\ncycleEnd = detectCycle.blocks","pinned":true,"hidden":false,"mode":"ojs"},{"id":607,"value":"// difference is the cycle size\ncycleSize = cycleEnd - cycleStart","pinned":true,"hidden":false,"mode":"ojs"},{"id":539,"value":"// height of all blocks (up to end of cycle)\ncycleHeight = blockHeight(detectCycle)","pinned":true,"hidden":false,"mode":"ojs"},{"id":529,"value":"// simalute once again the height until start of cycle\nbeforeCycle = dropBlocks(caveState, blocks, cycleStart + 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":536,"value":"// initial height is height until start of cycle\ninitialHeight = blockHeight(beforeCycle)","pinned":true,"hidden":false,"mode":"ojs"},{"id":548,"value":"// simulate last incomplete cycle\nincompleteCycle = dropBlocks(caveState, blocks, maxBlocks % cycleSize)","pinned":true,"hidden":false,"mode":"ojs"},{"id":550,"value":"// height of last incomplete cycle\nlastHeight = blockHeight(incompleteCycle)","pinned":true,"hidden":false,"mode":"ojs"},{"id":525,"value":"// total height is sum of initialHeight + cycles*cycleHeight + lastHeight\nresult2 = Math.floor(maxBlocks / cycleSize) * (cycleHeight - initialHeight) +\n  lastHeight","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}