Public
Edited
Dec 2
Paused
1 fork
2 stars
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function parse(input) {
const records = [];
for (const line of input.split("\n")) {
const [springs, grps] = line.split(/\s+/);
records.push({ springs: springs, lengths: grps.split(",").map(Number) });
}
return records;
}
Insert cell
Insert cell
function arrangements(r, state, memo = {}) {
const hash = `${state.pos},${state.grp},${state.len}`; // Hash the current state for memoization

// Have we seen this state before?
if (memo[hash] !== undefined) {
return memo[hash];
}

// Base case: We have reached the end of the string
if (state.pos === r.springs.length) {
if (state.len !== 0 && state.len !== r.lengths[state.grp]) {
return 0; // Invalid arrangement
}
return state.grp + (state.len === r.lengths[state.grp] ? 1 : 0) ===
r.lengths.length
? 1
: 0;
}

let n = 0; // Keep track of number of valid configurations
const { springs, lengths } = r;
const chr = springs[state.pos];

// Damaged spring
if (
chr !== "." &&
state.grp < lengths.length &&
state.len < lengths[state.grp]
) {
n += arrangements(
r,
{ pos: state.pos + 1, grp: state.grp, len: state.len + 1 },
memo
);
}

// Operational spring
if (chr !== "#" && (state.len === lengths[state.grp] || state.len === 0)) {
n += arrangements(
r,
{
pos: state.pos + 1,
grp: state.grp + (state.len === lengths[state.grp] ? 1 : 0),
len: 0
},
memo
);
}

memo[hash] = n; // Log this state in case we visit it again.
return n;
}
Insert cell
function part1(input) {
return parse(input).reduce(
(sum, record) => sum + arrangements(record, { pos: 0, grp: 0, len: 0 }),
0
);
}
Insert cell
Insert cell
Insert cell
Insert cell
function unfold(records) {
const repeat = (arr, n) => Array(n).fill(arr).flat();

return records.map(({ springs, lengths }) => ({
springs: repeat([springs, "?"], 5).join("").slice(0, -1), // remove the last '?'
lengths: repeat(lengths, 5)
}));
}
Insert cell
Insert cell
function part2(input) {
return unfold(parse(input)).reduce(
(sum, record) => sum + arrangements(record, { pos: 0, grp: 0, len: 0 }),
0
);
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
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