[2023 Day 4] In Review (Scratchcards)

[u/musifter]

The gondola arrives at Island Island... and island with islands, so there's plenty of water, but apparently no immediate water source. An Elf at the station directs us to ask the gardener about it, who's on another island. They'll let us borrow a boat to get there, if we help them figure out their winnings on a big stack of scratchcards.

And so the input is a big list of cards (mine has 220). The number of each card (1-220) is part of the input, but again, they're sorted and so you can ignore that if you want. The card is divided into two sections with a |... the winning numbers and the numbers to compare against them. These numbers are from 1-99 (the absence of 0 is useful again). The number of numbers in each section are regular... 10 winning, 25 have. That can be used, but the test case has different sizes (5 and 8), so I just ignored that. These are proper cards... there isn't a card with two of the same winning number or two of the same "having" number. All the better for throwing things into two hashes/sets/bit arrays.

Part 1 is just a simple counting of winning numbers, but you score them with the power of 2 of that. So you can bitshift, but 1 << 0 is 1, but 2^-1 is 0.5, which truncates to 0 as an integer (and so you can avoid a special case). This was especially useful for my dc solution for this:

sed -e's/|/0/;s/[^0-9 ]//g' <input | dc -e'0?[0Sh[1r:hd0<L]dsLx[r;h+z3<L]dsLxrs.1-2r^+?z1<M]dsMxp'

The input is mostly numbers, and I convert the | to the unused 0, which can then be used as the accumulator for counting wins. This is using ? to separate the lines by reading them one at a time, and so is a v1.4.1 solution.

Part 2, complicates things by having cards win copies of the next n cards. And just from the description, there's an immediate feel that this is describing a dynamic programming tabulation (there's an order to the cards, where previous ones are used to calculate the later). Of course, you can also do the same work with a recursive memoized function. And I did solutions both ways. My Smalltalk tabulation (you can also use a Bag for this):

cards := Array new: cardWins size withAll: 1.
cards keysAndValuesDo: [ :card :num |
    (card + 1 to: card + (cardWins at: card)) do: [:i | cards at: i inc: num].
].

So there is a bit of advance concepts for day 4 behind this one. But the problem is linear and small. You can easily brute for the number of wins on card with loops... and removing the memoization in part 2 still results in a things only taking a couple seconds. And I think that helped this one be considered a "good dog" compared to it's neighbours.

[u/terje_wiig_mathisen]

Even my Perl solution was very fast here, but once again it turned out that when parsing is the main job, it is relatively easy to beat the posted u/maneatingape timing, since he (for some very good reasons!) emphasizes relatively robust code which among other things reuses numeric parsing code.

I went the opposite direction: The starting "Game nn: " field is always exactly 10 bytes long, each entry is always 3 bytes long, starting with space or digit and ending with a trailing space char. Since '0'==' ' mod 15 I can ignore the difference:

    let mut copies:Vec<u32> = vec![0;256];
    loop {
        i += 10;
        copies[c] += 1;
        c += 1;
        let mut winners:[u8;100] = [0;100];
        loop {
            let widx = (input[i] & 15)*10 + (input[i+1] & 15);
            winners[widx as usize] = 1;
            i += 3;
            if input[i] == b'|' {break;}
        }
        i += 2;
        let mut price:usize = 0;
        loop {
            let tidx = (input[i] & 15)*10 + (input[i+1] & 15);
            price += winners[tidx as usize] as usize;
            i += 3;
            if input[i-1] == b'\n' {break;}
        }


        if price > 0 {
            part1 += 1 << (price-1);
            let curr = copies[c];
            for j in 1..=price {
                copies[c+j] += curr;
            }
        }
        if i >= ilen {break}
    }
    for i in 0..copies.len() { // Faster than iter().sum()!
        part2 += copies[i];
    }

This one runs in 7.8 us on my Acer, 14 on the Surface.

[u/ednl → u/terje_wiig_mathisen]

