Advent of Code - adventofcode.com

My solutions:

1. Loop over 10×10×21×21 array. I killed it after it hadn't even found the start state after one second as the array is so sparse. Not a good way to go.
   
2. Hash the state instead: 47s.
   
3. Hash the state, calculate next states in a function, cache that function: basically the same as above.
   
4. Recursive calls from a state until all games are won, and caching: 0.18s.
   
   

Quite disappointed that my first instinct was so far off optimal.

Nearly caught up (still day 19 to do), but here was my part2 for today (~55ms)

from functools import cache
def part2(inp):
    p1, p2 = inp
    p1 -= 1
    p2 -= 1

    moves = list(Counter(map(sum, product(*repeat(range(1, 4), 3)))).items())

    @cache
    def winners(A, B, s1, s2):
        if s1 >= 21:
            return (1, 0)
        if s2 >= 21:
            return (0, 1)
        winA = 0
        winB = 0
        for move, freq in moves:
            newA = (A + move) % 10
            news1 = s1 + newA + 1
            x, y = winners(B, newA, s2, news1)
            winA += y * freq
            winB += x * freq
        return (winA, winB)

    return max(winners(p1, p2, 0, 0))

Could see where today (day 22) was going to go, just don't have time to look at part 2 now. I know how I'm going to approach it and I'll continue to think about that until later this evening until I actually get time to sit down and do it.

I went straight for the part 2 solution. Bit more complicated than it appeared at first!

Essentially the same as what I ended up with

https://github.com/jyates13/aoc2021/blob/main/d21/d21.py#L53

See a couple of people have got day 22p2. Took a while to get back to mine but seem to have got there in the end with a very suboptimal algorithm.

Definitely a little bit of wee came out first time I saw a matching answer for the example input:-

...
LOOP got 0 (nos now 2043 done=2336)
part2: 2758514936282235

Horrible code, way too messy, hacks everywhere. Takes ages even on the example input. Will bash my head against it again tomorrow, sort it out and clean it up.

