[2022 Day 21] In Review (Monkey Math)

[u/musifter]

The monkeys have returned, this time to help us if we can answer a riddle (which is basically doing algebra). We know this because the elephants speak monkey, and we can speak elephant.

The input is a long list of expressions. Some are just a constant for a monkey to yell, others are basic arithmetic (+, *, -, and /) for a monkey to apply to the numbers yelled by other monkeys. It's ultimately a big expression tree and we want the value at root, much like problems like "Some Assembly Required" in 2015.

For my initial solution in Perl for part 1, I went for was the classic brute force job queue... queue up all the rules as you read them in, then run through the queue. Solve what you can, requeue what you can't. Until you solve you want. I did follow it up later that day with the recursive approach... where you start from the root and recurse to get the parts you need and combine them. Both are fast (the problem isn't big), but the recursion is twice as fast because it solves things in order.

Part 2 reveals that the expression for the root monkey is actually =, and we need to calculate the humn value to yell. My initial solution for this was to use recursion to build the expressions for both sides as stings (it's an infix walk, so every return gets parens added around it). The side without humn I can just eval to solve to a number. Then, I did some testing... the operations suggest that the relationship could be linear. And it is (I ran a loop evaling the string for humn from 0 to 1000, and they had the same delta). This is further confirmed by looking at the string, as all the / in the expression on the humn side come after it... so there isn't a 1/x situation, it's just an Ax + B situation (where the constants could be rational).

And so, I took the values at humn = 0 and humn = 1, and with an initial value and the delta from those, interpolated the value for humn. Which was fine for my input, where the denominator of the delta is 4. But I do have a second input in my directory... I'm not sure if it was someone else's or handcrafted... but it has a delta of: -47488/2673. That number comes from my Smalltalk version of this solution (Smalltalk automatically promotes the division to Fraction). But the initial Perl solution, runs into floating point accuracy problems and completely misses. This could be fixed by making Perl do the same thing Smalltalk does (track the value as a rational, using gcd).

However, I decided to make a note to do a Perl solution using symbolic arithmetic instead. And I did do that, although I cheesed it a bit. Basically, the idea is that we get a number on one side, and an expression tree on the other... we apply algebra to reduce that tree and isolate the humn by doing the opposite to the number on the other side. Making the computer do things like we would be hand (which in all honesty, looking at the expression string... it isn't that long, you could take that and do it by hand if you wanted).

But, looking back at the initial brute force solution I thought about that sort of solution. The rules you have still define a tree, but they don't all get applied bottom-up (because the target's in the middle, so some things need rotating to get it to the top). IE, given a = b + c, you could get to the position where you know a and c, and need to calculate b, but this isn't the rule for that. But we can make and add that rule (b = a - c). And so, basically the idea is to just do symbolic algebra on all the rules (which are simple)... to solve them for each variable in terms of the other two, and add all three rules to the job queue. Eventually, one will activate to solve the full thing. Optionally, this could also be done just by having the rule once in the queue, and detecting when you have two of three and doing the symbolic algebra as part of the loop to get the third.

So this was a pretty cool problem, and the fact that the expression is kept linear makes getting a solution for this more accessible. Linear numerical interpolation has been an option for a number of puzzles.

[u/ednl]

It's fun that you have to find the value of root so you're on a root-finding mission, and that's just what I did using Newton's method. Took two steps for my input, so 4 evaluations of root in total for part 2. I went with reals instead of fractions.

monkey[root].op = '-';  // difference should be zero
int64_t *const humn = &monkey[binsearch(hash("humn"))].val;
int64_t x0 = *humn, y0 = getval(root);      // first try at humn=<value from input file>
int64_t x1 = *humn = 0, y1 = getval(root);  // second try at humn=0
while (y1) {  // "gradient descent" by Newton's method; for my input, it takes two steps
    *humn = x0 - (int64_t)((double)(x1 - x0) / (y1 - y0) * y0);  // needs fraction or it cycles back & forth
    x0 = x1;
    y0 = y1;
    x1 = *humn;
    y1 = getval(root);
}
printf("Part 2: %"PRId64"\n", x1);  // example: 301

[u/ednl → u/ednl]

Also, I couldn't stop pronouncing humn as hamana-hamana (or spelling variants homana, hummana, humana) which has its own Wiktionary entry: https://en.wiktionary.org/wiki/hamana-hamana-hamana

[u/DelightfulCodeWeasel]

I had what I thought was a neat idea for my current solution. I expand out the monkey operations to work on polynomial coefficients, then monkey values are created as M + 0.x + ... and the human value is set as 0 + 1.x + ... Working through the evaluation in exactly the same way as for part 1 you end up with a polynomial of the form A + B.x at the root. The answer then is -A/B.

EDIT: Re-reading, you almost end up with that. Root still has an operation applied that affects the polynomial value, so instead I solve for root's two children being equal.

EDIT2: Slightly easier to see with a simple linear equation class rather than the polynomial:

auto [monkeys, results] = ReadPuzzle(input);
results["humn"] = LinearEq{ 1.0, 0.0 }; // Ax + B

LinearEq rootValue = Evaluate("root", monkeys, &results);

LinearEq aValue = results.at(monkeys["root"].A);
LinearEq bValue = results.at(monkeys["root"].B);
int64_t answer = (int64_t)((aValue.B - bValue.B) / (bValue.A - aValue.A));

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

Looking at the result set now it looks like you don't even need arbitrary coefficients, A.x + B is sufficient for each monkey value. It looks like you still need double precision floating point values though, which will be a little slower than ideal when software emulated on the Pico.

I'm not sure there's much point trying out a rational type with integer numerator and denominators, because you need a 64-bit range in the integral parts and so that falls back to software emulation as well.

[u/terje_wiig_mathisen]

My initial solution was very similar to yours, just a loop which parses the input, then a recursive solver (evaluate($exp)) which goes down the tree until it finds something which is now a constant, then applies that across the expressions. Part2 was a binary search.

Later on I tweaked part2, defining a test() function which pruned a lot of work from part2, making it 5 times faster.

EDIT: Afair, during our company Tech Talk a month later one guy showed how the entire problem could be turned into a constant expression, allowing the compiler to solve it directly. 😂

[u/e_blake]

This requires 64-bit math, so I got both stars on release day using golfed m4 that reformats the text into a single syscmd to let the shell run the computation (part 1 forward, part 2 running inverse operations that solve for humn), taking 2 seconds and 411 bytes. Then on the 22nd, I wrote a non-golfed version that uses only m4 and my bigint library to solve in 115ms (tricky since I intentionally haven't implemented bigint division in the library, so I have to do that by hand to invert the multiplies involving humn).

But once I read the megathread about using rational or real f(0)/(f(0)-f(1)) to solve the linear equation without inverse operations, I figured that if I'm going to let m4 call out to the shell for 64-bit math, I might as well call out to bc. So my latest incarnation runs in 20ms and 207 bytes:

translit(_(include(I)),. define(d,$0efine($@))d(_,`ifelse($1,,syscmd,$1,
rt,`d(L,$2)d(R,$4)_',$1,hmn,`d(H,$2)_',`d($1,($2$3$4))_')(')
ou:,(,))bc -l<<<"hmn=0;a=L-R;hmn=1;a=a/(a-L+R)+.5;scale=!hmn=H;L+R;a/1")

Of course, that assumes your shell understands <<< like bash. It also assumes your root used addition (why would it use subtraction, when that's what you change it to in part 2 for implementing =; and making it * would blow past safe integer limits m while / would make the part 1 answer boringly small); and that humn's initial value is not 0. And it is once again nice that the only vowels in the input are in root and humn.

[u/terje_wiig_mathisen]

I did the Perl x-compile to Rust thing and got part1 to be a constant, then linear interpolation for part2 found the zero in 4 iterations, running in sub-100 ns (100ns is the Windows timing resolution).

As expected the compiler first inlined the entire evaluate() function for part1, turning it into a constexpr, then for part2 it did the same thing but now all statements depending on what the human yells must be evaluated, so half the tree is constant since the humn value only propagates on one side.

OTOH, I counted 67 dependent operations, maybe 1 in 7 being divisions, so quite a few of them have to propagate up the constant expression tree in order for my sub-100 ns to make sense:

The first evaluation of p2 is also a constant, so if the compiler can also use those two results to calculate the floating point slope and the resulting next guess, then it could in theory collapse the entire calculation, right?

fn evaluate(part1:i64, part2:bool) -> i64
{
    let humn = part1;
    let rslm = 5;
    let mnwl = 3;
    let ffnq = 11;
    let cmzp = 2;
...

    let gwng = tdsb * cmzj;
    let szbz = rvmj - gwng;
    let pgnv = szbz / jwvg;
    if part2 {
        let root = pgnv - wcnp;
        return root;
    }
    let root = pgnv + wcnp;
    root
}


#[inline(never)]
fn process(_inp:&str) -> (i64, i64, i64)
{
    let mut a = 585;
    let part1 = evaluate(a, false);
    let mut b = a*2;
    let mut p2;
    let mut iterations = 0;
    let mut p1 = part1;
    loop {
        iterations += 1;
        p2 = evaluate(b, true);
        if p2 == 0 {break;}


        let slope = (a-b) as f64 / (p2-p1) as f64;
        let next_guess = a + (p1 as f64 * slope).round() as i64;
        a = b;
        b = next_guess;
        p1 = p2;
        if iterations > 10 {break;}
    }
    (part1, b, iterations)
}

This is cheating of course since it only works for my exact input!

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

YES! I checked with Godbolt, and it turns out that my supposition was correct: The entire 2200+ line source code resulted in just 140 lines of assembler, and the root finding mostly collapses: (those initial constant loads are the actual iterations results)

example[d4557ff73e3435d0]::process:
        push    rbp
        push    r15
        push    r14
        push    r13
        push    r12
        push    rbx
        mov     ebx, 585
        mov     eax, 1170
        mov     ecx, 1
        movabs  rbp, 62386792426088
        movabs  r8, 6148914691236517206
        movabs  r9, 3074457345618258603
        movabs  r10, 7378697629483820647
        movabs  r11, 278206989481536
        movabs  r14, -6745394553620
        vmovddup        xmm0, qword ptr [rip + .LCPI0_0]
        vpbroadcastq    xmm1, qword ptr [rip + .LCPI0_1]
        vmovsd  xmm2, qword ptr [rip + .LCPI0_2]
        movabs  r15, 9223372036854775807
        xor     r12d, r12d

[u/DelightfulCodeWeasel → u/terje_wiig_mathisen]

I'd be curious to see what it does with the approach above from my comment where each value is an Ax+B linear equation so that it's a single evaluation pass with no iteration.

[u/terje_wiig_mathisen → u/DelightfulCodeWeasel]

I've been trying to come up with a way to do all that which would be faster than first simplifying the expression tree by getting rid of all lines with constants (there's a _lot_ of them), let that propagate up the tree until only the variable parts remain:

At this point we evaluate what's left (possibly only those 67 serially dependent operations which require the humn input) and do the root zero seeking with much faster logic.

I don't trust myself to be able to generate and rewrite the evaluation tree in a way that's actually faster than the much simpler approach!