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)