Are you participating in the Advent of code this year?
If you don't know what the advent of code is, it's a website where you'll find a daily challenge (every day it gets harder). It's a really fun event, you should participate!
I try to solve the exercises using either JavaScript or TypeScript and will share my solutions daily (with one day delay so no one can cheat!). I only share the solution for the second part.
The complexity for this one was only to use the right data structure so performance would be acceptable. With an array, I can't manage to get the solution in less that 90 minutes. Once you start using a Linked List, it drops to about 5 seconds (and the code becomes way more readable).
Here is my solution for day #23:
const CUPS_SIZE = 1000000 const allCups: Node[] = Array(CUPS_SIZE) export function runOneTurn(currentNode: Node) { const minimalValue = 1 const maximalValue = allCups.length - 1 const first = currentNode.next const second = first.next const third = second.next // Find destination let destination: number | null = null let potentialDestinationValue = currentNode.value - 1 if (potentialDestinationValue < minimalValue) potentialDestinationValue = maximalValue while (destination === null) { if ([first.value, second.value, third.value].includes(potentialDestinationValue)) { potentialDestinationValue = potentialDestinationValue - 1 if (potentialDestinationValue < minimalValue) potentialDestinationValue = maximalValue } else { destination = potentialDestinationValue } } currentNode.next = third.next third.next = allCups[destination].next allCups[destination].next = first return currentNode.next } class Node { next: Node value: number constructor(value: number, next?: Node) { this.next = next || this this.value = value } } export function process(input: string, turns: number) { const allValues = Array(1000000) input .split('') .map((v) => parseInt(v, 10)) .forEach((v, index) => { allValues[index] = v }) for (let i = input.split('').length; i < CUPS_SIZE; i++) { allValues[i] = i + 1 } allValues .map((value) => { const currentNode = new Node(value) allCups[value] = currentNode return currentNode }) .forEach((node, index, array) => { node.next = array[(index + 1) % array.length] }) let currentNode = allCups[allValues[0]] for (let i = 1; i <= turns; i++) { // if (i % 10000 === 0) console.log(i) currentNode = runOneTurn(currentNode) } const oneNode = allCups[1] const first = oneNode.next const second = first.next return first.value * second.value } console.log(process('925176834', 10000000)) Feel free to share your solution in the comments!
Photo by Markus Spiske on Unsplash
Top comments (0)