NotAwfulTech

386 readers

4 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago

MODERATORS

self@awful.systems

Advent of Code 2024 - Historian goes looking for history in all the wrong places (adventofcode.com)

submitted 3 weeks ago by Architeuthis@awful.systems to c/notawfultech@awful.systems

54 comments fedilink hide all child comments

copy pasting the rules from last year's thread:

Rules: no spoilers.

The other rules are made up aswe go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

you are viewing a single comment's thread
view the rest of the comments

[–] swlabr@awful.systems 2 points 2 weeks ago

I will probably slow down and try to solve the problems on the weekends rather than daily. Anyway, 9:

part 1

This was straightforward in that all you need to do is implement the algorithm as given. I did optimise a little using the arithmetic progression sum, but this is a speed-up of, at most like, a factor of 9.

I am pretty sure I did an OK job at avoiding edge cases, though I suspect this problem has many of them.

part 2

Again, the algorithm is more or less given: Start from the back, look for a hole that'll work, and put it in if you can. Otherwise, don't. Then, calculate the contribution to the checksum.

The complex part was the "look for a hole" part. My input size was 19999, meaning an O(n^2^) solution was probably fast enough, but I decided to optimise and use a min heap for each space size prematurely. I foresaw that you need to split up a space if it is oversized for a particular piece of data, i.e. pop the slot from the heap, reduce the size of the slot, and put it in the heap corresponding to the new size.