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)