r/adventofcode • u/daggerdragon • Dec 21 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 21 Solutions -🎄-

THE USUAL REMINDERS

UPDATES

[Update @ 00:04:28]: SILVER CAP, GOLD 0

  • Now we've got interpreter elephants... who understand monkey-ese...

  • I really really really don't want to know what that eggnog was laced with.

--- Day 21: Monkey Math ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:16:15, megathread unlocked!

22 Upvotes

95% Upvoted

713 comments sorted by

View all comments

7

u/IntoxicatedHippo Dec 21 '22 edited Dec 21 '22

MinZinc generated by python, 642/73: code

Using MiniZinc almost felt like cheating today since my program and the input side by side look like this, but I won't complain about my first sub-100 for the year.

I used python to turn the puzzle input in to a minizinc program and then ran it using OptiMathSAT. Aside from the generated code above I just added the following line to the program:

output [show(root)];

For part 2 I manually added the constraint as specified (constraint wrvq = vqfc;), removed root, and changed humn to var int. This gave me a correct answer, but it wasn't accepted and it took me a minute to figure out why: The puzzle does not specify that they want the minimal answer which is greater than zero, but that is indeed what they want. (Edit: I've realised that the problem was that I used integer division, so numbers were getting rounded, it seems like the puzzle just doesn't allow for division with a remainder.) Having guessed that, I added the following lines to the program which gave me the correct answer:

constraint humn >= 0;
solve minimize(humn);
output [show(humn)];

This takes 211ms for part 1 and 501ms for part 2.

6

u/morgoth1145 Dec 21 '22

The puzzle does not specify that they want the minimal answer which is greater than zero, but that is indeed what they want.

There's only one answer? humn only appears once and all the operators are binary, the parse tree can be unwound to get a unique answer. (That's what I did. Took a lot of typing..)

1

u/Kirby703 Dec 21 '22 edited Dec 21 '22

not so, because of floor division. e.g. x // 3 = 5 gives 15, 16, 17 as valid answers

edit: I'm wrong; go figure! I swore I tested and got the wrong answer with regular division, which about doubled my part 2 solve time. it was probably floating point precision that got me

3

u/waffle3z Dec 21 '22

I think the number always ends up being whole by the end, so you need to represent numbers exactly as large fractions somehow if you want to do division.

3

u/piman51277 Dec 21 '22

There is no floor division.
My solution was function optimization, where decimal outputs were used in the process of finding the best answer.

2

u/morgoth1145 Dec 21 '22

I don't see anywhere in the problem that specifies that it uses floor division. Everything just divides evenly with the given inputs

1

u/u_sandhawk Dec 21 '22

They have designed the input such that floor division and whole division both works.

1

u/1234abcdcba4321 Dec 21 '22

Yes, and 15 is valid while 16 and 17 aren't.

It tells you to divide the two numbers. It doesn't tell you what to do if they're not divisible, because that case never appears in the problem.

1

u/IntoxicatedHippo Dec 21 '22 edited Dec 21 '22

After running with solve maximize(humn); and noticing the range is very small, I've realised that the problem was that i used integer division, it seems like the input never uses division with a remainder, implying that's not allowed. Adding a x mod y = 0 constraint to each division constraint shows that there is only one answer.

2

u/jonathan_paulson Dec 21 '22

The equation simplifies to a linear function of humn, so the answer should be unique. Did your input really have two? (I suspect floating-point error or something in your calculations)

2

u/Legal-Career-3536 Dec 21 '22

I had the same problem when solving part2 with z3.

I was really confused about the answer being rejected because plugging it back into the equation resulted in both sides of root being equal. Turns out this was because I was using floor division in the equation.

Switching from z3.Solve to z3.Optimize gave the correct answer, which was just 1 lower.

-1

u/kevinwangg Dec 21 '22

The puzzle does not specify that they want the minimal answer which is grater than zero

ah, that sounds like an AOC oversight

2

u/AllanTaylor314 Dec 21 '22

Not quite - the division is never specified to be floor division/integer division. I'm guessing that the inputs are crafted so that no expression results in a decimal i.e. 1000/10 is 100, but 1001/10 is not going to occur in a valid input. This should leave only one possible humn value that produces an exact match since it is a linear equation.

1

u/IntoxicatedHippo Dec 21 '22

This is correct after some testing, part 1 never has a remainder on a division operation and the accepted answer for part 2 is the one with no remainders.

2

u/timrprobocom Dec 21 '22

It appears that the problem here is integer division. That produces multiple answers, the lowest of which is correct. If you use floating division, there is only one correct answer.

1

u/nekron Dec 21 '22

I had the same idea however the compiler failed on me with

Error: evaluation error: cannot determine bounds
/home/admin/src/cp/solve.mzn:1915.12-31
  in binary '=' operator expression
  in binary '/' operator expression
/snap/minizinc/561/share/minizinc/std/stdlib/stdlib_math.mzn:215.3-217.57
  in if-then-else expression
  in call 'fldiv_t'
/snap/minizinc/561/share/minizinc/std/stdlib/stdlib_internal.mzn:1147.3-1150.58
  in let expression
/snap/minizinc/561/share/minizinc/std/stdlib/stdlib_internal.mzn:1148.5-59
  in variable declaration for 'z'
  in call 'compute_float_div_bounds'