Today we're back in the jungle where the item-stealing monkeys are at it again. This time they've stolen The Historians' device, and to get it back we'll need a lot of money bananas. So we turn to the Monkey Exchange Market, where monkeys are buying good hiding spots, and our experience in the jungle means we have some to sell. We just need to know when to sell. And fortunately for us the monkeys use a fixed PRNG... a 24-bit XORshift.

The input is just an ordered list of over 2000 numbers to seed the PRNG. They run from about 160k to just short of 2²⁴. As is typical for problems using a PRNG, part 1 is just a test to verify that we've got the PRNG correct (iterate on each seed 2000 times and sum). I was happy to have this little break, this day was one where I was dealing with brain fog and feeling slow, and it took 15 minutes just to read the question. And so I just did the thing:

foreach my $num (@input) {
    for (my $i = 0; $i < 2000; $i++) {
        $num = (($num <<  6) ^ $num) & 0xffffff;
        $num = (($num >>  5) ^ $num) & 0xffffff;
        $num = (($num << 11) ^ $num) & 0xffffff;
    }
    $part1 += $num;
}

For the Smalltalk version I removed the unneeded 24-bit bitmask from the right shift. There it makes a difference because there's no special handling for expressions, it's all message passing. With the Perl, I left the copy-pasta in the part 1 script (I removed it for part 2).

With part 2 we get asked to use the generator. It turns out that the buy offers are only the ones digit of these secret numbers. We don't speak monkey to negotiate though, and so The Historian has found us a helper monkey to do that job. This monkey is capable of recognizing a single sequence of four consecutive changes in price and then selling for us. We can't change it between buyers, we need to pick the pattern that works the best across them all.

And my idea was just to build a hash of the "last four deltas" => "sum of last digits". So I coded that, but it returned 25 bananas for the test case instead of 23. So I needed to figure out how I was "cheating"... and the answer was that I forgot that the helper monkey isn't smart. He always takes the first match (not all, not best, just first). So I and invoked //= to set things only once. Resulting in this simple code in the loop to collect all values for the sequences of a buyer:

push( @window, ($num % 10) - $last );
$last = $num % 10;

if ($i >= 3) {
    $tmp{"@window"} //= $last;
    shift @window;
}

And then collecting those into our hash (of the amount for that sequence across all buyers) after the 2000 iterations are done:

$hash{$_} += $tmp{$_} foreach (keys %tmp);

And finally, the answer is just the best value in that after all seeds are processed:

say "Part 2: ", max values %hash;

I did do a dc version of part 1... it is quite slow (it was 90 minutes on the old hardware, but with the trick of preallocating constants in registers it gets to 30 minutes):

dc -f- -e'0s0 1s1 2s2 3s3 4s4 5s5 64sa32sb2048sc2000sd24se_1sf[l0d[l3Rl4Rl4~l3Rl4~l3Rdlfr^l3R*+l4dl3R+r%l4Rdl2r^l3R*l5R+rl2+dle>L]dsLxl3Rl4R++s.]s^[ld[rdla*l^xdlb/l^xdlc*l^xrl1-dl0<I]dsIx+lp+spzl0<M]dsMxlpp' <input

The difficulty here is that dc doesn't have bitwise XOR. That's what takes the time (I did do a version using my version of dc with embedded Perl (so I could just call out to that for the XOR)... that only took 90s to run). And most of the time I spent on this problem was experimenting with ways to do that dc to find a good one (there's an xor directory in this problem's directory of scripts and tests for this).

1-bit XOR is "add without carry" so that is simply +2%. It's also "absolute difference", and so -d* will work (again, this is only for 1-bit values)... and that's slightly faster. However the ultimate winner, that's in that code above, was this 2-bit XOR arithmetic function I found online: (a + b * (-1)^a ) % 4 looped 12 times. It's still a relatively simple function to code and execute and so it's a good balance. Trying for more bits, the function's going to get uglier... this is part of the reason why XOR is good for the PRNG.

So this is essentially a break day after the daunting problem of controlling a chain of robots. It is computationally heavy. If we had to do a tremendous amount of this, it might start to make sense to calculate and store the full cycle (it's only 24-bits) and work from that.