AoC - Day 19

:date: 2023-12-19 12:00

Part One

I'm quite proud of this one. I don't know what "normal" people do with this but it's basically saying, "Hey, whip up a custom programming language and give it this program!"

Uh... No thanks! Since I'm getting my C mojo back I realized that this syntax supplied in the puzzle input was just a few unix tricks away from actual compilable C!

This line of sed magic...

sed /^$/q $I|head -n-1|sed -e's/,/;/g' -e's/{/:/' -e's/;\([^};][^};]*\)}/; goto \1;/' -e's/\([xmas][<>][0-9][0-9]*\):\([^;][^;]*\)/ if (\1) goto \2/g'

Turns this puzzle input line...

px{a<2006:qkq,m>2090:A,rfg}

Into this valid C code...

px: if (a<2006) goto qkq; if (m>2090) goto A; goto rfg;

So I create this very simple C program that very creatively uses the #include preprocessor directive. It pulls in the code generated by the previous sed line.

[source,c]

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int x= atoi(argv[1]);
    int m= atoi(argv[2]);
    int a= atoi(argv[3]);
    int s= atoi(argv[4]);
goto in;
#include "19-input.c"
R:return 1;
A:printf("%d\n",x+m+a+s);
    return 0;
}

Note that this is a madhouse of goto statements. Who says they're bad? Not here!

Here's the test case working.

$ sed -n 's/{x=\([0-9][0-9]*\),m=\([0-9][0-9]*\),a=\([0-9][0-9]*\),s=\([0-9][0-9]*\)}/\1 \2 \3 \4/p' $I|while read N; do ./19 $N; done|awk '{X+=$1}END{print X}'
19114

And it worked on the full input taking only 363ms to finish.

Part Two

This was another one of those deals where you had to figure out how to burn your computer down or start going in and making actually sensible decisions based on ranges you could skip. I was too lazy for the latter and the former is just bad karma.

But here is a frightfully fast brute forcer if that's how you want to do it.

[source,c]

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    unsigned long long accepts= 0;
    for (int x=1;x<4001;x++) {
        for (int m=1;m<4001;m++) {
            for (int a=1;a<4001;a++) {
                for (int s=1;s<4001;s++) {
                    goto in;
                    #include "19-input.c"
                    A: accepts++;
                    R:continue;
            }   
        }
    }
    printf("%lld\n",accepts);
    return 0;
}

It will still take 40 days or so on my laptop. Maybe 10 if I broke it down into ranges to load all my processors. Maybe a full day of grinding on my work station. No thanks.

I did experiment with various compiler options. After all, isn't the kind of optimizing that this problem is looking for exactly what a compiler is supposed to be doing? Following this through was really to satisfy my curiosity about how good compiler optimizations were. I did use the opportunity to experiment with different optimization flags. For example....

gcc -O3 -march=native  -funroll-loops  -o 19b 19b.c

It turns out (for this problem) only the -O3 really mattered but it sure mattered! I took 3x longer with no optimization.

I used to tell people at the supercomputer center I worked at that perhaps they could save some watts by just compiling their programs more sensibly (or god forbid - using Fortran instead of Python/Perl in the first place), but for them, getting the NIH to buy new computers was easier than getting them to pay me a salary to write good code.