DEV Community

Cover image for Advent of code - Day 13
Quentin Ménoret
Quentin Ménoret

Posted on

Advent of code - Day 13

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.

First tough challenge of the year in my opinion! I really needed to invest some time for the part 2, as the standard brute force was completely impossible. Still, my solution is far from perfect and can be improved. I generate the result in ~ 90 seconds, but it could be instantaneous with a bit more optimisation. But hey, If It Works It Works! 😉

Here is my solution for day #13:

const buses = input
  .split(',')
  .map((x) => parseInt(x, 10))
  .map((x) => (isNaN(x) ? 1 : x))
  .map((busId, index) => {
    const minutes = busId
    return { busId, minutes, index }
  })
  .filter((bus) => bus.busId !== 1)
  .sort((a, b) => b.busId - a.busId)
  .map((bus, _index, array) => ({ ...bus, index: bus.index - array[0].index }))

function acceptableSchedule(buses) {
  const expected = buses[0].minutes
  return buses.every((bus) => {
    return (expected + bus.index) % bus.busId === 0
  })
}

// Find the distance between the two highest id buses
// To limit the number of possibilities you explore
// This could be used several time to go even faster
function findOffset(busA, busB) {
  const found = []
  while (found.length < 2) {
    busA.minutes += busA.busId
    if (acceptableSchedule([busA, busB])) {
      found.push(busA.minutes)
    }
  }
  return { startAt: busA.minutes, offset: found[1] - found[0] }
}

const { startAt, offset } = findOffset({ ...buses[0] }, { ...buses[1] })

buses[0].minutes = startAt

while (!acceptableSchedule(buses)) {
  buses[0].minutes += offset
  if (buses[0].minutes % (buses[0].busId * 10000000) === 0) console.log(buses[0].minutes)
}
console.log(buses)
Enter fullscreen mode Exit fullscreen mode

Feel free to share your solution in the comments!


Photo by Markus Spiske on Unsplash

Discussion (0)