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?
Adventures in Advent of Code
61–70 of 71 posts
Re: Adventures in Advent of Code
#62Related: It's possible to simplify things using bitmaps: https://github.com/antirez/adventofcode2022/blob/main/day-3/...
Hey, just noticed our impls. for Day 2 look very similar. If you’re curious, Day 2 can be further improved by using modulo + 2 (or 1 if compiler is smart enough) branches instead of lookup table: https://github.com/neon-sunset/AOC2022/blob/main/Day2/Progra...
In which way do you reckon doing modular arithmetic is an improvement over two 3x3 look-up tables?
Re: Adventures in Advent of Code
#63I 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.
Right, that's exactly what I've done and is, I think, the idiomatic way to do it in Go. I meant for things like intersection, union, etc I will have to write my own implementations, but that's part of the fun!
Re: Adventures in Advent of Code
#64I 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.
I hear you. That's part of the joy I seek with AoC. Most years I choose a language I've never worked with commercially (e.g. Fennel in 2022) and rather than reach for prebuilt libs for timesaving fancy array or set or string ops, I'll invent those wheels myself without dependencies and I find a ton of satisfaction in it. Unwise commercially but ideal for learning and play. And, yeah, bugs! IMO, when it's not a custom…
It is great fun to try and build as much as possible yourself. Last year I ended up with a pretty good A* implementation in Clojure cos it kept coming up in the puzzles and I learnt a ton from doing it.
Re: Adventures in Advent of Code
#65Earlier quoted context omitted.
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.
You don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.
Great idea!
Re: Adventures in Advent of Code
#66Earlier quoted context omitted.
Hey, just noticed our impls. for Day 2 look very similar. If you’re curious, Day 2 can be further improved by using modulo + 2 (or 1 if compiler is smart enough) branches instead of lookup table: https://github.com/neon-sunset/AOC2022/blob/main/Day2/Progra...
In which way do you reckon doing modular arithmetic is an improvement over two 3x3 look-up tables?
The rationale is as following - if the compiler cannot fold the lookup table, then math with 1-2 branches will be much cheaper because it involves no memory access and has constant (low) latency (keep in mind that when for example selecting a literal, a conditional select might be emitted which is usually cheaper than a regular branch e.g. Aarch64).
In addition, unlike in C, in many other languages indexing into array will involve bounds check if the compiler cannot prove that the access is always in bounds. Obviously most branches will be predicted but branch retire throughput is always lower than math operations throughput.
Re: Adventures in Advent of Code
#67Earlier quoted context omitted.
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.
You don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.
Could you expand on this, ideally with a python implementation?
Re: Adventures in Advent of Code
#68I'm doing AoC in Rust and Go. Go, because I got cozy with it during this year. With Rust, however, I never did. I tried, though. So let's try again.
Re: Adventures in Advent of Code
#69Earlier quoted context omitted.
You don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.
Could you expand on this, ideally with a python implementation?
Here you go. https://pastebin.com/raw/BzEQ1bfe
For the problem we don't care how many instances of each letter occurs. We just need to know if there is 0 or 1 instance of a given letter. A set is a pretty good way to do this. Store a set of each "compartment", intersect the two sets, and you should have one value.
We can do the same thing except instead of a set we use an integer and set bits. a-z are bits 0-26 and A_Z are bits 27-52. We can set a bit with bitwise-or. We can intersect two masks with bitwise-and.
My code is probably a little too verbose. I'm not super familiar with python so I wasn't sure the best way to deal with characters and integers. But it's functional.
Re: Adventures in Advent of Code
#70Earlier quoted context omitted.
In which way do you reckon doing modular arithmetic is an improvement over two 3x3 look-up tables?
The rationale is as following - if the compiler cannot fold the lookup table, then math with 1-2 branches will be much cheaper because it involves no memory access and has constant (low) latency (keep in mind that when for example selecting a literal, a conditional select might be emitted which is usually cheaper than a regular branch e.g. Aarch64). In addition, unlike in C, in many other languages indexing into arra…
Thanks for the reply. The bounds checking is a valid reason I haven't thought of. In my case, using 3x3 array is roughly 3-4 times faster.