Ha. Ran out of time. Day 23p2 my Dijkstra algorithm seems to be picking up nodes with lower tentative distances for some reason, lack the time to debug it. [EDIT - Fixed that but now it doesn't find a solution, plus it still takes too long. Something bigly amiss.]

Day24 looks equally hard given the top100 times and don't have any time today so I'll guess I'll leave the remaining challenges until after Christmas.

Then, at some point, I've got to redo them all in Go...

22 was a bit annoying. My first instinct was to add a negative block when there's an intersection (seemingly the fastest/simplest solution) but after I couldn't get it to work I convinced myself that splitting cubes would be easier. It was a pain.

Did not solve 23 part 2 before I had to travel home for Christmas but it was getting a solution (also Dijkstra), just giving me the wrong cost. I was hoping we'd done all the hard ones for the year so that was a nasty surprise

Today looks annoying as well

Today looks annoying as well

There must be a trick, because just naively trying the 9^14 combinations isn’t very feasible.

Yes, the trick will be working out what the program actually does with each input and how each of the inputs interact.

No time sadly.

Yep. Hopefully binary search or something is all you need but I'm skeptical.

D23 done, A* too slow so I went with recursion and memoising which was shockingly fast by comparison

Yep. Hopefully binary search or something is all you need but I'm skeptical.

See if you can spot a pattern in the calculations done on the input values. I have something which I suspect is right, but failed to collect the right information in my recursive call.

D23 done, A* too slow so I went with recursion and memoising which was shockingly fast by comparison

My basic approach using Dijkstra was ~4s, I did some mild perusal of other people's solutions and with an appropriate cost-function for A* got down to ~150ms.

I must have done something wrong with my Dijkstra as it wouldn't finish on the 4 row version.

https://github.com/jyates13/aoc2021/blob/main/d23/d23.py

With a bit of mutation I've found plenty of valid numbers. I was hoping you could find them by just changing a pair of numbers (so each number has 8 x 8 neighbours) and then use Dijkstra or similar with cost being z and for zero z you go by the larger the number the better. Then I tried mutating 3 numbers at a time. But it doesn't work, you just get stuck in a local minima or whatever. I think I have to read the program.

e.g.
best is my highest valid number but that one is wrong.

base: 59989387179819 best: 59989499379819 cost:  0
valid: 19989387179815
valid: 29989387179816
valid: 39989387179817
valid: 49989387179818
valid: 59389387119819
valid: 59489387129819
valid: 59589387139819
valid: 59689387149819
valid: 59789387159819
valid: 59889387169819
valid: 59912387179819
valid: 59923387179819
valid: 59934387179819
valid: 59945387179819
valid: 59956387179819
valid: 59967387179819
valid: 59978387179819
base: 59989387178719 best: 59989499379819 cost:  0
valid: 19989387178715
valid: 29989387178716
valid: 39989387178717
valid: 49989387178718
valid: 59389387118719
valid: 59489387128719
valid: 59589387138719
valid: 59689387148719
valid: 59789387158719
valid: 59889387168719
valid: 59912387178719
valid: 59923387178719
valid: 59934387178719
valid: 59945387178719
valid: 59956387178719
valid: 59967387178719
valid: 59978387178719

Done it by brute force. Ugh. Ended up checking like 60m cases for each of the last 3 digits. 12 minute runtime for each part in pypy.

And that's a wrap (modulo finishing some of the days in rust):

$ python main.py 
Day        Part 1         Part 2           Time [ms]
----------------------------------------------------
Day 01     1374           1418                  2.01
Day 02     1660158        1604592846            1.52
Day 03     3895776        7928162               4.52
Day 04     14093          17388                 3.80
Day 05     6397           22335               177.87
Day 06     393019         1757714216975         0.79
Day 07     355989         102245489             1.30
Day 08     473            1097568               5.64
Day 09     600            987840               55.01
Day 10     321237         2360030859            2.38
Day 11     1637           242                  28.11
Day 12     5252           147784                2.81
Day 13     724            CPJBERUL              2.63
Day 14     2233           2884513602164         3.94
Day 15     523            2876                772.99
Day 16     852            19348959966392        5.14
Day 17     14535          2270                  8.71
Day 18     4435           4802                599.87
Day 19     396            11828               547.72
Day 20     5475           17548                65.86
Day 21     503478         716241959649754      50.66
Day 22     603661         1237264238382479     82.99
Day 23     19167          47665               153.68
Day 24     29599469991739 17153114691118        0.24
Day 25     516                                319.61
----------------------------------------------------
                                             2926.96

Just snuck in under 3 seconds total solve time.

Finished everything! Run times for a few of the puzzles are over a minute each. There is definitely some room for optimization on a few of them. But I wrote everything in R, so speed was never the top priority.

Day 5 is proving a right pain. Sorting a list of 100,000 integers takes 10 minutes and 2GB of RAM in jsonnet using the stdlib's mergesort.

Hoping to get to the remaining days (23p2, 24, 25) tomorrow, plus having a run through of all of them (aiming for <1s total time).

(Day 24 is a bit of a tricky one in this respect as, ideally, the spirit of the challenge would be coming up with something that could come up with any suitable input and output the answer, and Day 24 is most commonly done with hand optimisation for the specific input. But I guess it'll just be an asterisk on this years' challenge.

the spirit of the challenge would be coming up with something that could come up with any suitable input and output the answer

That's how I felt about D24 and why I ended up with the 12 minute runtime. Even then I had to make assumptions about the input.

Right, finally caught up and finished it.

Day 23, still need to fix mine as it is still taking way more than 1s, but at least it does end up giving me the right answer for both the example and my input.

Day 24 my rejigged solution runs almost instantaneously and I assume it will work on every input that anyone doing AoC will be presented with (I can't test that as I don't have everyone's input). Obviously it cannot work on completely arbitrary input programs, but it's possible to do a much more generic solution once you work out what is doing under the covers.

Day 25, simple, if you don't forget to increment the moved counter when dealing with the v movers. That meant it stopped early and reported a solution that was too low (but not for the example input obviously).

Here's my Day 24 that should work nigh-on instantaneously for any valid Day 24 puzzle input. I haven't put the "how/why" in the code but you can find it elsewhere (/r/adventofcode for example).

https://gist.github.com/alexgreenbank/265a7fc88002e3be68c44d3bad06af64

Still working on my Day 23. Current code (in perl, which is generally slow for this kind of thing) gets the answer for both the example input and my input in about 5s but manages not to find the answer for some really simple input, so there's something still amiss there. Not sure whether to rewrite it in C or Go to make it a lot faster or find/fix the problem in Perl first.

That came around quick. Is this the year I get beyond the first week? Time will tell...

Lol same. Might engage but with no expectations on myself

I usually do them in C#; did day one as a pretty simple loop iteration then a lambda for Part two. Whenever I do these I always strongly suspect that anything I've done isn't the best way to do them.

As usual, I'll check reddit later to see that someone's managed to do the whole thing in a single line of python.