Public
Edited
Dec 13, 2023
1 fork
Insert cell
Insert cell
maps = input
.split("\n\n")
.map((puzzle) => puzzle.split("\n").map((line) => [...line]))
Insert cell
binary = (puzzle) => ({
cols: puzzle[0].map((_, k) => d3.sum(puzzle, (line, i) => (1 << i) * (line[k] === "#"))),
rows: puzzle.map((line) => d3.sum(line, (d, i) => (1 << i) * (d === "#")))
})
Insert cell
test = (r, skip) => {
const n = r.length;
return d3.range(1, r.length).find((i) => {
if (i === skip) return false;
if (2 * i < n)
return r.slice(0, i).reverse().join(",") === r.slice(i, 2 * i).join(",");
return (
r
.slice(2 * i - n, i)
.reverse()
.join(",") === r.slice(i, n).join(",")
);
});
}
Insert cell
score = (puzzle) => {
const { cols, rows } = binary(puzzle);
return test(cols) ?? 100 * test(rows);
}
Insert cell
answer1 = d3.sum(maps, score)
Insert cell
Insert cell
Insert cell
findSmudge = ({ cols, rows }) => {
const currentScore = test(cols) ?? 10000 * test(rows);

const C = d3.group(
cols.map((c, i) => ({ c, i })),
({ c }) => c
);
const R = d3.group(
rows.map((c, i) => ({ c, i })),
({ c }) => c
);
for (let x = 0; x < cols.length; ++x) {
for (let y = 0; y < rows.length; ++y) {
// flip the bit
cols[x] ^= 1 << y;
rows[y] ^= 1 << x;

// test
let score;
if (C.has(cols[x])) score = test(cols, currentScore);
if (!score && R.has(rows[y]))
score = 100 * test(rows, currentScore / 10000);

// restore
cols[x] ^= 1 << y;
rows[y] ^= 1 << x;

if (score) return { x, y, score };
}
}
}
Insert cell
answer2 = d3.sum(maps, (d) => findSmudge(binary(d)).score)
Insert cell
{
// This runs in about 3ms, but Jo has found an optimization to go < 1ms!
// https://observablehq.com/@jwolondon/advent-of-code-2023-day-13
const t0 = performance.now();
d3.sum(maps, (d) => findSmudge(binary(d)).score);
return performance.now() - t0;
}
Insert cell
Insert cell

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.
Learn more