Skip to content

Instantly share code, notes, and snippets.

@warriordog
Last active December 24, 2020 02:26
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save warriordog/c8349084ae29fd6b4646e3e2574d25b4 to your computer and use it in GitHub Desktop.
Solution to Advent of Code 2020 Day 23 Part 2
//const INPUT = [ 3, 8, 9, 1, 2, 5, 4, 6, 7 ]; // TEST input
const INPUT = [ 1, 6, 7, 2, 4, 8, 3, 5, 9 ]; // PROD input
const MOVES = 10000000;
/**
* @typedef {object} Cup
* @property {number} label
* @property {Cup} clockwise
* @property {Cup} counterClockwise
*/
/** @typedef {Cup[]} */
const inputCups = INPUT.map(label => ({
label,
clockwise: undefined,
counterClockwise: undefined
}));
const initialInputMax = INPUT.reduce((max, curr) => Math.max(max, curr), 0);
for (let i = 0; i < (1000000 - INPUT.length); i++) {
const label = initialInputMax + 1 + i;
inputCups.push({
label,
clockwise: undefined,
counterClockwise: undefined
});
}
inputCups.forEach((cup, i) => {
const clockwise = inputCups[(i + 1) < inputCups.length ? (i + 1) : 0];
const counterClockwise = inputCups[(i - 1) >= 0 ? (i - 1) : (inputCups.length - 1)];
cup.clockwise = clockwise;
clockwise.counterClockwise = cup;
cup.counterClockwise = counterClockwise;
counterClockwise.clockwise = cup;
});
function getCupByValue(value) {
if (value < 1) {
value = 1000000 - value;
}
if (value <= initialInputMax) {
return inputCups.find(cup => cup.label === value);
} else {
return inputCups[value - 1];
}
}
function insertClockwise(cup, next) {
// get original next
const nextNext = cup.clockwise;
// point next to cup and nextNext
next.clockwise = nextNext;
next.counterClockwise = cup;
// point cup to next
cup.clockwise = next;
// point nextNext to next
nextNext.counterClockwise = next;
}
function insertCounterClockwise(cup, next) {
// get original next
const nextNext = cup.counterClockwise;
// point next to cup and nextNext
next.counterClockwise = nextNext;
next.clockwise = cup;
// point cup to next
cup.counterClockwise = next;
// point nextNext to next
nextNext.clockwise = next;
}
function removeCup(cup) {
cup.clockwise.counterClockwise = cup.counterClockwise;
cup.counterClockwise.clockwise = cup.clockwise;
}
let currentCup = inputCups[0];
/** @param {Cup[]} rCups */
function findInsertionCup(rCups) {
let targetValue = currentCup.label;
// find a value that is not in the removed
do {
targetValue--;
if (targetValue < 1) {
targetValue = 1000000;
}
} while (rCups.some(rCup => rCup.label === targetValue));
// Find the cup
return getCupByValue(targetValue);
}
function playMove() {
// pick up cups
const rCups = [];
for (let i = 0; i < 3; i++) {
const rCup = currentCup.clockwise;
removeCup(rCup);
rCups.push(rCup);
}
// find insertion point
const insertionCup = findInsertionCup(rCups);
// insert cups
let insertCup = insertionCup;
for (const currCup of rCups) {
insertClockwise(insertCup, currCup);
insertCup = currCup;
}
// select new current
currentCup = currentCup.clockwise;
}
function playAllMoves() {
for (let i = 0; i < MOVES; i++) {
playMove();
}
}
// Part 2
playAllMoves();
const cup1 = getCupByValue(1);
const cup2 = cup1.clockwise;
const cup3 = cup2.clockwise;
console.log(`Part 2: The final result is ${ cup2.label } x ${ cup3.label } = ${ BigInt(cup2.label) * BigInt(cup3.label) }.`);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment