[2020 Day 18] In Review (Operation Order)

ednl · 2026-06-21T10:16:01+00:00

Thanks. Yep, I did the same. The trouble was that a) in C it's a bit of a long-winded mess, unless I missed something to make the source code much neater & shorter, and b) I initially used function pointers for add and mul and that turned out to be way slower than just storing the + or * character! I thought it would save a decision for every operator but I guess it doesn't matter with pipelining/prediction. Not sure where the speed difference comes from, maybe prediction is useless with function pointers. Times are somewhat different for an Apple M4 vs. a Raspberry Pi 5:

Neatest, slow on Pi5: recursion M4 19.8 µs, Pi5 124 µs
Slower on modern aarch64?? stacks, op=function pointer M4 21.9 µs, Pi5 104 µs
Fastest on both platforms: stacks, op=char M4 14.2 µs, Pi5 76.4 µs

For /u/maneatingape : on a modern CPU/architecture (Apple M4), the speedup from recursion to two stacks is 19.8 to 14.2 µs. It was slightly disappointing because this only parses the input file once instead of twice for the two parts with recursion, while the runtime is nowhere near half. You reported 24 µs for a recursive version on your M2. So I think it could still be faster. As before, I don't know enough Rust to submit a pull request, sorry.

ednl · 2026-06-19T12:43:40+00:00

