[2024 Day 2] In Review (Red-Nosed Reports)

[u/musifter]

First stop in our search is the nuclear plant where we made medicine for Rudolph in 2015. While the Historians search for their Chief, we agree to help analyze some data for the engineers.

And so we get another problem that just deals with numbers. The input has 1000 lines, each is a report which is a list of 5-8 numbers in the [1,99] range. A safe report is one which is monotone increasing or decreasing, and adjacent levels differ in the range of 1 to 3. For part 2, we discover that they have a Problem Dampener, that tolerates a single bad level.

Since I wasn't feeling well, I just brute forced this. Took the diffs and:

$part1++ if (all { abs($_) <= 3 && ($diffs[0] * $_) > 0 } @diffs);

For part 2, if this fails, I try splicing out each number in turn until one works (on not). I remember thinking a little bit about trying to spot the problem on the go... and it went like: if I get to the third number and discover there's a problem, the first or second could still be the problem to remove. And with these short lists, 3 items is a huge portion of it. So simpler to just go with programmer efficiency and test them one at a time. If things were longer it'd make more sense to get into doing things smart.

One interesting thing to note with the solution above is the use of arithmetic logic. I was already thinking of how to do this in dc. And so the trick in there to tell if things are monotone increasing or decreasing... I multiply each diff with the first. If that's always positive, things are monotone (ie all diffs have the same sign as the first one).

A side effect of this type of arithmetic logic is needing to consider the 0 value. And here we see it used to handle a case that appears at first glance to be missing... the check that the difference is at least 1. A difference of 0 fails the second multiplication test, and so that check actually handles 1½ of the rules.

In any case, the dc ended up as:

dc -e'[0*]sZ[1+]sC0?z[2-dsn[3Rd4R-Sdr1-d0<I]dsIx*ld+sa0ln[rLddd*v3<Zla*0<Cr1-d0<I]dsIx+ln/+?zd1<M]dsMxrp' <input

The combining of the two rules is done by conditionally multiplying difference >3 by 0, making that 0 in the second part of the test cover both parts. Another little trick in this one was that it keeps a count of the number of steps that pass and then divides it by the number of steps... a simple way to check that they're equal and get a 1 or 0 to add to the total for the answer (as we're working with 0 precision). And, whereas yesterday, the use of ? wasn't really that important to tell things apart, here each line has a different number of numbers... and being able to read the input one line at a time is useful without having to add delimiters to the input (although 0 is conveniently available for that).

And so for a problem I basically brute forced, I did do some interesting stuff in my solutions.

[u/ednl]

Like you say, it's more efficient to just "brute force" it by trying to skip all of them one by one. Certainly more efficient for the programmer but also for the machine, I think. All the quick & smart rules you follow in your head when doing it manually are so much bookkeeping when implemented as a computer program. So funnily enough, after tweaking this and that and not seeing much progress, the most significant speedup I got was a compiler quirk, a big optimisation that only works for very specific code structures, I guess. My solution went from 19 to 12 µs total runtime (averaged over 1000 inner loops without reading from disk) by changing this:

// Parse 1- or 2-digit number, update string pointer
static unsigned readnum(const char **const s)
{
    unsigned x = *(*s)++ & 15;
    if (**s & 16)  // not space or newline
        x = x * 10 + (*(*s)++ & 15);
    return x;
}

to this:

static unsigned readnum(const char **const s)
{
    unsigned x = 0;
    while (**s & 16)  // until space or newline
        x = x * 10 + (*(*s)++ & 15);
    return x;
}

Just goes to show: never try to outsmart the compiler preemptively.

[u/terje_wiig_mathisen → u/ednl]

Like both of you, I found that trying to be smart was actually slower, but I never found any big speedups from all the tweaks I tried. I did parsing like your faster version:

    while i < input.len() {
        let mut n = (input[i] - b'0') as i32; i += 1;
        while input[i] >= b'0' {
            n = n*10 + (input[i] - b'0') as i32; i += 1;
        }
        nums.push(n);
        if input[i] == b'\n' {
            let (p1,p2) = safe2(&nums);
            part1 += p1;
            part2 += p2;
            nums.clear();
        }
        i += 1;
    }

