17.md

Day 17

Part 1

Simulate a full six-cycle boot process. How many cubes are left in the active state after the sixth cycle?

const input = `
.#.
..#
###
`.trim()

const initialState = input.split('\n').reduce(
  (state, line, y) => {
    line.split('').forEach((cube, x) => {
      state.cubes.push({ active: cube === '#', x, y, z: 0 })
      state.x = {
        min: Math.min(state.x.min, x),
        max: Math.max(state.x.max, x),
      }
    })
    state.y = {
      min: Math.min(state.y.min, y),
      max: Math.max(state.y.max, y),
    }
    return state
  },
  {
    cubes: [],
    x: { min: 0, max: 0 },
    y: { min: 0, max: 0 },
    z: { min: 0, max: 0 },
  }
)

const range = (from, to) =>
  Array.from({ length: to - from + 1 }, (_, i) => i + from)

console.time()

const finalState = range(1, 6).reduce(
  (state) => simulateCycle(state),
  initialState
)
const result = finalState.cubes.filter((cube) => cube.active).length

console.log('Result:', result)
console.timeEnd()

function simulateCycle(state) {
  const newState = {
    cubes: [],
    x: { min: state.x.min - 1, max: state.x.max + 1 },
    y: { min: state.y.min - 1, max: state.y.max + 1 },
    z: { min: state.z.min - 1, max: state.z.max + 1 },
  }

  const xs = range(newState.x.min, newState.x.max)
  const ys = range(newState.y.min, newState.y.max)
  const zs = range(newState.z.min, newState.z.max)

  xs.forEach((x) => {
    ys.forEach((y) => {
      zs.forEach((z) => {
        const prev = state.cubes.find(
          (cube) => cube.x === x && cube.y === y && cube.z === z
        )
        const activeNeighbors = state.cubes.filter(
          (cube) =>
            cube !== prev &&
            [x - 1, x, x + 1].includes(cube.x) &&
            [y - 1, y, y + 1].includes(cube.y) &&
            [z - 1, z, z + 1].includes(cube.z) &&
            cube.active
        ).length
        const active = prev?.active
          ? [2, 3].includes(activeNeighbors)
          : activeNeighbors === 3

        newState.cubes.push({ active, x, y, z })
      })
    })
  })

  return newState
}

Try it out on flems.io

Running the code against the real puzzle input takes about half a second on my machine. Not great, but good enough.

Part 2

Same as Part 1, but with one more spatial dimension (w).

We need to just™ add the fourth dimension to initialState and simulateCycle():

 const initialState = input.split('\n').reduce(
   (state, line, y) => {
     line.split('').forEach((cube, x) => {
-      state.cubes.push({ active: cube === '#', x, y, z: 0 })
+      state.cubes.push({ active: cube === '#', x, y, z: 0, w: 0 })
       state.x = {
         min: Math.min(state.x.min, x),
         max: Math.max(state.x.max, x),
       }
     })
     state.y = {
       min: Math.min(state.y.min, y),
       max: Math.max(state.y.max, y),
     }
     return state
   },
   {
     cubes: [],
     x: { min: 0, max: 0 },
     y: { min: 0, max: 0 },
     z: { min: 0, max: 0 },
+    w: { min: 0, max: 0 },
   }
 )

 function simulateCycle(state) {
   const newState = {
     cubes: [],
     x: { min: state.x.min - 1, max: state.x.max + 1 },
     y: { min: state.y.min - 1, max: state.y.max + 1 },
     z: { min: state.z.min - 1, max: state.z.max + 1 },
+    w: { min: state.w.min - 1, max: state.w.max + 1 },
   }

   const xs = range(newState.x.min, newState.x.max)
   const ys = range(newState.y.min, newState.y.max)
   const zs = range(newState.z.min, newState.z.max)
+  const ws = range(newState.w.min, newState.w.max)

   xs.forEach((x) => {
     ys.forEach((y) => {
       zs.forEach((z) => {
+        ws.forEach((w) => {
           const prev = state.cubes.find(
-            (cube) => cube.x === x && cube.y === y && cube.z === z
+            (cube) =>
+              cube.x === x && cube.y === y && cube.z === z && cube.w === w
           )
           const activeNeighbors = state.cubes.filter(
             (cube) =>
               cube !== prev &&
               [x - 1, x, x + 1].includes(cube.x) &&
               [y - 1, y, y + 1].includes(cube.y) &&
               [z - 1, z, z + 1].includes(cube.z) &&
+              [w - 1, w, w + 1].includes(cube.w) &&
               cube.active
           ).length
           const active = prev?.active
             ? [2, 3].includes(activeNeighbors)
             : activeNeighbors === 3

-          newState.cubes.push({ active, x, y, z })
+          newState.cubes.push({ active, x, y, z, w })
+        })
       })
     })
   })

   return newState
 }

There's one problem though: on my machine, it takes about 18 seconds to run the code against the sample input, and about 60 seconds to run it against the real puzzle input. During this time, the page is unresponsive.

Let's implement a quick and dirty Web Worker solution like in the 2015/04 puzzle:

const initialState = input.split('\n').reduce(/* Same as before */)

const worker = (() => {
  const code = `(${workerFn.toString()})()`
  const blob = new Blob([code], { type: 'application/javascript' })
  const url = URL.createObjectURL(blob)

  return new Worker(url)
})()

worker.onmessage = ({ data: result }) => console.log('Result:', result)
worker.postMessage(initialState)

function workerFn() {
  const range = (from, to) =>
    Array.from({ length: to - from + 1 }, (_, i) => i + from)

  onmessage = ({ data: initialState }) => {
    console.time()

    const finalState = range(1, 6).reduce((state, n) => {
      console.log('Simulating cycle', n)
      return simulateCycle(state)
    }, initialState)
    const result = finalState.cubes.filter((cube) => cube.active).length

    postMessage(result)
    console.timeEnd()
  }

  function simulateCycle(state) {
    // Same as before
  }
}

flems

This is as slow as without using a Web Worker, but now the page doesn't freeze for a minute.

What did I learn?

Nothing, but this was a fun puzzle. 😋