Advent of code - Day 23

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

Blog

Advent of code - Day 23

Quentin Ménoret

Join Our Newsletter. No Spam, Only the good stuff.

Related