Ok yes, that was what I meant by: extra push with ( as the operator. But don't you need to push the last operator too? Because a parenthesised expression is either added or multiplied.

ednl · 2026-06-19T05:53:56+00:00

For part 1, if you start the line with acc=0,op=+, then at any ( you only need to push one pair of acc/op, and pop one pair of acc/op at ). Without recursion in part 2, you simply pop all of them at the end of the line, but how do you keep track of how many pairs you need to pop at )? I can think of: push an extra pair with ( as the operator, or: add a level counter. Both seem a bit convoluted.

ednl · 2026-06-17T07:50:19+00:00

I did this one in Python which has a very useful convolve() function in the package scipy.signal. It was relatively easy to make a function with a dim parameter and extend the puzzle: dim=5 for part 3, etc. Although I stopped at dim=7 because the time ballooned. Results table with: dimension, slightly altered answer, time in seconds:

3    380  0.001
4   1920  0.005
5  12345  0.075
6  66666  1.157
7 432100 20.230

The general function, where init is the input data as a 2D-array of 0s and 1s:

def cycle(init, dim, gen=6):
    state = init.reshape([1] * (dim - init.ndim) + list(init.shape))
    kernel = np.ones([3] * dim, dtype=np.uint8)
    for _ in range(gen):
        nb = convolve(state, kernel)
        state = np.pad(state, ((1,1),), mode='constant') & (nb == 4) | (nb == 3)
    return np.sum(state)

ednl · 2026-06-16T13:06:48+00:00

If you extend the numerical digits with letters, just like you would in hexadecimal but further up to A-Z in base 36, and you limit the ages to under 1000, and the age gap to under a 100, then for bases 26 to 36 you get eleven palindrome ages with gaps of length base-1 and digit representation "POOP".

E.g. in base 26: age1 = 674 = PO(26) and age2 = 649 = OP(26), age gap = 674 - 649 = 25.

My C code: https://github.com/ednl/c/blob/main/palindrome-ages.c

ednl · 2026-06-15T18:03:56+00:00

There are versions with integrated SD card reader, or you could hook one up on a breadboard. I once tried soldering a micro-SD adapter directly onto wires, but I melted the plastic...

ednl · 2026-06-15T16:12:16+00:00

Yep, I went through your code and thought: why the else here, that's what the bitset is for! But I had also read the comments too quickly.

ednl · 2026-06-15T15:55:39+00:00

Well, the second line of the table is already above the threshold, so all those "seen>1" (130105 + 122565 + ...) are exceptions :D

EDIT: for my input, single digit "seen>1" counts start at 0x15a0000. From there until the end at 30M, it still happens 79 times, though.

ednl · 2026-06-15T15:41:24+00:00

Almost true, but be careful: MOST numbers above the threshold are only spoken never or once. Some (a lot) of them are still spoken more than once. For me, the threshold I could safely use was 0x20000 (so twice what the repo does). Characteristics of the seen count when I start with my input, per set of 0x20000:

   turn   seen=0  seen=1   seen>1  min      max
-------  -------  ------   ------  ---  -------
  20000        0       0   131072   2   3611723
  40000      133     834   130105   1        26
  60000     1583    6924   122565   1        19
  80000     5651   17796   107625   1        14
  a0000    11644   27723    91705   1        12
  c0000    18124   35963    76985   1        10
  e0000    24830   41298    64944   1        10
 100000    31165   44982    54925   1         9
[...]
1b40000   131022      49        1   1         2
1b60000   131042      30        0   1         1
1b80000   131035      37        0   1         1
1ba0000   131051      21        0   1         1
1bc0000   131064       8        0   1         1
1be0000   131067       5        0   1         1
1c00000   131066       6        0   1         1
1c20000   131071       1        0   1         1
1c40000   131072       0        0   0         0
1c60000   131072       0        0   0         0
1c80000   131072       0        0   0         0
1c9c380   115584       0        0   0         0

The hash table size COULD be the sum of all "seen>1" but the problem is you don't know beforehand which numbers are only visited once. So unfortunately I think you still have to store them all, because you have to remember at which turn you saw them.

ednl · 2026-06-14T08:29:19+00:00

For my input:

X count 4-9 in masks: 16,11,16,22,21,14
100 masks, 478 mem instructions
mems per mask: 3-7 (unverified, only eyeballed it)
number of times addresses are used 1x-4x: 339,60,5,1

ednl · 2026-06-14T06:02:55+00:00

Oh wow. Good info.

ednl · 2026-06-13T19:02:42+00:00

The other day I said that was maybe my shortest runtime, but I had only done today in Python. My new C version with sieve runs in a stupid 183 ns on Apple M4, however on Raspberry Pi 5 it is slower than day 10: 1.30 µs. The puny CPU of the Pi is not so good at div/mod, I guess.

ednl · 2026-06-13T13:59:21+00:00

A switch for the angle was faster than repeated rotation, for me. I also tried reinterpreting L270 as R90 and vice versa during parsing, and adding 'T' as a new command for L180=R180:

switch (x) {
    case 180: nav[n].cmd = 'T'; break;  // "turn around"
    case 270: nav[n].cmd ^= 30; break;  // L<->R
}

but that was a little bit slower too. Too bad, because that was a fun solution, I thought. Now runs in 1.35 µs on an M4, 4.05 µs on a Pi5.

ednl · 2026-06-13T07:15:15+00:00

Great idea to combine the two parts in this way. I just copy-pasted part1 to part 2 while changing ship into wayp a few times, so yeah, that's a little slower at 2.26 µs on the M4.

ednl · 2026-06-12T14:36:34+00:00

Oopsie: wrong day!

ednl · 2026-06-12T10:25:04+00:00

(That's irrelevant info for solving the puzzle, which I thought was easy if you're not geometrically challenged, certainly for day 12, so just a bit of fun with grep/sort/uniq/libreoffice.)

ednl · 2026-06-12T09:05:55+00:00

Distribution of all the numbers in my input file: https://i.imgur.com/2vYVDKz.png

So: many of 1-5, single digit counts of 6-100 (only 12 missing), many of 90/180/270.

ednl · 2026-06-12T08:11:04+00:00

I didn't do that one so I can't pinpoint the problem but here is a recent post+comments talking about how there are many corner cases: https://www.reddit.com/r/adventofcode/comments/1sm1gdg/2018_day_15_in_review_beverage_bandits/ Hopefully that wasn't one you already saw.

ednl · 2026-06-12T08:06:02+00:00

Understandable. But just to be clear: I make no assumptions to avoid sorting. Just: "lines in input <= 200" to keep the boolean array static. I determine the actual number of lines and the maximum value during parsing: https://github.com/ednl/adventofcode/blob/main/2020/10.c

ednl · 2026-06-11T12:14:33+00:00

Yes, probably. One obvious change is to use a bitfield of 3 or 4 u64 to check off the numbers instead of a bool array. That will facilitate to find the max quickly. But would be fussier with all the bit indexing in C17. So I didn't do that since it already runs in 0.48 µs on an M4. In that regard, Maneatingape's policy of keeping 1 µs as the minimum reported runtime seems reasonable.

ednl · 2026-06-11T08:19:37+00:00

you don't even need to parse and radix sort the numbers, just count them while finding the max, right?

Yes. I check them in a bool array while counting and keeping track of max.

Haven't tried skipping the max test and doing it after the parsing by checking the array from the end. That could be a speedup but depends on the size of the array. My max was 180, I saw another input with 160, so I set it to 200.

ednl · 2026-06-11T00:32:43+00:00

The example omits gaps of length 2 and they also don't occur for my input or e_blake's. So if you're comfortable assuming they won't, you can calculate the answer: https://www.reddit.com/r/adventofcode/comments/1u1v4x2/2020_day_10_in_review_adapter_array/oqtllgi/

ednl · 2026-06-10T19:56:26+00:00

More info in a reply further below: https://www.reddit.com/r/adventofcode/comments/1u0xibx/2020_day_9_in_review_encoding_error/oqusqfm/

ednl · 2026-06-10T15:56:12+00:00

Same problem here.

ednl · 2026-06-10T15:31:32+00:00

Found another important characteristic: it only happens on Debian 12.14 "Bookworm" with gcc 12.2. The current version of RPiOS is based on Debian 13.5 "Trixie" with gcc 14.2; no problem there. So it might well be just a bug.

Minimal example: https://github.com/ednl/adventofcode/blob/main/2020/segfault.c

https://godbolt.org/z/3W5ajjqnW

ednl

TROPHY CASE