<Advent of Code 2022 day 21> :thread:

# advent-of-code

[Advent of Code 2021 day 21]

Advent of Code 2022 day 21 🧵

[Sergei Petunin]

The obligatory "Part 2 works on test, but doesn't work on input"... Anyone had this yet?

[Jonathan Kolberg]

Oh man for part1 I first had negative answer, told me to use Long

[Timmy]

Finally had an excuse to use kmath for AOC! Specifically the polynomials for part 2. Although I admit my first solution for part 2 was printing the equation as a string and asking an online solver to give me the answer...

https://github.com/TimothyEarley/advent-of-code/blob/master/src/main/kotlin/de/earley/adventofcode2022/day21/Day21.kt

[Sergei Petunin]

Oh, I've found the issue. The "reversing" of mathematical operations is a bit trickier than I thought

[Sergei Petunin]

Nothing like a nice cup of recursion to start the day https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2022/Day21.kt

[Jonathan Kolberg]

oh man I'm still struggeling to solve the equation system for part2, mainly with inputing it into a solver

[Lidonis Calhau]

I have used https://www.mathpapa.com/equation-solver/

[Jonathan Kolberg]

tanks @Lidonis Calhau that was useful, now I have to come up with how to solve it in code.

[nkiesel]

for part 2 I determined if my node was in the left or the right. then eval the other side, adjust the required value (initial value for this is eval of root node subtree not containing me). Once you reach the "me " node, you have the required value.

[Jonathan Kolberg]

oh nice found a case where idea suggest removing type parameters, but kotlin is not able to, have build a minimal reproduction https://youtrack.jetbrains.com/issue/KTIJ-24042

[Jonathan Kolberg]

after computing part2 I get the correct value for the example but real input gives me a big negative number and I know that the answer has to be positive, did anybody else have that problem?

[Jonathan Kolberg]

so I figured it out why it happens when I reverse the operations I get an Long overflow

[ritesh]

@Lidonis Calhau thanks for the link 😄

[ephemient]

https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day21.kt

[ephemient]

I started writing my own polynomial class, but partway through I thought "is this really gonna be required?"

[ephemient]

so I tested with only supporting m x + b and it worked, so that's what I'm going with

[phldavies]

https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day21.kt I opted to evaluate the expression up front as much as I could, then walk up the expression tree rearranging the expression much as I’d do manually on paper

[phldavies]

It probably amounts to much the same as @nkiesel’s approach of isolating the branch in which humn is in, evaluating the other branch and then rearranging - except by the time I come to solve it I’ve already evaluated all possible constant branches.

[nkiesel]

I never rearrange. Just find the branch my node is in, eval the other side, and then compute what my branch must return to produce the correct value. I could memorize the path to my node instead of repeatably searching, but the tree is shallow...

[ephemient]

I handle DAGs, didn't realize that wasn't necessary. I originally had code to handle humn² or humn¯¹ or other exponents, but I took it out

[Sergei Petunin]

Part 1 on coroutines

[ephemient]

I think you could use a CompletableDeferred instead of a channel

[Ozioma Ogbe]

Is there anything in the part 2 that indicates that the resulting equation is linear?

[Sergei Petunin]

There’s just one unknown, and it only occurs as part of arithmetic operations with constant values, so it’s linear.

[Ozioma Ogbe]

I was thinking if its linear, we could also use binary search (maybe start with a higher base like base 10000) to find the value of humn

[rkechols]

I cache the result of each node in part 1, then in part 2 I walk up the tree from humn clearing those cache entries. Then I do like Norbert said: walk down the tree along the path of unknowns (no val in cache) reversing the calculations from parent + known child to get the needed value of the unknown child.

[ephemient]

@Sergei Petunin that alone doesn't guarantee linearity; there needs to be only one path to humn as well, otherwise

root = aaaa + bbbb
aaaa = humn * humn
bbbb = 1

[rkechols]

Yeah, there's a lot of convenient stuff in this one, like how it's strictly a binary tree, not something more complicated where things are reused in multiple places

[Hasan Gilmanov]

For part 2 i made sort of machine learning stuff)):

start with current humn value (5 as before)
calculate diff between left and right operands,
while diff != 0 {
check diff for two new humns values:
diff1: newHumn1 = humn + diff / 2
diff2: newHhum2 = humn - diff /2

if (abs(diff1) < abs(diff2)) {
humn = newHumn1
} else {
humn = newHumn2
}
}

[Riccardo Lippolis]

for part 1 I didn't want to risk evaluating unnecessary branches, so using by lazy for the evaluation worked nicely. For the second part, basically the same solution as @nkiesel indeed 👍

[nkiesel]

Yeah, I first made sure that the equations form a tree and not a graph. Otherwise, my approach would not have worked. And I don't cache subtree values because I never evaluate a subtree more than once.

[ephemient]

I didn't check 😆 I had a cache but found that things got ~2x faster when I took it out

[Jon Senchyna]

Not sure how this compares to only lazily computing, but I computed values as I parsed monkeys. As I found monkeys waiting on others, I stored them in a map using the target monkeys as the key. Each time I processed a monkey that had a number, I checked the monkeys waiting on it and processed them if they were no longer waiting (recursively for those waiting on the newly processed monkey).

For part two, I searched down the tree for the path to human and then did the operation reversal everyone else did, except that I had all values already resolved so I only had to traverse directly down to humn.

https://github.com/TheSench/advent-of-code-2022/blob/main/src/main/kotlin/day21/Day21.kt

[todd.ginsberg]

That was fun. I really liked this one. It took me a while to work out all of the anti-operation formulas, but eventually got it. 🙂

• Blog
• Code

[Michael Böiers]

Compact solution (55 sloc) https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2022/day21.kt

[Michael Böiers]

Yes, I complained about this about half a year ago. Annoying, but not critical and therefore not a priority to fix, it seems …

[Jonathan Kolberg]

I reported a similar thing, got an answer that it's fixed for next idea version, maybe that one is also fixed with it