Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Adventures in Advent of Code

davedelong.com

Post reply on HN
Print view View original

41–50 of 71 posts

Re: Adventures in Advent of Code

#41

Post by tialaramex »

rashkov wrote: post #37
mtlmtlmtlmtl wrote: post #26

Earlier quoted context omitted.

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, b…

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?

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.

Re: Adventures in Advent of Code

#42

Post by mtlmtlmtlmtl »

rashkov wrote: post #37
mtlmtlmtlmtl wrote: post #26

Earlier quoted context omitted.

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, b…

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 :)

Re: Adventures in Advent of Code

#43

Post by mtlmtlmtlmtl »

tialaramex wrote: post #41
rashkov wrote: post #37

Earlier quoted context omitted.

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?

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…

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.

Re: Adventures in Advent of Code

#44

Post by orlp »

forrestthewoods wrote: post #22
sokoloff wrote: post #12

Earlier quoted context omitted.

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

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

Re: Adventures in Advent of Code

#45

Post by orlp »

Volundr wrote: post #29
sokoloff wrote: post #12

Earlier quoted context omitted.

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 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.

Re: Adventures in Advent of Code

#46

Post by benced »

stareatgoats wrote: post #2

When your code fails it's never the fault of the language. It's always ones own fault, a typo, some error in the logic, or something. Debugging always reveals that with a stone face. Always. Except > "It turns out, there was a bug in Set.intersection(_:), but it had only been discovered this past June, and the fix hasn’t made it into a public version of Swift yet. "

For most engineers, you’ll have a handful of times in your career when the compiler or runtime really is the problem. The rest of the time it’s like 95% your fault and 5% the library’s fault.

Re: Adventures in Advent of Code

#47

Post by sordina »

Volundr wrote: post #29
sokoloff wrote: post #12

Earlier quoted context omitted.

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.

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

Re: Adventures in Advent of Code

#48

Post by wging »

angrais wrote: post #5
shaftoe444 wrote: post #4

I picked go for my language this year, which doesn't have good support for sets. May end up writing my own buggy implementation of this.

What if you used a map and stored the value as a key? Then get all keys? Could work as a simple alternative and you could check if values are in it. Requires thinking if you want to implement set difference or intersection. I just figured depending on needs using existing built-in types may be fun.

Intersections are the reason you'd want a set, as the original post indicates. See the problem here: https://adventofcode.com/2022/day/3 (sets are even more of a fit for part 2, which is hidden for an anonymous viewer).

Re: Adventures in Advent of Code

#49

Post by rufus_foreman »

No I won't be participating in Advent of Code, and no, it is not one of the highlights of my holiday season.

The highlights of my holiday season are stepping away from the keyboard and spending time with friends and family. The highlights of my holiday season do not include doing leetcode exercises, much as a I realize the need for leetcode exercises.

So, no. I will not be participating in your Advent of Code.

Re: Adventures in Advent of Code

#50

Post by w-m »

Wow, Dave DeLong! A name that reminds me of learning Objective-C for an internship in 2010. As he was very active on Stackoverflow back then, and blogging too, maybe? I haven’t kept track much of Swift and the he Apple ecosystem since, but seeing this post brings back good memories.
Post reply on HN