Well, running on the Apple //c. To be honest, most of the coding has been done on a modern laptop, at first using BASIC, then cross-compiled C using cc65, and transferred over serial.
Nevertheless, I’ve (re-)learnt a lot about this little machine that was my first computer, and doing it with arbitrary exercises like the ones Advent of Code proposes made for a very nice learning curve. At the start, the most difficult thing was getting the serial connection right. I could just code the solution that came to mind, and it would run, albeit slowly. Then with days passing, the level of difficulty raised both algorithmically, and also, even after having gotten the algorithm correctly, in terms of how to fit this into that. (is there a joke to be made there? I wouldn’t know). The Apple //c has 64kB of memory, of which you can use about 38 at best. A 1 MHz 8-bit processor that can’t do things like multiplication. A 40*24 screen that can display High-Resolution Graphics of 280*190 in 5 colors (including black and white), 3 of which look the same on a monochromatic display). A disk I/O bandwitch of about 150 bytes/second, and about 200 via serial.
Things started to get challenging on day 8. The problem was about tree visibility in a forest of 100×100 trees, which I initially tried to store in a DIM H(100,100) array, which… wouldn’t fit. Had to dig back to remember about BASIC variable type: VAR is a real number and takes 5 bytes to store. VAR$ is a string. VAR% is an integer number and takes 2 bytes. My array of 10000 real numbers would not fit, of course, but 10000 integers would.
Day 9 was the same problem: dataset size. This time, integers instead of reals would not suffice, as the map where I was supposed to be counting the number of coordinates visited was 267*220. That’s the day I ditched BASIC and started with cc65. I solved the memory constraint by using a bool_array implementation, AKA a bitfield, which takes one bit per coordinate. This translates to 7.5kB of memory, at the expense of slower execution time, as the Apple //c’s processor, the mighty 1MHz 6502, does not do multiplication natively.
Day 10 was much simpler, and running it on the Apple //c made it look even better, as it was about displaying a message on a very low-res “CRT screen” :
On day 11, I implemented a few basic string helpers, strsplit() and trim(), do parse the input in a cleaner way. In the end, I didn’t use them that much, because every malloc() counts and it’s much leaner to just *strchr(str, ‘ ‘) = ‘\0’ like in the old days. I also had to implement a bigint library to work on numbers of arbitrary size, and even though it’s really naive and slow, it does work, so I’m kind of proud of it.
Day 12 was fun, it was path finding, something I’m not very very good at but like a lot because it’s an algorithm that has very tangible real-world uses. I implemented a breadth-first-search algorithm that I later generalized a bit, and, as I wanted a visualization of the solving, had to figure out more things about cc65, the memory layout of the Apple //c (if you want to to “high-resolution graphics”, and by high resolution they mean 280*192, you get 3kB less RAM to use, plus all the kBs used by the graphics driver itself), etc. I ended up having a first program solving the path and writing it to disk, and a second one display it from the stored on-disk solution: (it’s totally going to be reused for a maze solver btw).
Then there was day 13, where you had to parse arrays of arrays of numbers and sort them using a complicated algorithm. The parsing itself was quite painful (I longed for a json_decode() or similar), but not especially challenging to run on the //c. The sorting, though, would never be possible as there was much too much data to fit in RAM. As smart people told me later, “you don’t have to sort the whole thing to get the result”, but as I’m not that smart, I implemented a floppy-based external sort. It solves the problem slowly, but with lots of very satisfying stepper motor noises.
Day 14 was simulating sand fall. As much as I did want to see falling sand make growing piles of sand, it would not be smart to do it, each grain taking more than two minutes to do its trip down (and the no-viz run told me there would be 28000 grains to fall). So I “cheated” by calculating whether a grain could end up there, from top to bottom, and the visualization looks like a pyramid:
Day 17 was a Tetris-like, where I was supposed to know the height of the tower after the fall of 2022 blocks. This day was mostly challenging because it was full of off-by-ones opportunities, but I managed to get something working… and then served myself with another bunch of off-by-ones to have a speedy-enough vizualisation, and instead of updating the whole screen, just update 1 pixel around the falling block. I’m keeping the source so that one day, I can make a crappy Tetris out of it.
Day 18 ? BFS again, but this time in 3D. Actually BFS was too slow and RAM consuming, so I did a DFS instead, which I didn’t take time to properly generalize. The problem with DFS is it’s recursive, and the recursion absolutely smashed the little 2kB stack of the Apple //c. So I did a DFS with a maximum recursion level of 19, and running it again and again until there were no “Unsure” result about reachability. It did work quite well, and my visualization, which I though would be crap at first — it shows slides of the 3D cube, one Z at a time — was quite satisfying in the end, looking a bit like a very low-res brain scan.
On day 21, the very mean memory constraints came back. (You can allocate about 28kB, 38kB maximum when bypassing the ProDOS dispatcher, never more, and the bigger your program is, the less free RAM you have). First of all there were 2200 monkeys with names of 4 characters each (which means 11kB of memory), that had either a number (two bytes) or an operation (left operand plus operator plus right operator, 5 bytes minimum). But then, as the algorithm consisted of making them ask other monkeys for numbers or operations to complete their own operation, the algorithm had to be recursive. (Well, it could be not recursive and iterate over the whole dataset, doing any immediately feasible operation and skipping the other ones, until every operation would be done, but that would have sucked). Oh, and did I mention? Bigints, again (one byte per digit with my implementation).
Instead, I wrote the program in two parts, one that reads the names and converts them to indexes, then writes a pre-digested input on disk, and the other one just opens this file and reads it at the relevant offset for every accessed monkey – an array, but on disk. This allowed me to allocate more RAM to the stack and less to the heap, and be able to, hopefully, recurse deep enough.
It did work, with a stack size set at 24kB, leaving ~6kB heap and ~7kB for the code. Once again, very satisfying floppy disk drive noises.
Day 22 was more simple and there were no specific issues. I could even do an high-resolution graphics viz in the main program.
The last day I did, 23, was another day with too much data in memory. Well, in fact, I could store the minimally required amount of data and have the answer, but that would require using an O(n+n^2) algorithm, which is just not an option on a processor doing 1000 cycles per second. So I stored a bit more data on floppy, allowing me an O(2n) algorithm. I made a little text-mode visualization for it, but it’s only enabled for the example data, has the real data has a map size of 70*70 ending at 112*112, just a bit more than the Apple //c is capable of textually displaying, 40*24.
In the end, I am very happy that my wife suggested to me that we should do the AOC, and extremely happy to have the weird idea to do it on the Apple //c.
I’ve learnt and relearnt a lot of things, have been really impressed at how much we take for granted now while we had been able to do so much on glorified calculators forty years ago, and have lots of ideas to play with this adorable computer. I want to do a maze solver. A Tetris. A CLI front-end to the home-control system, which will require coding a serial-http proxy. I’ve coded some quite helpful tools already, enabling me to send arbitrary files over serial without having to transfer whole floppy images via ADTPro. And I’m having a lot of fun!
