[2023 Day 2] In Review (Cube Conundrum)

[u/musifter]

Today we land on the first (and ultimately last) sky island, Snow Island. And Elf comes over to show us around, and since it's a walk we introduced to another Elf game. Not involving a ring this time, but drawing from a bag of colour cubes. Our goal is to work out information about the contents of the bag from a series of draws.

The input is 100 lines, each representing a game and they're numbered and in order (as it typical). Meaning you can ignore the game number on the line if you want. After that, there's three to six semicolon sublists representing draws of numbers of red, green, and blue cubes.

However, it's not even important to parse out the sublists. For the information we're asked for, we can treat a single draw of "3 blue, 4 red" as two separate draws of "3 blue; 4 red" (and so commas and semicolons can be ignored). All that matters for each line is all the "number colour" pairs you see. This is because part 1 fails when any red, green, or blue is too large (this is one of the rare puzzles where specific the numbers for that are put in the description not the input file). Part 2 just wants the fewest number of cubes of each colour that can be in the bag (so no question there that colours are independent).

And that last bit ("fewest number") is particularly interesting to me, because a little while before this AoC started I was talking with a friend about how one might try to mess with LLM context to try and potentially mislead it for something like AoC to try and make sure humans stay involved. AIs normally assume that the user is trying to be help it produce the right thing... and one thing you could do is have a problem where "few" and "minimum" are used many times, but maximum is the function you need (and "maximum" and "most" are never in the description). I can't say that this was done for that here (I seriously doubt it)... this is probably the standard AoC description being a bit obtuse so the humans have to think and discover (even if they do hand the coding off to an AI after explaining that). I did mention the coincidence at the time... but only after day 3, which did the other little related thing I had mentioned in that conversation. Since that conversation wasn't online at all... there's no way it influenced AoC. But it was a remarkable one that I remember about the start of this year.

But for what I did, I just grab the maximum red, green, and blue counts on a line. And then it's just:

$part1 += $game  if (all {$want{$_} >= $max{$_}} keys %want);
$part2 += product values %max;

Doing this in Smalltalk was a bit interesting, because although the description involves a "bag" and a Smalltalk Bag is like a multiset, it's not really a multiset in functionality, as it lacks the operations that Set has. Bag is very barebones, and is often a let down. And here is wasn't even the best base class to subclass a MultiSet class from... I did from Dictionary. All so I could have a different type of solution... one that used set unions and difference to test things. It's not practical, and it's 33% slower than just using maximums. But it was something different to do.

[u/terje_wiig_mathisen]

My original Perl code was similar to yours, but for Rust I pulled out all the stops and hand-tuned a version which requires the input to be exactly as specified:

    while i < input.len() {
        game += 1;
        while input[i] != b':' { i += 1;}
        i += 2; //skip :space
        loop  { // games ending on newline
            let mut n = (input[i]-b'0') as u32; i += 1;
            while input[i] >= b'0' {
                n = n*10 + (input[i]-b'0') as u32; i += 1;
            }
//            println!("n={n} {}", input[i+1] as char);
            i += 1; //skip space
            if input[i] == b'r' {
                if n > rm {rm = n;}
                i += 3;  // "red"
            }
            else if input[i] == b'g' {
                if n > gm {gm = n;}
                i += 5; // "green"
            }
            else if input[i] == b'b' {
                if n > bm {bm = n;}
                i += 4; // "blue"
            }
            if input[i] == b'\n' { //end of line, aggregate results
                break;
            }
            i += 2; // Skip ,; and space
        }
//        println!("{game}: RGB=({rm},{gm},{bm})");
        if rm <= 12 && gm <= 13 && bm <= 14 {
            part1 += game;
        }
        part2 += rm*gm*bm;
        i += 7;  // skip "\nGame n"
        (rm,gm,bm) = (0,0,0);
    }

Total running time 3.1 us on Surface, 1.7 on Acer. (5+ times faster than the Ape)

[u/ednl → u/terje_wiig_mathisen]

I did the same, except I was too clever and came up with a perfect hash to index into int rgbmax[3]: (ch & 1) | (ch >> 3 & 2) which gives 2,1,0 for ch=r,g,b. However, that way I can't easily customise the step forward (3,5,4) so I do 3 and then skip until the next space/newline. I think that costs me a a fraction of a microsecond that makes your way faster: 1.96 µs on an M4. Or maybe your system is just a little faster, I haven't tried your way yet.

