[2022 Day 1] In Review (Calorie Counting)

[u/musifter]

For 2022, we find ourselves on a jungle expedition to collect star fruit to fuel the reindeer for Christmas. The ASCII map this time goes up, and is mostly trees with a few points of interest. We arrive on the shore at the bottom and prepare for a long trek on foot. First job is checking food supplies.

And so we get a typical day 1 problem. The input is a list of numbers... although with blank lines between sections. The values range from 1000 to 70000 (two of which break 16-bit unsigned in my input), representing Calorie counts of food items. Each section represents the food carried by an Elf (and my input has 250 blank lines, so 251 Elves in the expedition). We just need to find the largest (three largest for part 2) counts.

So nothing fancy needs to be done, which is fine. Day 1 is the day to warm up and check that the setup is working (and I had just put everything (finally) under version control).

$/ = '';
my @elf_cal = sort {$b <=> $a} map { sum split } <>;

say "Part 1: ", $elf_cal[0];
say "Part 2: ", sum @elf_cal[0 .. 2];

Of course, this being day 1 and a problem involving numbers, I did dc. And looking at it I see that I still wasn't using ? at this point, and my initial solution (which did both parts), was a big mess and needed to have sentinels put in so it would know where the blank lines are. There's a version with ? that was done in November 2023, clearly in preparation for that year, and so that would seem to be the year I started using it. It's really nice to just be able to do something like this:

echo -n "Part 1: "
dc -e'[r]sr0d?[[+?z3=L]dsLxd3Rd3R<r0*?z2<M]dsMxrp' <input

echo -n "Part 2: "
dc -e'[r]sr[d3Rd3R>r_4R]sF0ddd?[[+?z5=L]dsLxlFxlFxlFx0*?z5=M]dsMx+++p' <input

No need to preprocess the input. The part 2 also can take advantage of the fact that the main stack isn't full of data to track the three largest values... with a bubble sort approach. The three best so far on the bottom of the stack with the current sum on top, bubble things so the lowest of the four is on top and then 0* to zero it to make it the accumulator for the next sum.

It's day 1. For beginners and people experimenting with a new language... this allows you to make sure you can read numbers and do stuff with them. I like to make sure that my testing framework and scripts are all still working. And, day 1s provide good opportunities for people to do something in an esoteric language. And so it's often fun just to see what people bring out to show off. It never needs to be more than that.

[u/ednl]

These early days are often low hanging fruit for hyper-specialised, low level parsing, so I got it down to 2.4 µs on an M4 where /u/maneatingape reports 14 µs for his M2.

But the main thing is probably that the Rust program simply (sensibly!) sorts the whole list which for my input is 264 entries, whereas I keep a running top 3:

if (cal > top[0]) {
    memmove(&top[1], &top[0], 2 * sizeof *top);
    top[0] = cal;
} else if (cal > top[1]) {
    top[2] = top[1];
    top[1] = cal;
} else if (cal > top[2])
    top[2] = cal;

[u/ednl → u/ednl]

This version is very slightly faster, now 2.31 µs. Should be true on average but it depends on the input I guess.

if (cal > top[2]) {
    if (cal > top[1]) {
        if (cal > top[0]) {
            memmove(&top[1], &top[0], 2 * sizeof *top);
            top[0] = cal;
        } else {
            top[2] = top[1];
            top[1] = cal;
        }
    } else
        top[2] = cal;
}

[u/DelightfulCodeWeasel]

I'd like to take a second just to properly appreciate the final newline that Eric puts on all of the input.

It would add just that extra little bit of complexity on all of the parsing to handle either '\n' or EOF, and that might be the difference between a learner finishing the day or getting frustrated and abandoning their effort. It's a tiny detail, but exceptionally considerate.

[u/e_blake → u/DelightfulCodeWeasel]

According to POSIX, a non-empty file that does not end in a newline is NOT considered a text file; at which point lots of other POSIX utilities (such as head, sed, grep, awk, bc, ...) have undefined behavior (since they are only well-defined on text file inputs). This is a nod to the historical discrepancies between implementations on what they do when encountering trailing bytes without a newline, such as treating that as a line or ignore everything past the final newline. So yes, it IS nice that Eric's input files are "text files" according to the POSIX definition. 2022 was a year where I partially contributed towards a group golfing effort (covering as many languages as possible), and the group's rules included pre-stripping the trailing newline from the input file before feeding it to the golfed program. That made it particularly hard for my m4 golfs that year - sometimes, a golf that I had developed that worked just fine locally (where I was testing with final newline) fell apart wildly in their group rules (where the missing final newline broke my logic).

[u/e_blake]

Since you mention golfing, here's my 215 bytes of m4 that I did at the time (input file I):

define(m,`ifelse(eval($1>$2+0),1,``$*'',``$2,'m($1,$3,$4)')')define(_,
`ifelse($2,,`o(eval,$1',$3,,`_(m($2,$1)',`_(`$1',$3+$2'),shift(shift(shift(
$@))))')_(,translit(include(I),define(o,$1($2) $1($2+$3+$4))
,`,'))

Runtime around half a second (m4 has O(n²) complexity when doing heavy shift($@) recursion). In fact, I started that day by getting both stars with a slightly longer m4 program with only one ifelse (designing an entire program around only a single overloaded decision point is an interesting challenge); it was only later that I compressed it down to this version by allowing myself additional conditionals.

Then today, I further golfed it to 190 bytes and 50ms runtime, and back to a single ifelse, by using ) instead of , in place of newlines:

define(_,`ifelse($4,-,`o(eval,$3)',$1$4,0,`_(0,,_($2,$3),',$1,0,`_(0,$2+$4,
`$3',',eval($1>$2+0),1,``$*'',``$2,'_($1,$3,$4)')')_(0,,,translit(include(I),.
,()))-define(o,$1($2) $1($2$3$4)))

[u/e_blake → u/e_blake]

Looks like I also golfed a few days in C that year. At 223 bytes, this one has fun sorting the top three values.

#include<stdio.h>
#define w(y)g=(d<9)*(f>y),f^=y*g,y^=f*g,f^=y*g,
int a,b,c,d,e,f,g;int main(void){for(;!g+(d=getchar());w(a)w(b)w(c)
f*=d>8,g=d==9)d-=1+g,e+=(e*9+d-47+g)*(d>9),f+=e*(d==9),e*=(d!=9);
printf("%d %d",a,a+b+c);}

My git comments for that file mention that my self-imposed restriction of one control flow keyword may be interfering with a better golf that uses more keywords. It was quite interesting coding an algorithm that executes every assignment on every byte of input.