https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 21> :thread:
# advent-of-code
a
s
The obligatory "Part 2 works on test, but doesn't work on input"... Anyone had this yet?
j
Oh man for part1 I first had negative answer, told me to use Long
t
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
s
Oh, I've found the issue. The "reversing" of mathematical operations is a bit trickier than I thought
j
oh man I'm still struggeling to solve the equation system for part2, mainly with inputing it into a solver
l
j
tanks @Lidonis Calhau that was useful, now I have to come up with how to solve it in code.
n
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.
j
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
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?
so I figured it out why it happens when I reverse the operations I get an Long overflow
r
@Lidonis Calhau thanks for the link 😄
e
I started writing my own polynomial class, but partway through I thought "is this really gonna be required?"
so I tested with only supporting 
m x + b
and it worked, so that's what I'm going with
p
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
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.
n
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...
e
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
s
Part 1 on coroutines
e
I think you could use a CompletableDeferred instead of a channel
o
Is there anything in the part 2 that indicates that the resulting equation is linear?
s
There’s just one unknown, and it only occurs as part of arithmetic operations with constant values, so it’s linear.
o
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
r
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.
e
@Sergei Petunin that alone doesn't guarantee linearity; there needs to be only one path to 
humn
as well, otherwise
Copy code
root = aaaa + bbbb
aaaa = humn * humn
bbbb = 1
r
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
h
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 } }
r
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 👍
n
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.
e
I didn't check 😆 I had a cache but found that things got ~2x faster when I took it out
j
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
t
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
m
Yes, I complained about this about half a year ago. Annoying, but not critical and therefore not a priority to fix, it seems …
j
I reported a similar thing, got an answer that it's fixed for next idea version, maybe that one is also fixed with it
7 Views
Open in Slack
PreviousNext
Powered by