Last active
December 24, 2020 02:26
Star
You must be signed in to star a gist
Solution to Advent of Code 2020 Day 23 Part 2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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