31:Tca8,md`# Day 17 - Conway Cubes As your flight slowly drifts through the sky, the Elves at the Mythical Information Bureau at the North Pole contact you. They'd like some help debugging a malfunctioning experimental energy source aboard one of their super-secret imaging satellites. The experimental energy source is based on cutting-edge technology: a set of Conway Cubes contained in a pocket dimension! When you hear it's having problems, you can't help but agree to take a look. The pocket dimension contains an infinite 3-dimensional grid. At every integer 3-dimensional coordinate (x,y,z), there exists a single cube which is either active or inactive. In the initial state of the pocket dimension, almost all cubes start inactive. The only exception to this is a small flat region of cubes (your puzzle input); the cubes in this region start in the specified active (#) or inactive (.) state. The energy source then proceeds to boot up by executing six cycles. Each cube only ever considers its neighbors: any of the 26 other cubes where any of their coordinates differ by at most 1. For example, given the cube at x=1,y=2,z=3, its neighbors include the cube at x=2,y=2,z=2, the cube at x=0,y=2,z=3, and so on. During a cycle, all cubes simultaneously change their state according to the following rules: If a cube is active and exactly 2 or 3 of its neighbors are also active, the cube remains active. Otherwise, the cube becomes inactive. If a cube is inactive but exactly 3 of its neighbors are active, the cube becomes active. Otherwise, the cube remains inactive. The engineers responsible for this experimental energy source would like you to simulate the pocket dimension and determine what the configuration of cubes should be at the end of the six-cycle boot process. For example, consider the following initial state: \`\`\`text .#. ..# ### \`\`\` Even though the pocket dimension is 3-dimensional, this initial state represents a small 2-dimensional slice of it. (In particular, this initial state defines a 3x3x1 region of the 3-dimensional space.) Simulating a few cycles from this initial state produces the following configurations, where the result of each cycle is shown layer-by-layer at each given z coordinate (and the frame of view follows the active cells in each cycle): Before any cycles: \`\`\`text z=0 .#. ..# ### \`\`\` After 1 cycle: \`\`\`text z=-1 #.. ..# .#. z=0 #.# .## .#. z=1 #.. ..# .#. \`\`\` After 2 cycles: \`\`\`text z=-2 ..... ..... ..#.. ..... ..... z=-1 ..#.. .#..# ....# .#... ..... z=0 ##... ##... #.... ....# .###. z=1 ..#.. .#..# ....# .#... ..... z=2 ..... ..... ..#.. ..... ..... \`\`\` After 3 cycles: \`\`\`text z=-2 ....... ....... ..##... ..###.. ....... ....... ....... z=-1 ..#.... ...#... #...... .....## .#...#. ..#.#.. ...#... z=0 ...#... ....... #...... ....... .....## .##.#.. ...#... z=1 ..#.... ...#... #...... .....## .#...#. ..#.#.. ...#... z=2 ....... ....... ..##... ..###.. ....... ....... ....... \`\`\` After the full six-cycle boot process completes, 112 cubes are left in the active state. Starting with your given initial configuration, simulate six cycles. How many cubes are left in the active state after the sixth cycle?`32:Tb88,function q1(input, cycles) { const t0 = performance.now(); // since we can only advance one neighbor per cycle, // our "stride" is equal to the nr of cycles plus // the longest dimension of our input // NOTE TO SELF: if we need a lot of cycles we might // have to switch to big integers const stride = cycles + Math.max(input.length, input[0].length); // convenience functions to convert [x,y,z] coordinate to a // single unique nr const X = stride * stride * 4; const Y = stride * 2; // + stride so that we can start at x = y = z = 0, // and don't have to worry about z = -1 and stuff like that // again making use of the fact that we can advance at most // one cube per cycle const XYZ = (x, y, z) => (x + stride) * X + (y + stride) * Y + (z + stride); const getXYZ = xyz => { // const x = ((xyz / X) | 0) - stride; // const y = (((xyz - (x + stride) * X) / Y) | 0) - stride; // const z = xyz - (x + stride) * X - (y + stride) * Y - stride; // return [x, y, z]; const x = (xyz / X) | 0; xyz -= x * X; const y = (xyz / Y) | 0; xyz -= y * Y; const z = xyz - stride; return [x - stride, y - stride, z]; }; let activeCubes = new Set(); for (let y = 0; y < input.length; y++) { const row = input[y]; for (let x = 0; x < row.length; x++) { if (row[x]) activeCubes.add(XYZ(x, y, 0)); } } let nextCubes = new Set(); const countNeighbors = new Map(); for (let n = 0; n < cycles; n++) { // Count neighbors for all cubes adjacent to active cubes countNeighbors.clear(); for (const xyz of activeCubes.values()) { const [x, y, z] = getXYZ(xyz); for (let i = -1; i <= 1; i++) { for (let j = -1; j <= 1; j++) { for (let k = -1; k <= 1; k++) { // note that active cubes count themselves as // neighbors (i = j = k = 0) so we have to // adjust for that later const xyzN = XYZ(x + i, y + j, z + k); // abuse Map.get() => undefined, // and undefined | 0 being converted to 0 countNeighbors.set(xyzN, (countNeighbors.get(xyzN) | 0) + 1); } } } } // for all cubes with active neighbors, determine which // remain active or are activated nextCubes.clear(); for (const [xyz, totalNeighbors] of countNeighbors) { // if active and 2 or 3 neighbors (so totalNeighbors 3 or 4, // because the count includes the current active cube), // active cube remains active if (activeCubes.has(xyz)) { if (totalNeighbors === 3 || totalNeighbors === 4) { nextCubes.add(xyz); } } else if (totalNeighbors === 3) { // else if exactly 3 neighbors, incactive becomes active nextCubes.add(xyz); } } [activeCubes, nextCubes] = [nextCubes, activeCubes]; } return { activeCubes, time: performance.now() - t0 }; }33:T1137,function* q2(input, cycles) { const t0 = performance.now(); const timing = []; // since we can only advance one neighbor per cycle, // our "stride" is equal to the nr of cycles plus // the longest dimension of our input const stride = cycles + Math.max(input.length, input[0].length); // convenience functions to convert [w,x,y,z] coordinate to a // single unique nr const W = stride * stride * stride * 8; const X = stride * stride * 4; const Y = stride * 2; // + stride so that we can start at w = x = y = z = 0, // and don't have to worry about z = -1 and stuff like that // again making use of the fact that we can advance at most // one cube per cycle const WXYZ = (w, x, y, z) => (w + stride) * W + (x + stride) * X + (y + stride) * Y + (z + stride); const getWXYZ = wxyz => { const w = (wxyz / W) | 0; wxyz -= w * W; const x = (wxyz / X) | 0; wxyz -= x * X; const y = (wxyz / Y) | 0; wxyz -= y * Y; const z = wxyz - stride; return [w - stride, x - stride, y - stride, z]; }; let activeCubes = new Set(); for (let y = 0; y < input.length; y++) { const row = input[y]; for (let x = 0; x < row.length; x++) { if (row[x]) activeCubes.add(WXYZ(0, x, y, 0)); } } let nextCubes = new Set(), maybeNextCubes = new Set(); const countNeighbors = new Map(); for (let n = 0; n < cycles; n++) { // Count neighbors for all cubes adjacent to active cubes countNeighbors.clear(); maybeNextCubes.clear(); let t1 = performance.now(); for (const wxyz of activeCubes.values()) { // note that active cubes count themselves as // neighbors (h = i = j = k = 0) so we have to // adjust for that later // const [w, x, y, z] = getWXYZ(wxyz); // for (let h = -1; h <= 1; h++) { // for (let i = -1; i <= 1; i++) { // for (let j = -1; j <= 1; j++) { // for (let k = -1; k <= 1; k++) { // const wxyzN = WXYZ(w + h, x + i, y + j, z + k); // Optimization: we can easily compute wxyzN directly, // saving a tiny bit of call overhead on getWXYZ and WXYZ for (let w = -W; w <= W; w += W) { for (let x = -X; x <= X; x += X) { for (let y = -Y; y <= Y; y += Y) { for (let z = -1; z <= 1; z++) { const wxyzN = wxyz + w + x + y + z; // abuse Map.get() => undefined, // and undefined | 0 being converted to 0 const neighbors = (countNeighbors.get(wxyzN) | 0) + 1; // Optimization: // If active and 2 or 3 neighbors (so totalNeighbors 3 or 4, // because the count includes the current active cube), // active cube remains active. // If inactive and exactly 3 neighbors, become active. // Therefore we can pre-filter: only add cubes with // three neighbors to nextCubes, remove cubes // with five neighbors, and skip // No need to update if more than five neighbors, since // the cube will always end up inactive with five or more // neighbors, and we already mark that when we reach // five neighbors if (neighbors > 5) continue; else if (neighbors === 3) maybeNextCubes.add(wxyzN); else if (neighbors === 5) maybeNextCubes.delete(wxyzN); countNeighbors.set(wxyzN, neighbors); } } } } let t2 = performance.now(); if (t2 - t1 > 200) { t1 = t2; yield { n, timing, activeCubes, time: t2 - t0 }; } } // for all cubes in nextCubes, determine if // 3 + inactive, or (3|4) + active. If so // they will be active the next round nextCubes.clear(); for (const wxyz of maybeNextCubes.values()) { if (countNeighbors.get(wxyz) === 3 || activeCubes.has(wxyz)) nextCubes.add(wxyz); let t2 = performance.now(); if (t2 - t1 > 200) { t1 = t2; yield { n, timing, activeCubes, time: t2 - t0 }; } } activeCubes.clear(); [activeCubes, nextCubes] = [nextCubes, activeCubes]; let t2 = performance.now(); timing.push(t2 - t0); yield { n, timing, activeCubes, time: t2 - t0 }; } yield { cycles, timing, activeCubes, time: performance.now() - t0 }; }34:[] 2f:{"title":"Day 17 - Conway Cubes","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"input_text = `#.#..###\n.#....##\n.###...#\n..####..\n....###.\n##.#.#.#\n..#..##.\n#.....##`","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"testInput_text = `.#.\n..#\n###`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"function parseInput(input) {\n return input\n .split('\\n')\n .map(line => line.split('').map(char => (char === \"#\" ? 1 : 0)));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":21,"value":"input = parseInput(input_text)","pinned":true,"hidden":false,"mode":"ojs"},{"id":25,"value":"testInput = parseInput(testInput_text)","pinned":true,"hidden":false,"mode":"ojs"},{"id":28,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":48,"value":"test1 = q1(testInput, 6)","pinned":true,"hidden":false,"mode":"ojs"},{"id":95,"value":"answer1 = q1(input, 6)","pinned":true,"hidden":false,"mode":"ojs"},{"id":97,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":111,"value":"q2(testInput, 6)","pinned":true,"hidden":false,"mode":"ojs"},{"id":117,"value":"q2(input, 6)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}