DEV Community

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

Advent of code - Day 13

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.

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)

pic
Editor guide