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)
Feel free to share your solution in the comments!
Photo by Markus Spiske on Unsplash
Top comments (0)