Tinkering with code and algorithms for fun
function parseInput(input) {
return input
.split('\n')
.map(line => line.split('').map(char => (char === "#" ? 1 : 0)));
}
input = parseInput(input_text)
testInput = parseInput(testInput_text)
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(<not present>) => 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 };
}
test1 = q1(testInput, 6)
answer1 = q1(input, 6)
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(<not present>) => 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 };
}
q2(testInput, 6)
q2(input, 6)
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.