Tinkering with code and algorithms for fun
Day 1 - Report RepairDay 2 - Password PhilosophyDay 3 - Toboggan TrajectoryDay 4 - Passport ProcessingDay 5 - Binary BoardingDay 6 - Custom CustomsDay 7: Handy HaversacksDay 8 - Handheld HaltingDay 9 - Encoding ErrorDay 10 - Adapter ArrayDay 11 - Seating SystemDay 12 - Rain RiskDay 13 - Shuttle SearchDay 14 - Docking DataDay 15 - Rambunctious RecitationDay 16 - Ticket TranslationDay 18 - Operation OrderDay 19 - Monster Messages (part one)
Day 17 - Conway Cubes
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)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
