Public
Edited
Dec 12, 2021
1 star
Insert cell
Insert cell
Insert cell
function parse(input) {
const caves = new Map();
const addEdge = ([c1, c2]) => {
const [adj1, adj2] = [caves.get(c1), caves.get(c2)];
caves.set(c1, adj1 ? adj1.add(c2) : new Set([c2]));
caves.set(c2, adj2 ? adj2.add(c1) : new Set([c1]));
};
input.forEach((edge) => addEdge(edge.split("-")));
return caves;
}
Insert cell
Insert cell
Insert cell
function isSmall(cave) {
return cave === cave.toLowerCase();
}
Insert cell
function findPaths(caves) {
let paths = 0;

const traverse = (cave, visited) => {
if (cave === "end") {
return paths++;
}
visited = isSmall(cave) ? visited.add(cave) : visited;
for (const neighbour of caves.get(cave)) {
if (!visited.has(neighbour)) {
traverse(neighbour, new Set(visited));
}
}
};

traverse("start", new Set());
return paths;
}
Insert cell
function part1(input) {
return findPaths(parse(input));
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function findPaths2(caves) {
let paths = new Set();

const smallCaves = [...caves.keys()].filter(
(c) => isSmall(c) && c !== "start" && c !== "end"
);

const traverse = (cave, visited, path, special) => {
if (isSmall(cave)) {
if (cave !== special) {
visited.add(cave);
} else {
special = null;
}
}
path.push(cave);
if (cave === "end") {
return paths.add(path.join(","));
}
caves.get(cave).forEach((neighbour) => {
if (!visited.has(neighbour)) {
traverse(neighbour, new Set(visited), path.map(AOC.identity), special);
}
});
};

smallCaves.forEach((c) => traverse("start", new Set(), [], c));
return paths.size;
}
Insert cell
function part2(input) {
return findPaths2(parse(input));
}
Insert cell
Insert cell
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