4 ms·

Good luck! Personally, I'm still going with CL but decided to try it in all the languages I "know" for the first day. Including C which doesn't have hash tables

Good luck! Personally, I'm still going with CL but decided to try it in all the languages I "know" for the first day. Including C which doesn't have hash tables (inb4 hsearch)... what a pain, let me tell you. https://git.sr.ht/~q3cpma/aoc2024/tree/master/item/01 https://git.sr.ht/~q3cpma/aoc2024/tree/master/item/01 If you could post a repo link so I can look at some of the progress, I'd be grateful.

nickstinemates 2y ago
I just want to note that Quake 3 CPMA is one of the best games ever made. No idea if the handle is in reference to that, but thanks for the :)
- schubart 2y ago
  Perhaps it’s a reference to the Kraftwerk song? https://www.musixmatch.com/lyrics/Kraftwerk/Boing-Boom-Tschak https://www.musixmatch.com/lyrics/Kraftwerk/Boing-Boom-Tscha...
shawn_w 2y ago
POSIX `hsearch` is absolutely terrible and almost useless, but... it would get the job done for this problem.
- BoingBoomTschak 2y ago
  The advantages of foregoing hsearch is that I don't have to understand its weird API that works only for NUL-terminated string keys and that I don't require POSIX. Remember that brute force is also a solution in the AoC; had plenty of fun using SBCL to crack some problems where Pythonistas had to be clever, last year =)
Twirrim 2y ago
I don't think there are enough entries to make it worth the cost of a hash. I know it's not "efficient" exactly, but just repeatedly looping through and counting just isn't that slow.
- 9029 2y ago
  The numbers are so small that you can also just use a big array
liontwist 2y ago
- bsearch + qsort is a great way to implement associative tables - you can implement a hash table in C in about 125 LOC and reuse it. - hash tables are not the only way to solve problems. hammer/nail
- lanstin 2y ago
  Also the TclHash table implementation is quite good and independent of the Tcl interpreter runtime.
- a-french-anon 2y ago
  > bsearch + qsort is a great way to implement associative tables Only if you write/read your table in two separate passes. A tally needs mixed read/write to increment a counter, not just insertion, so it must be kept sorted during the table creation. Some kind of tree or linked list is probably better in this case. > you can implement a hash table in C in about 125 LOC and reuse it. I know. Anyone who uses C and never made at least a basic FNV1A/bucket-based hash table must be insane. But I wanted a small self-contained .c here and have become allergic to (void *); if I were to use C seriously, I'd fix it using a better preprocessor (à la https://github.com/etwyniel/c-generics https://github.com/etwyniel/c-generics). > hash tables are not the only way to solve problems. hammer/nail Eh, a tally seemed the most intuitive way for the 2nd part.
  - liontwist 2y ago
    > incremental insert vs two pass Insert each element in its sorted position. It will only degenerate if there are many more inserts than lookups, in which case a hash table would do nothing for you. This could also be a good case for a radix structure. > void* hash table I would stay far from poor implementations of high level languages. Why use C if you want generics? A reusable hash table can be implemented by implementing open addressing with 64 bit integer keys. Then if you have a fancy type you write a hash function and perform linked list chaining on the values. Another way is to treat the keys as byte arrays. > seemed the most intuitive way for the 2nd part. Intuition is a kind of familiarity. There is no reason to learn C if you just write the techniques you already know in a less safe and more verbose way. You instead should be learning a new way to think about problems.

nickstinemates 2y ago

I just want to note that Quake 3 CPMA is one of the best games ever made. No idea if the handle is in reference to that, but thanks for the :)

schubart 2y ago
Perhaps it’s a reference to the Kraftwerk song? https://www.musixmatch.com/lyrics/Kraftwerk/Boing-Boom-Tschak https://www.musixmatch.com/lyrics/Kraftwerk/Boing-Boom-Tscha...

shawn_w 2y ago

POSIX `hsearch` is absolutely terrible and almost useless, but... it would get the job done for this problem.

BoingBoomTschak 2y ago
The advantages of foregoing hsearch is that I don't have to understand its weird API that works only for NUL-terminated string keys and that I don't require POSIX. Remember that brute force is also a solution in the AoC; had plenty of fun using SBCL to crack some problems where Pythonistas had to be clever, last year =)

Twirrim 2y ago

I don't think there are enough entries to make it worth the cost of a hash. I know it's not "efficient" exactly, but just repeatedly looping through and counting just isn't that slow.

9029 2y ago
The numbers are so small that you can also just use a big array

liontwist 2y ago

- bsearch + qsort is a great way to implement associative tables - you can implement a hash table in C in about 125 LOC and reuse it. - hash tables are not the only way to solve problems. hammer/nail

lanstin 2y ago
Also the TclHash table implementation is quite good and independent of the Tcl interpreter runtime.
a-french-anon 2y ago
> bsearch + qsort is a great way to implement associative tables Only if you write/read your table in two separate passes. A tally needs mixed read/write to increment a counter, not just insertion, so it must be kept sorted during the table creation. Some kind of tree or linked list is probably better in this case. > you can implement a hash table in C in about 125 LOC and reuse it. I know. Anyone who uses C and never made at least a basic FNV1A/bucket-based hash table must be insane. But I wanted a small self-contained .c here and have become allergic to (void *); if I were to use C seriously, I'd fix it using a better preprocessor (à la https://github.com/etwyniel/c-generics https://github.com/etwyniel/c-generics). > hash tables are not the only way to solve problems. hammer/nail Eh, a tally seemed the most intuitive way for the 2nd part.
- liontwist 2y ago
  > incremental insert vs two pass Insert each element in its sorted position. It will only degenerate if there are many more inserts than lookups, in which case a hash table would do nothing for you. This could also be a good case for a radix structure. > void* hash table I would stay far from poor implementations of high level languages. Why use C if you want generics? A reusable hash table can be implemented by implementing open addressing with 64 bit integer keys. Then if you have a fancy type you write a hash function and perform linked list chaining on the values. Another way is to treat the keys as byte arrays. > seemed the most intuitive way for the 2nd part. Intuition is a kind of familiarity. There is no reason to learn C if you just write the techniques you already know in a less safe and more verbose way. You instead should be learning a new way to think about problems.