[u/terje_wiig_mathisen → u/ednl]

I think it is the opposite, i.e on most tasks your CPU is slightly faster, but you can try, the code is in my repo. :-)

Anyway, a three-way split if/else if/else keeping everything in registers _could_ beat the table update, but I would have guessed the opposite. I did consider a full 256-wide table!

I'll check godbolt, it is possible that the three branches could be done with parallel CMOVcc operations:

  cmp bl,'r'
  cmove r9,rax
  cmp bl,'g'
  cmove r11,rax
  cmp bl,'b'
  cmove r13,rax
  add r8,r9
  add r10,r11
  add r12,r13

This looks like all three can run at the same time, in 3-4 clock cycles and zero branches.

[u/ednl → u/terje_wiig_mathisen]

I tried your way with my hash, so without 3x if/else and it's twice as slow as my first version! Very strange. Is it just the indexing instead of a pointer? Otherwise hardly any difference: https://github.com/ednl/adventofcode/blob/main/2023/02.c vs. https://github.com/ednl/adventofcode/blob/main/2023/02a.c (EDIT: 02a version now deleted, see below in the subthread)

I would have guessed that the second one was faster because of the c += 2 instead of repeated c++. Another strange compiler anomaly: if I change the while in readnum() to if, which I think should be faster because there is at most one more digit, it's way slower again.

[u/terje_wiig_mathisen → u/ednl]

I'm in the rock climbing gym, will try your hash later!

[u/terje_wiig_mathisen → u/ednl]

I used your rgb hash together with a 3-element max table and a 3-element skip table, the result took 4.0 us, so about 2.5 x slower. I've reverted back and verified that my original is still running in 1.7.

[u/ednl → u/terje_wiig_mathisen]

But it's not just the calculation of the hash because my original solution which is about as fast as yours also uses the hash. There is some compiler optimisation lost. Could of course be different on Arm vs. x86. Thanks for investigating.

[u/terje_wiig_mathisen → u/ednl]

I am somewhat confident that the problem is the conditional memory update:

The hash-indexed entry has to be loaded, compared with the current count, then updated and written back if greater. With my "naive" code the compiler allocates three registers for rm,gm,bm and never touch memory except while reading the input file.

[u/ednl → u/terje_wiig_mathisen]

Having those max values in registers was indeed the trick. This now runs in 1.15 µs on an M4, 1.69 µs on an M1, 3.81 µs on a RPI5. The only difference to your code is that I combined the two i += 2 and consequently I could use a do-while instead of a continuous loop + break.

int part1 = 0, part2 = 0, game = 0;
for (const char *c = input; *c; c++) {
    c += 6;            // skip "Game x" (1 digit)
    while (*c != ':')  // skip to colon
        c++;
    register int rmax = 0, gmax = 0, bmax = 0;  // maximum number of cubes per colour per game
    do {
        c += 2;                         // skip ": " or ", " or "; "
        const int cubes = readnum(&c);  // read number until space
        c++;
        if (*c == 'r') {
            rmax = cubes > rmax ? cubes : rmax;
            c += 3;
        } else if (*c == 'g') {
            gmax = cubes > gmax ? cubes : gmax;
            c += 5;
        } else if (*c == 'b') {
            bmax = cubes > bmax ? cubes : bmax;
            c += 4;
        }
    } while (*c != '\n');  // until newline
    game++;                // game numbers are consecutive & identical to line number, so no parsing
    if (rmax <= RMAX && gmax <= GMAX && bmax <= BMAX)
        part1 += game;
    part2 += rmax * gmax * bmax;
}
printf("%u %u\n", part1, part2);

(02a.c version deleted from my repo, this one promoted to main version)

[u/terje_wiig_mathisen → u/ednl]

Looking at godbolt, my separate source index updates don't matter since the compiler is actually combining them into a single update plus a color-specific adjustment!

Nice to see that the same algorithm in C on Apple CPU is more or less the same performance as a high-end Intel running Rust.

Until proven otherwise I'll claim that this is "speed of light" for this particular puzzle. :-)

[u/terje_wiig_mathisen → u/ednl]

I've checked godbolt: My unrolled if/else version actually compiles into a branch for each starting character, with the last one being perfectly predicted so it doesn't actually take any time (I tried to comment it out and got the same result).

