Advent of Code: 2016 Day 1Advent of Code: 2016 Day 2Advent of Code: 2016 Day 3Advent of Code: 2016 Day 4Advent of Code: 2016 Day 5Advent of Code: 2016 Day 6Advent of Code: 2016 Day 7Advent of Code: 2016 Day 8Advent of Code: 2016 Day 9Advent of Code: 2016 Day 10Advent of Code: 2016 Day 12Advent of Code: 2016 Day 13Advent of Code: 2016 Day 14Advent of Code: 2016 Day 15Advent of Code: 2016 Day 16Advent of Code: 2016 Day 17Advent of Code: 2016 Day 18Advent of Code: 2016 Day 19Advent of Code: 2016 Day 20Advent of Code: 2016 Day 21Advent of Code: 2016 Day 22
Advent of Code: 2016 Day 11
function parse(input) {
return input
.split("\n")
.map((s) => s.match(/(\w+ generator|\w+-compatible microchip)|(nothing)/g))
.map((items) => {
return [
items
.filter((item) => item.endsWith("generator"))
.map((item) => item.split(/[ |-]/)[0])
.map((item) => item.slice(0, 2) + "G"),
items
.filter((item) => item.endsWith("microchip"))
.map((item) => item.split(/[ |-]/)[0])
.map((item) => item.slice(0, 2) + "M")
].flat();
});
}
function atGoal(state) {
return state.slice(0, 3).flat().length === 0;
}
function getCombinations(items) {
const combinations = [];
for (let i = 0; i < items.length; i++) {
combinations.push([items[i]]);
for (let j = i + 1; j < items.length; j++) {
combinations.push([items[i], items[j]]);
}
}
return combinations;
}
function move(state, from, to, items) {
const newState = AOC.cloneArray(state);
for (const item of items) {
const index = newState[from].indexOf(item);
newState[from].splice(index, 1);
newState[to].push(item);
}
return newState;
}
function willFry(floor) {
const gens = floor
.filter((item) => item.endsWith("G"))
.map((g) => g.slice(0, -1));
if (gens.length === 0) {
return false; // Can't fry if no generators on this floor.
}
// Will fry if some microchip doesn't have a matching generator.
return floor
.filter((item) => item.endsWith("M"))
.some((chip) => !gens.includes(chip.slice(0, -1)));
}
function heuristic(state) {
let totalDistance = 0;
const k = 100; // A little larger than approximate shortest steps
for (let i = 0; i < 3; i++) {
totalDistance += state[i].length * (k - i);
}
return totalDistance;
}
function genericState(state) {
// Store a string of Gs and Ms representing number of generators and microchips on each floor
return state.map((floor) => floor.map((item) => item[2]).sort());
}
function minTransitions(state) {
const visited = new Set();
const queue = new PriorityQueue();
queue.put([state, 0, 0], 0);
while (!queue.isEmpty()) {
const [state, floor, nTransitions] = queue.get();
const gState = JSON.stringify([floor, genericState(state)]);
if (visited.has(gState)) {
continue; // We've been here before
}
visited.add(gState);
if (atGoal(state)) {
return nTransitions; // We've reached the top floor with all items!
}
const items = state[floor];
const payloads = getCombinations(items);
for (const payload of payloads) {
for (const direction of [-1, 1]) {
const newFloor = floor + direction;
if (newFloor < 0 || newFloor > 3) {
continue; // No floor to move to
}
const newState = move(state, floor, newFloor, payload);
if (willFry(newState[floor]) || willFry(newState[newFloor])) {
continue; // Invalid move
}
const priority = nTransitions + 1 + heuristic(newState);
queue.put([newState, newFloor, nTransitions + 1], priority);
}
}
}
return -1; // No more possible states and we haven't reached the goal.
}
function part2(input) {
const initState = parse(input);
initState[0] = initState[0].concat(["elG", "elM", "diG", "diM"]);
return minTransitions(initState);
}
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.
