5 ms·
This years challenge for me: write it in C without the standard library or an allocator. Has to be runnable on an STM32 with 32kb of SRAM. I tried doing it in
by the_duke 2y ago
This years challenge for me: write it in C without the standard library or an allocator. Has to be runnable on an STM32 with 32kb of SRAM.
I tried doing it in Assembly two years ago, ended up spending hours and hours writing an Assembly standard library, then gave up and switched to Rust...
- BoingBoomTschak 2y agoGood 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 agoI 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 agoPerhaps 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 agoPOSIX `hsearch` is absolutely terrible and almost useless, but... it would get the job done for this problem.
- BoingBoomTschak 2y agoThe 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 agoI 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 agoThe 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 agoAlso 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.
- sebtron 2y agoYour restrictions sound quite challenging, good luck! Last year I solved all the problems in C without external libraries [1] and I enjoyed it a lot. It forced me implement some low-level stuff that I had forgotten how to do (e.g. a heap) and to write some numerical routines myself (easier than you'd think!). [1] https://github.com/sebastianotronto/aoc/tree/master/2023 https://github.com/sebastianotronto/aoc/tree/master/2023
- derethanhausen 2y agoFitting, given that iirc one of the problems was to implement a hashtable!
- badgersnake 2y agoLast year I tried C on a real Amiga 1200 (using DICE, Matt Dillon’s compiler / runtime). I didn’t get very far, lack of memory protection makes things really hard. This year the Amiga has an 060 upgrade with an MMU, so perhaps I can figure out how to use that and have another go.
- peterashford 2y agoHeh. Yeah, a memfault tanking the machine is not conducive to iterative programming :o)
- lanstin 2y agoHonestly, I forgot all about that aspect of ancient programming. It probably made one more careful, or more patient. (Source: typing 6502 programs into a hex "monitor" which is a way to edit memory, view memory, and issue "jump to this memory address".)
- rob74 2y agoGuru Meditation anyone? (https://en.wikipedia.org/wiki/Guru_Meditation https://en.wikipedia.org/wiki/Guru_Meditation)
- RandomThoughts3 2y agoJust stop writing memfault. I say it in jest but that's actually how I used to program a few years ago when I was working on large industrial pieces of software with long compilation time. You just have to be careful and check what you wrote before sending it to the machine. I think "iterative" programming has made people really complacent when it comes to silly errors. Slowing down can often do wonder.
- ChrisRR 2y agoI feel like if you're writing C then writing with memory safety in mind should probably be autonomous anyway
- simmonmt 2y ago
- 127 2y agoDo you have a public repo?
- ikiris 2y agothis is like trying to solve it in a computer built in turing complete
- mlsu 2y agoGlorious! I think I'll follow in your footsteps. STM32F7 with 320k but with bare metal Rust :)
- nine_k 2y agoSymmetrically, I would consider only using sh and standard non-Turing-complete CLI tools (grep yes, awk no). About as limiting, but without devastating memory corruption bugs.
- a_humean 2y agoI think there might end up being some problems which will be very challenging to solve with those resource constraints - namely memory. You will probably have to be pretty clever with your solutions. I remember one of my naive brute force solutions from last year ended up allocating gigabtyes of memory. There were obviously more efficient solutions, but some of the inputs are pretty large and so hefty allocations might be difficult to avoid.
- foota 2y agoAs long as you can make an RPC call, anything is doable within 32kb of ram :-)
- uticus 2y agoAssembly is so much cleaner on an STM8 8-bit. If you’re into that sort of masochism
- ChrisRR 2y agoI tried doing it in C a few years ago but wasted so much time just not having a string library