I gotta say, there are some entries on the leaderboard that seem fishy to me. For example, on day 1, the first place entry on the leaderboard took 4 SECONDS to complete the first part, and 9 SECONDS to complete both parts. Admittedly the first day was pretty easy, but how could you even read the instructions in 4 seconds, let alone type in a program to solve it?
Probably just an AI solution: It was, of course, an AI-generated solution; they posted it here: https://web.ar... | Hacker News
Man, part 2 of day 7 is killing me. I wrote a program which I am pretty sure is correct, but is way too slow. I just try every possible permutation of the 3 operators, so the runtime is exponential in the number of operators. I could see it was going to take forever, so I split the 850 lines of input data into 12 pieces and ran 12 instances of my program in parallel on a 12-core CPU. After running for about 13 hours, 2 of the programs have finished; 10 are still running. Yet some people have solved it in minutes. Because of the size of the numbers I’m using Perl’s bigint library, which is pretty slow, but I don’t think that’s the main issue. There must be a better algorithm than the one I’m using.
Today was a struggle for me because I overthought it. I had a idea for a solution but thought it would be too slow so I tried to think of clever shortcuts. The first solution I tried (the one I thought was clever) was slower than the one I eventually tried (the one I had thought would be too slow). I guess I have a lot to learn about efficiency!
Day 11 has stumped me. A correct algorithm was pretty easy, and I got part 1 in a few minutes, using an obvious algorithm that keeps a list containing one entry for each pebble. But part 2 (extending the run from 25 to 75 blinks) seems to result in far too many elements for that algorithm to work. The number of pebbles increases by a factor of about 1.5 for every blink. I ran it for 45 blinks, at which point the list was about 500 million entries long. Running for the remaining 30 blinks would, I estimate, result in a list about 96 trillion entries long. There’s no way to keep such a list in memory. Perhaps careful analysis of the rules would reveal some shortcuts but I’m not seeing it immediately.
Hint for day 11: You don’t need a list of the pebbles. You just need to count how many there are. The order of the pebbles doesn’t matter.
Another hint for day 11: You will be performing the same calculations repeatedly.
We’ve reached the halfway point! Today’s problem made me glad I took linear algebra in college. I vaguely remembered I could use that to solve this kind of problem but had to refresh my memory to actually solve it.
At first I thought day 13 was going to require some weird modification of Euler’s algorithm and Bezoit’s identity. But yeah, it’s just a pair of linear equations in two unknowns.
Well, we’ve reached the point in the event where it’s starting to become difficult for me. I got stuck on part 2 of day 15, but eventually solved it. Then I got stuck on part 2 of day 16. I haven’t even looked at days 17, 18, and 19 yet. Some of my relatives will be coming for Christmas soon so I’ll have less time to do the puzzles. I’m hopeful that I can still finish sometime next year!
Yeah, they’re definitely getting harder.
Day 15 part 1 was fun. Part 2 changed things enough so that I had to throw away my part 1 solution and take a completely different approach, but I eventually got that one too.
I spent a couple of days thinking about day 16 because I thought there might be some trick that would make it unnecessary to write a general-purpose maze solving algorithm. Finally I solved it with an implementation of Dijkstra’s algorithm. I haven’t done part 2 yet; I have some ideas but the problem doesn’t actually seem interesting enough for me to put in the work yet.
Day 17 part 1 was pretty straightforward and fun. However there must be some trick for part 2. I tried an simple approach that reuses most of my part 1 solution but it ran for several hours without finding a solution, so there must be a trickier way to do it, which I haven’t yet been motivated to try to find.
Day 18 is another maze solving problem, which I’m getting kind of tired of, and haven’t yet attacked.
Day 19 is kind of interesting. I thought I had a clever idea to solve it by translating it into an exact-cover problem and using Knuth’s Dancing Links algorithm. I implemented that, and it worked for the sample problems, but when I tried to run it on the main problem I could see that it was going to be much too slow, so I gave up on that approach. I noticed an interesting feature of the input data that I hadn’t noticed at first, which might lead to a more fruitful approach, but haven’t gotten to it yet.
Last December, I got stuck at day 17, part 2. A few days ago, I decided to give it another try. I got through that one and then the next few days weren’t too bad until I got to day 24, part 2. I eventually solved that one and day 25. I have now completed year 2024! I have 50 stars for 2024 and a total of 484 stars for all years.