aoc2022 VS a2tools

It may be a nifty hash table (no, it is!:)) but the whole program runs about 12x slower on an M1 than my version where I first determine the max dimensions and simply allocate a grid of booleans... So I wonder how much the 8x8 bitset breakup could improve. But bitsets are a C++ feature. In C, like NRK: https://github.com/ednl/aoc2022/blob/main/09.c (my "startstoptimer.c" and .h are in the same repo)

I also checked lines but only after doing a rotation by 45 degrees, so the lines are straight. Compiled in C, fastest run time on M1 was 26 µs: https://github.com/ednl/aoc2022/blob/main/15.c

Same code but with preprocessed input to make it all fit into memory, runs in 7 ms on an Arduino Uno! https://github.com/ednl/aoc2022/blob/main/aoc22-15/aoc22-15.ino

Complete program runs in 463 µs on Apple M1, 2.61 ms on Pi 4. See comments at the top of the source file for how I measured. My comparison function:

Not 100% sure this is Upping-The-Ante, maybe just Other. I wanted to share some benchmark results of my solution for today, day 11 with the 10,000 monkeys, and how I got there. I think the easiest way to compare performance is to use the same hardware, and nowadays fairly common & standardised hardware might be the Raspberry Pi 4. Although, you can't buy any for years now... Best score I got when running my solution on my Pi 4 home server is 15.6 ms.

I quickly saw that I could do "item = item modulo (product of all div-test numbers)" but the implementation took me a while in C without queues or circular buffers. But that's all part of the fun for me! I didn't look for further clever optimisations because the compiled program runs in 20 ms on a Raspberry Pi 4. That was fast enough for today, I thought. Source code: https://github.com/ednl/aoc2022/blob/main/11.c

Yay, embedded software engineering!! :) Short, fast & almost no memory needed in C: https://github.com/ednl/aoc2022/blob/main/10.c or the relevant bits:

That's great, but on what hardware? My solution in C runs in 0.8 ms average (0.6 ms minimum) using hyperfine to measure 1000 runs in a Mac Mini M1. Same on a Pi 4 in performance mode: 3.6 - 3.8 ms.

Well, it took me a while to realise that in part 1 you always have to check the whole row or column because a higher tree can come at any point ... And except for skipping the borders, I couldn't come up with any sort of clever optimisation that would help reduce the O(N^2) complexity. It still runs in under 1 ms on a Mac Mini M1 according to hyperfine. Full code 52 lines without space/comments: https://github.com/ednl/aoc2022/blob/main/08.c

Here's the code: https://github.com/colinleroy/aoc2022/blob/master/a2tools/src/aoc/day23/day23.c

I only did part 1 tonight, somebody's literarlly doing Redditor wife at the office door.

Here's the (awful) code (it was less awful at the beginning when I didn't have to shrink everything to struct arrays with members have multiple purposes)

Well. I suck at doubly-linked lists so I shift one position at a time. This is quite a number of CPU cycles, but it's going to be quite a number of cycles anyway so let's leave it at that and spend the evening doing something else!

Here it is :)

I didn't do part 2 yet.

I'm stopping at part 1 because I guess part 2 would take days even if I figure out a good algorithm. Here's the code.

Quite happy with my solution for part 1, it runs in under a minute on the //c.

The night, for part 2. But the Apple 2 screen's not wide enough to use the hgr page as memory, so I need an array, but also there's not enough main ram to store char[350][170]... So I use this and it is slow (I should be able to improve it quite a bit though) https://github.com/colinleroy/aoc2022/blob/master/a2tools/src/lib/bool_array.c

So off we go read the input file twice, the first time to get the map boundaries, the second time to setup the bool array : part 1 using 2kB of RAM.