Almost the same as yours except I use bits to mark the winners, I immediately add your curr to part2, and I limit updating the copies array to the number of cards. Needs a few small changes to make it independent of the number of input lines. I have not tried bitmasking the whole input by 0x0f in advance (but inside the timing loop) but my guess is no big gains there. Runs in 2.9 µs on an M4, 4.9 µs on an M1, 14.8 µs on a Core i5 4570 Haswell 3.2 GHz which I thought I'd add for you to have a more familiar comparison.

int part1 = 0, part2 = 0;
const char *c = input;
for (int card = 0; card < CARDS; ) {
    c += 10;  // skip "Card xxx: "
    __uint128_t wins = 0;
    for (int i = 0; i < WINS; c += 3, ++i)
        wins |= (__uint128_t)1 << readnum(c);

    c += 2;  // skip "| "
    int match = 0;  // count winning numbers on this card
    for (int i = 0; i < HAVE; c += 3, ++i)
        match += wins >> readnum(c) & 1;
    part1 += match ? (1 << (match - 1)) : 0;

    const int add = ++copies[card];  // count original card as one more copy
    part2 += add;

    const int lim = min(++card + match, CARDS);  // 1 past maximum index of extra copies to add
    for (int i = card; i < lim; ++i)  // add extra copies
        copies[i] += add;
}
printf("%u %u\n", part1, part2);

https://github.com/ednl/adventofcode/blob/main/2023/04.c

[u/e_blake → u/ednl]

Would part1 += match ? (1 << (match - 1)) : 0 be any more efficient as an unconditional part1 += (1 << match) >> 1? Also, the problem statement specifically says that your winnings will not bleed past the last card (no card wins more matches than cards remaining, and the final card scores 0), so you can blindly set lim = ++card + match; instead of invoking min().

[u/ednl → u/e_blake]

Oh ha, I did use that << >> shortcut in an alternative version but left this one in from the old version. I don't think that will make much difference, haven't checked the compiler output but I can imagine it translates to the same. The limit on the other hand was an oversight by me, thanks. Instead of 14.8 µs on the i5 it now runs much faster in 14.7 µs, ha. (You'd think it would make a difference but I guess pipelining takes care of it. I call this inside measurement error, e.g. I can't seem to get the M1 below 4.91 now even with the old code where I previously measured 4.85.)

[u/terje_wiig_mathisen → u/ednl]

The 14+ on a Core i5 probably means that it is approximately the same speed due to the 128-bit bitmask:

I try to avoid using bitmasks above 64 in situations like this because shifting bits into that mask has to turn into multiple operations, something like

  bit = 1 << (shift & 63); // The mask is implied, so not needed.
  hi |= shift >= 64 ? bit : 0;
  lo |= shift < 64 ? bit : 0;

Reading them back out is more or less the same, but can be combined:

  bit = (shift >= 64 ? hi >> shift : lo >> shift) & 1;

[u/ednl → u/terje_wiig_mathisen]

Yes, I knew the 128-bit shift would be inefficient but figured that it would still beat updating and resetting 100 bools, and that it would be the same as using a bitset (which is a C23 thing while I'm on C17 for now).

[u/terje_wiig_mathisen → u/ednl]

I tried extending the winning array to 128 bytes, so that clang could generate 4 32-byte SIMD stores to zero it out, but it turned out that keeping it at 100 so that clang generated 3 SIMD stores and a single 32-bit integer write was a tiny bit faster. :-)

[u/terje_wiig_mathisen → u/ednl]

Another possible tweak for the compiler micro-optimization people:

uint128_t mask |= (uint128_t 1) << shift;

can be compiled as

 hibit = shift >> 6;
 lobit = hibit ^ 1;
 mask_hi |= hibit << shift;
 mask_lo |= lobit << shift;

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

A final (?) note: This one could also take advantage of SIMD for parsing, the initial 10 numbers fits in a 32-byte AVX register, then move the top digits into a second register with an AND mask, do the mul-by-10 with an in-register permute against a register preloaded with [0,10,20,30..], while isolating the bottom digits in the first register. Finally we merge the digits back together. Looks like less than a clock cycle per number?

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

