Posts and replies

More good news: I have gotten out part 1 of day 5 of #AdventOfCode, despite my language's attempts to silently truncate the comma separated list of numbers in my input to 10 items.

I don't think my structure makes part 2 that much more difficult, but that's a tomorrow problem.

Part 2 of day 6 of #AdventOfCode is being a little tricky, because I've backed myself into a corner where my I have an O(MN) algorithm. I've managed to reduce M so it grows slower than N, but this all would have been avoided if I'd just thrown more memory at the problem or implemented a hash table.

Took a quick look ahead at day 7, and it looks like we've got >32bit integers, which is also tricky, but I think I can reuse some old code for that.

Spent a substantial amount of time yesterday implementing a weird integer type (uint64 + a sign bit, that probably takes up 24 bytes of memory), along with base-10 parsing, fast conversion from builtin int32s, addition, multiplication (which is much slower than I'd like) and comparison.

My first strategy for part 1 of day 7 was very slow to run, so I tried to add some short-circuits, but didn't get the logic quite right there, so got the wrong answer. Went back to the drawing board and found a better way of approaching the problem using a stack. Unfortunately, the obvious way of putting my integer type into the stack leads to a landmine of language implementation bugs that should be impossible, so it again took a while to figure out how to redesign things to avoid that problem.

Anyhow, it's running now, and I should get an answer out in 20m or so. (I already wrote an independent implementation of my approach which got the correct answer)

Part 1 came out fine, but it took more like an hour to run (this is merely implementation issues, the same algorithm in Python takes < 1s).

I thought Part 2 would need me to implement base 10 rendering or division for my cursed integer type, but then I realised if I just defined 10, 100, 1000, … as constants, I could write something that would work for what I needed.

Unfortunately, my estimate is that my implementation of Part 2 has ~32x base operations as Part 1, so yeah, I guess I'll move onto Day 8 while that's running. #AdventOfCode

Day 8 of #AdventOfCode was uneventful, since I had binary search and COUNT DISTINCT from earlier problems.

Alas, Day 9 posed more challenges, since (a) the input has more characters in a line than previously seen; and (b) the naive way of turning those characters into digits had utterly awful performance. So I spent a bunch of time writing some specialised code, and then moved onto the actual problem. Part 1 was not too difficult, but I failed to think about the size of the answer, which fortunately made my int32 negative, so some judicious wrapping with my cursed integer type was necessary to get the right answer (with some performance cost).

I have a plan for Part 2, but I think I have exhausted my coding ability for tonight.

Finally managed to get part 2 of day 9 of #AdventOfCode working with a binary heap and a performance improvement to sorting with custom comparators.

Also added some utility functions for debugging so I don't have to keep commenting/uncommenting bits of code.

Spent the day catching up on #AdventOfCode.

I read part 1 of day 10 wrong the first time, and started designing a clever solution for it before realising it was a lot simpler than that. Conveniently, part 2 was what I had incorrectly assumed part 1 was.

I suspect that the optimisation I did to part 1 of day 11 was what most people needed to do to get part 2 working, so my part 2 is still running . Maybe I’ll actually drop a layer of abstraction to make my integer operations fast (which would help with part 2 of day 7, which I haven't yet has a successful run for).

My language has reasonable performance for sorting lists of numbers, but not for sorting anything more complicated than that, which means a common pattern has been encoding (x, y) as y*width+x (and whenever I need to add a direction to that, (y*width+x)*4+d). So far I haven't needed a tree or hash map—sort then do many binary searches is the common pattern—but I’m pretty sure I’ll end up implementing at least one of these (oh, does your language have them built in? how quaint.)

Day 13 of #AdventOfCode had two obvious solutions (brute force and do some maths), and so I did the maths for Part 1, which worked out quite nicely. Unfortunately, Part 2 introduced some bigger numbers, and my cursed integer type was not up to the job.

So now I have an implementation of arbitrary precision integer arithmetic with operators +-*/<>=, str and parse (in a language that has i32 but not u32). Division was the hardest part, I may have exclaimed "praise be to Knuth" at some point during this foolish endeavour.

Anyhow, Part 2 is done now.

Now up to Day 14 of #AdventOfCode: I took the easy approach for part 1, though I didn't carefully check my integer bounds, but it turned out to work just fine.

Part 2 was much more interesting: how am I meant to do image recognition on the robot positions?! But I reduced this down to "find an arrangement where lots of robots are together", which invited the following heuristic: if we put all the robot positions on a space-filling curve, then the length of the longest run of consecutive positions should be higher when lots of robots are together.

Found https://github.com/jakubcerveny/gilbert to give me a space-filling curve for the 101×103 grid, which I turned into an array of 10403 numbers, where indexing by y*103+x gives the position on the curve.

Made more progress up to Part 1 of Day 17 of #AdventOfCode.

But now I'm heading back to Part 2 of Day 7, which was lacking in performance. I've switched it to my bignum type, which has let me implement some algorithm improvements, and now it gives a correct answer in < 1h. \o/

Spent the evening wiring the first 10 days together, and now you can "play" a prerelease of my #AdventOfCode solution for 2024 at https://static.flowblok.id.au/pub/aoc2024/

This is a Glulx game implemented with Inform 7, which I used for Day 5 of 2023 (write-up: https://blog.flowblok.id.au/2024-03/advent-of-code-2023-day-5.html).

With the exception of Part 2 of Day 17 (which I've skipped because it looks rather involved, particularly when you lack bitwise operators), I now have everything up to Day 20 of #AdventOfCode published (https://static.flowblok.id.au/pub/aoc2024/)

(disclaimer: many of the solutions will be sloooow to run, and are not resilient to bad inputs)