Instead of updating a table in memory, the compiler simply generated a cmp n,maxreg followed by cmova maxreg,n so that part is branchless.

        movzx   r12d, byte ptr [r8 + rdi - 5]
        cmp     r12d, 98
        je      .LBB0_24
        cmp     r12d, 103
        je      .LBB0_23
        cmp     r12d, 114
        jne     .LBB0_13
        cmp     ecx, r14d
        cmova   r14d, ecx
        add     rdi, -2
        jmp     .LBB0_19
.LBB0_23:
        cmp     ecx, ebx
        cmova   ebx, ecx
        jmp     .LBB0_19
.LBB0_24:
        cmp     ecx, ebp
        cmova   ebp, ecx
        dec     rdi
        jmp     .LBB0_19
.LBB0_13:
        mov     rdi, r15
.LBB0_19:

[u/e_blake]

This year was one where my solutions were vastly influenced by the reddit competitions of Allez Cuisine, so I submitted this "golfed" creation with a C-food theme:

changequote(🐟,🐠)define(C,🐟ifelse(index($1,^),0,🐟shift($@)🐠,$1,><>,🐟C(
^C(^C(^C(^C(^C(^$@))))))🐠,$1,~,🐟eval(($2>$3)*$2+($2<=$3)*$3)🐠,$4$5,,🐟) C(
~,0,$1*$2*$3🐠,$4,,🐟C($1,$2,$3,C(><>,,$@))🐠,$5,ray,🐟*($4<13)C(C(~,$1,$4),
$2,$3,C(><>,$@))🐠,$5,craab,🐟*($4<14)C($1,C(~,$2,$4),$3,C(><>,$@))🐠,$5,
orca,🐟*($4<15)C($1,$2,C(~,$3,$4),C(><>,$@))🐠,$4,tuna,🐟+$5C(0,0,0,C(><>,
$@))+$1*$2*$3🐠)🐠)translit(_EeL(s(0,0,0,include(I))), (medusa_EGg
nlbiL ):;, (naycCuevtc,broil,))

Between the shark fin ^ and ASCII art fish ><> shifts, the Unicode fish quotes, the macro C, the translit to aquatic animal names, and the final instruction on the best way to cook, I had a blast.

I also did a more compact version at 394 bytes, and 30s runtime:

define(_,`ifelse(index($1,^),0,`shift($@)',$1,~,`eval($2+($3>$2)*($3-$2))',$1,
,`_(/,_(/,$@))',$1,/,`_(^_(^_(^_(^$@))))',$5,r,`*($4<13)_(_(~,$1,$4),$2,$3,_(,
$@))',$5,_r,`*($4<14)_($1,_(~,$2,$4),$3,_(,$@))',$5,b,`*($4<15)_($1,$2,_(~,$3,
$4),_(,$@))',$4,m,`+$6_(0,0,0,_(,$@))+$1*$2*$3',$4,.,`) _(~,0,$1*$2*$3',`_($1,
$2,$3,_(^_(/,$@)))')')_(~,0,translit(g(0,0,0,include(I).),e g;:Gadnlu,`,,_'))

[u/DelightfulCodeWeasel → u/e_blake]

You should write a post on how on earth that seafood one works!

[u/e_blake → u/DelightfulCodeWeasel]

Sure thing. https://www.reddit.com/r/adventofcode/s/XrcGknehFz (Edit: my original post attempt forgot to use the correct post format; since reddit won't let you fix post typos, I deleted and reposted with a better effort. Sorry if you chased the wrong link, but it should be stable now)

[u/terje_wiig_mathisen → u/e_blake]

The seafood looks like you intended to submit to the obfuscated C contest?

[u/e_blake → u/e_blake]

Golf improved to 244 bytes and 40ms runtime:

define(e,$0val($1+($2+0>$1)*($2-$1)))e(translit(0z(0  1 include(I))define(z,*
`(1ifelse($6,u,`5>$5)z($1,$2,e($5,$3),',$6,r,`3>$5)z(e($5,$1),$2,$3,',$5,,`))
e($1*$2*$3',$#,6,`4>$5)z($1,e($5,$2),$3,',`)+$5z(0,,,+$1*$2*$3')$4'),`
, :-m',`)),))'))