Hacker News Reader

Comment by mtlmtlmtlmtl | Hacker News Reader

I'll be doing AoC in C this year. And I've decided to do that every year as I enjoy doing it in C and trying to get the entire calendar, all 50 parts to run in less than one second on a single core, which it turns out is quite doable, but only with a much deeper understanding of the problems. I end up learning a lot more computer science this way.

I also like it since I don't do any work or even side projects in C these days, and so it's nice to keep my C chops up to scratch.

View on HN

Hat tip if you did 2021:14:2 under this constraint. I didn’t find the trick to allow that type of performance.

Day 22 (https://adventofcode.com/2021/day/22) is the one that nearly killed me in 2021. I did get it using a technique of breaking any overlaps into smaller and smaller rectangles, but it took like 30s to run. I looked on the AoC reddit, and honestly I still don't understand what I needed to do to make it better, but visualizing 3d spaces has always been a weakness for me.

My day 22 solution runs in <10ms: https://github.com/orlp/aoc2021/blob/master/src/bin/day22.rs

The trick I used was to represent signed volumes, compute the intersection and then store the 'negative cube' instead of splitting up cubes.

My target is usually 1 second each, because that feels about right for my patience, rather than 1 second overall target.

My 2021 (Rust) solutions all meet that, but some only do so when optimized, and day 22 was one of those where without the optimizer I'm waiting 2-3 seconds for an answer.

IIRC the trick was to compact the indices, so e.g instead of thinking about X values of 120203 494302 and 109383 you call those 1, 2, 0. Do all the working out of which cells within the resulting tiny structure are on or off, and then expand the 1x1 cells you're talking about to their true size based on the real values instead of indices.

Yeah same! It really was a tricky one for me: https://github.com/sordina/advent2021/blob/solutions/src/Adv...

Is that the right day? My code for 2021:14 runs in 440 microseconds for both parts. 2021:23:2 is the only day I couldn't get under 1 second.

https://github.com/forrestthewoods/aoc2021/blob/master/rust/...

My 2021 day 23 runs in 5 milliseconds for both parts using A* with a custom heuristic: https://github.com/orlp/aoc2021/blob/master/src/bin/day23.rs

I have a writeup of my 2021 solutions at https://programsareproofs.com/articles/aoc_2021.html. I got day 23 down to 31ms using Rust.

I struggled with that one; thanks for linking your code; I’ll have a look and see the trick I missed.

The key is you didn’t need to keep track of the strings, just the counts.

I don't think I did the 2021 one, but I did do 2020.

Nice! I’m writing in C this year too, although I’m very much a beginner in C.

What kinds of optimisations have you had to do? Are you hosting your code anywhere?

For doing it in C, by far the most useful thing you could do is implement your own generic hash table. Having a good hash table handy makes things a lot easier. Though since you're a beginner you might want to find a good library for it at first. Writing a hash table is great C exercise though, so I definitely recommend doing it at some point.

I don't necessarily want to share my github as it contains my real name, but I'd be willing to send you a tarball of my 2020 code tomorrow if you send an email to mtlmtlmtlmtl at pm.me

I've just now started on day 1 for this year, so no code there yet worth showing off.

I think I understand how to build a hash table except for one thing: which hash function should you use? Is there a simple one that’s good enough for most things? How do you pick one?

You would write your hash table constructor to accept a hash function as a function pointer then pass in the appropriate hash function for whatever the key type is.

You can use the same hash function for any arbitrary struct as long as there's no pointers in it. If there are pointers, you'd have to implement one combining the hashes of all the members through something like xor. I used fnv1a_64 for my hash function in AOC 2020 which is a pretty good general choice for strings and other contiguous objects and is just 10 lines of code. Pseudocode on Wikipedia or I'm sure you can find C code on Stackoverflow. Hope that helps :)

if your hash table is a really good modern open addressed hash table, something like Google's Swiss Tables, you need a really good hash because you will be badly penalised otherwise, these modern structures demand a hash with proper behaviour for even halfway reasonable performance.

If it's just a My First Hash table with closed addressing, buckets etc. you needn't care too much. If you're hashing integers, just use the integer itself, that's a terrible "hash" but with this like 1980s data structure it's good enough.

A lot of the time if the key is an int however you can get away with an array assuming the range is reasonably small.

Worth noting that for AOC I got by just fine with the simplest possible bucket based implementation.

Short answer: FNV-1a.

https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo...

https://github.com/rurban/smhasher#summary

Reply on news.ycombinator.com