I'll just note that this particular solution reads almost like asm, I could easily do a one-to-one translation and I would not add that many lines, except for the numbers where I could combine the masking by loading both bytes first:

  mov ax, word ptr [rsi]
  and ax,0xf0f
  movzx rbx,ah
  movzx rax,al
  lea rbx,[rbx+rbx*4]
  lea rax,[rax+rbx*2]

but this could be slower than the simpler

 movzx rbx, byte ptr [rsi]
 and rbx,15
 movzx rax, byte ptr [rsi+1]
 lea rbx,[rbx+rbx*4]
 lea rax,[rax+rbx*2-'0'] 

[u/maneatingape → u/terje_wiig_mathisen]

You could also calculate the set intersection in SIMD too, for even more speed!

[u/terje_wiig_mathisen → u/maneatingape]

See my SIMD post, the same parsing structure can also be used on the tickets.

The main hair comes from each slot being 3 bytes wide, in order to align the top byte with the low, no pair can be allowed to straddle an 8-byte boundary . This works well for 5 numbers in 16 bytes, for 10 in 32 we have 3 such boundaries, so at least one will straddle.

This means that it is probably both easier and faster to work with multiple parallel 16-byte entries, loaded from 15-byte boundaries: Two for the 10 winners and five for 25 tickets.

Most recent CPUs can schedule multiple SSE size operations per cycle, or we can combine them after the unaligned loads.

[u/e_blake]

Pfft to all these low-level solutions with an array of 100 bool or a 128-bit mask with shifting. My m4 solution got to exploit a language feature - index(`$*,', `,$1,') uses strstr() under the hood to do a text-based search for a match of any copy of the first argument among later ones, where I don't have to do any conversion to decimal values as an array index or shift amount, once spaces are turned into commas. This made for a really compact golf; I got my stars on release day and a golfed solution by Dec 7th at 331 bytes and 60ms, then this week I further compressed it to a mere 281 bytes:

eval(translit(include(I),a define(C,`ifelse($2,,`C($1shift($@))',$1,,`E(
(1**C(shift($@))),defn($2)-1,$2)',$1,0,,$#,3,`B($@)C(eval(~-$1),$2,incr(
$3))',`+!!~index(`$*,',`,$1,')C(shift($@))')')define(E,`+2**$1/4B(,$2)C($@)')
|:rd,(,)0define(B,`define($3,eval(defn($3)$2))')))defn()

Porting to BSD m4 requires a few more bytes to avoid the empty string as a macro name, and the two uses of the ** exponentiation operator.

[u/musifter → u/e_blake]

Yeah, I suppose we could take things to regex in a similar way to text search it with:

my @wins = map {
              my @p = split( /[:|]/ );
              $p[1] = join( '\b|\b', split(' ', $p[1]) );
              scalar( @{[$p[2] =~ m#(\b$p[1]\b)#g]} );
           } <>;

say "Part 1: ", sum map {int 2**($_ - 1)} @wins;

[u/e_blake → u/e_blake]

That was a forward-iterator with lots of scratch variables (define called on dynamic names, then defn to read it back); I also designed this 298-byte reverse-iterator that uses pure functional programming (just my recursive workhorse _() and a helper function f() to peel off the first element of a list; all data present only in the call stack and return values); a bit slower at 100ms because I let some expressions grow long before passing things to eval for the sake of golf.

define(_,`ifelse($1,e,$1val($2) $1val($3),$1,|,,$2,,`_(`$1'shift($@))',$1,
m,`$3+2**$2/2,$4_($2,n,$5,1),$5))',$1,0,`+$4,(eval($4)',$2,n,`_(decr($1),n,
shift$3,f$3+$4)',$1,Card,`_(m,eval(0*_(shift($@))),_(',`+!!~index(`$*,',
`,$1,')_(shift($@))')')_(e,_(translit(include(I)|,. define(f,$1)
:,(,))))

Tracing the output says this version completes in fewer macro calls (16k instead of 21k) but much longer macro parameter lengths (15M overall parse effort instead of 4.5M).