Yesterday was a cool one. I usually enjoy the simulation puzzles. Although I did have some brain farts when it came to rotating things on a discrete grid. We're now officially over halfway done! Keep it going!
In today’s puzzle, we're officially done with boats! Boats are so yesterday. Today, shuttles are the new boats, and we're trying to optimize our way through a staggered schedule of departures to get on our way to another airport.
As always, this is the spot where I’ll plug any leaderboard codes shared from the community.
Ryan's Leaderboard: 224198-25048a19
If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.
Updated 07:55AM 12/13/2020 PST.
Top comments (14)
I don't know about those theorems. It's a prime factorisation problem (and evidently all bus numbers are prime numbers, so that makes it even easier). My Ruby solution is general purpose (so also non-prime busses) but 🤷
Thanks for this. I was really stuck on this; came on here and saw folks mentioning a new theory (which bummed me out). I had been trying to figure something out with LCM, and your solution showed me what I'd been missing. Here's the core of mine:
No way I could figure out part 2 without googling. I was playing around with least common divisor + gcd + clever looping. Finally googling around I found the chinese remainder theorem.
rust rust rust :)
Man, this turned out really concise. Also, thank you for letting me shamelessly steal your logic for part 2 :D
Part 1 JS solution, (maybe) Part 2 coming soon (This Chinese remainder theorem thing sounds complicated for a 7th grader and looking at other comments brute force for part 2 doesn't seem like an option)
Solution of Part 2 in Python
More efficient if list of buses was ordered from highest to lowest, the iterator would be the necessary remainder of the first bus, the increment would be the first bus and the first element of the list wouldn't be iterated
I feel really, really proud of myself for coming up with a fast algorithm for this pretty much on my own with no cheating. The only thing I'll say is that I saw other people commenting about prime numbers, which led me down the right track. I've got it commented in part two down in the code, but essentially, if you try to get each bus to fall into step incrementally, and you multiply your timestep by each found bus's ID, you can keep pace with the complexity of the problem for an arbitrary number of input busses. It's because, since the inputs are prime, they would only coincide on a number where they are multiplied together, and the same relationship applies even if you shift the second one by one.
As I write this, I know it doesn't make any sense, but just take a look at the code and see if that helps at all.
I worked out the algorithm on my own with no googling too. We should get extra stars!
OK, I just discovered AoC, more than a month late... This one had me stumped, I took it from the hints that it should be brute-forceable, but it just took too long. Then I saw this video that inspired me to try to construct a solution one bus id by one, and once I did that modulo the product of all the bus id's, it was correct! In Odin (which I am trying to learn for this occasion): [edit: after modification, the modulo on the endresult is no longer needed]
Well today's AOC 2020 was interesting, initally I thought it was going to be very straightforward, but that turned out not to be the case. Part 1 I could just do by force, but I got very stuck on part 2, as it was going to take a very long time :-) So after some pointers on reddit I ended up learning a new bit of number theory to make it work, utlizing a extended GCD from stack overflow.
Once I knew about that, it was a lot easier, not to mention quicker:
Staying true to COBOL
I admit I tried to brute force part 2 at first, then had to think about it. The solution was quite neat in the end and runs in 4 milliseconds.
Only going to post my part 1 solution here, as I cheated and read through the thread in order to figure out part 2. Looking back, the brute force solution would have taken quite a while to show up; glad I didn't just "set and forget."
Anyway, part 1 in Rust. As always, on Github.