DEV Community

loading...
Cover image for Advent of code - Day 23

Advent of code - Day 23

qmenoret profile image Quentin Ménoret ・2 min read

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))
Enter fullscreen mode Exit fullscreen mode

Feel free to share your solution in the comments!


Photo by Markus Spiske on Unsplash

Discussion (0)

pic
Editor guide