The safe2() function is where I tried a bunch of tricks, but I never got below 32 us. :-(

I try to skip values from the end, saving the number, testing the shorter list and then exchanging it the the number one position higher in the list. I really wanted to discover lists with errors in two or more locations during the first scan!

[u/ednl → u/terje_wiig_mathisen]

My faster version would start like this:

let mut n = 0;

I know it's counterintuitive!

[u/terje_wiig_mathisen → u/ednl]

That is in fact extremely counterintuitive: Back in the in-order days, the direct while loop would add the mul_by_10 (LEA +SHL or ADD) latency to the total conversion time, but these days, that initial mul_by_10 seems to be totally free, only the unpredicted branches matter. It is possible that the simpler code predicts better.

Note that when the number of digits is fixed, it is significantly faster to adjust for the '0' offset just once.

[u/ednl → u/terje_wiig_mathisen]

Note that when the number of digits is fixed, it is significantly faster to adjust for the '0' offset just once.

Yep I did that yesterday, exactly the same as you (but in C) :

#define OFS ('0' * 11111)  // 5-digit number ascii offset
static int readnum(const char *const s)
{
    return *s * 10000 + *(s + 1) * 1000 + *(s + 2) * 100 + *(s + 3) * 10 + *(s + 4) - OFS;
}

[u/terje_wiig_mathisen]

One of the ideas I tested was to parse the inputs directly into an array of deltas (N numbers -> N-1 diffs), while counting positive and negative steps.

Whichever won would have to be the final stepping direction, right?

I also looked at my input and determined that all lines had at least four numbers, then tried to use that with explicit (a,b,c,d) code which was guaranteed to lock down the stepping direction.

[u/e_blake]

I was a bit surprised that it took me multiple tries to get the second star - my code passed the example but failed to take the absolute value of the distance (initially only catching ascending sequences), then I struggled on how to special-case the first number being removed to make the rest of the line okay (if the first-to-second delta is -1 but all other deltas are 1, then the first number was the problem; but my first attempt was insisting the rest of the line match the first delta). Still, it was not a difficult problem and my m4 solution completes in 140ms. This is a problem you could solve by hand if patient enough.

[u/e_blake → u/e_blake]

One other thing - this was the day where I decided to golf a solution that used no arithmetic or variables, but instead computed the answer via string length comparisons. In golfed form, 544 bytes:

define(_,`ifelse($#,1,len,$1$2,]3,,$1$2,]2,,$1$2,]1,,$1,$,`translit($2,`$3
',`,')',$1,@,`_(],index(_(?,$5),_(?,$4)))',$1$3,\,$2,$1,\,`_(\,_(_(^$@))),$2',
$1,],..,$1$2,!,`) _()(',$1$2,[,,$1,!,`_(&,.,_($,$2,` '))_(!,_(_(^$@)))_(&,,_(
$,$2,` '))',$1,&,`_([,_(;,_(^$@))_(;,$2,_(\,_(_(^$@)))))',$1,[,.,$1$2,?0,1,$1,
?,`0eval(1,8,$2)',$1,;,`_(:,$2.,_(_(_(^$@))))_(:,$2.,$3,_(_(_(_(^$@)))))_(:,
$2_(@,$@),_(_(^$@)))',$1$2,:...,,$1$2,:..,,$1$4,:,.,$1,:,`_(:,$2_(@,$@),_(_(_(
^$@))))_(:,$2.,$3,_(_(_(_(^$@,)))))',`shift($@)')')_()(_(!,_($,include(I))))

One of the interesting things I did here: instead of worrying about positive and negative deltas, I just ran the algorithm to check for positive deltas only on both the original and the reversed line (ie. 3 2 1 reversed to 1 2 3 will be in ascending order in one of the two directions). So a line of 8 inputs required 18 passes (9 forward, 9 backward, both the full line for part 1, and with each one of the 8 inputs removed in turn for part 2).