11
votes

# Day 18: Operation Order

Today's problem description: https://adventofcode.com/2020/day/18

Join the Tildes private leaderboard! You can do that on this page, by entering join code `730956-de85ce0c`

.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python`

with any of the "short names" listed in this page of supported languages):

```
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
```

Literally textbook today - not that there's a problem with that.

C### Part 1

## Part 2

## Helpers

## Commentary

This was literally just implementing the shunting-yard algorithm based off the wiki article. I can't really complain, though - I've never actually _done_ it before, and it's a neat process to watch the way everything lines up in the end. I wonder if there's any part of this that should go in the Future AoC Library that I should really get around to making...Today was another day of having a better part 2 leaderboard ranking than part 1, which I'm always proud of.

I ran into a bug that only effected 4 of my equations and was very hard to track down. I had to run someone else's per-equation answers through diffchecker to even figure out why the fuck my answer wasn't correct. More on the specifics in the spoilery parts.

I'm legitimately impressed with how small some people can make these solvers.

Tonight's eurobeat is DEJA VU

## Day 17 Part A – Python

Basically I run my parenthesis method on every row. What parenthesis does is it looks for pairs of parenthesis and then sends the internals over to my string_solve method, which handles reading through a string using the new order of operations. Then it swaps in the the solution in place of the old parenthesis and checks again. It keeps going like that until there are no more parenthesis.

Once all the parenthesis have been dealt with, it sends all the remaining parts to string_solve one last time, and that's the answer

Basically everything finds a small portion of the equation that it knows how to deal with, the it simplifies it and runs replace to swap the more complex version out for the simpler version

The bug that was taking forever to solve was that my 'replace' functions didn't have the 'DO THIS ONLY ONCE' command, so in some rare cases (4, I counted). It would swap out multiple portions of the equation... which fucked up the result but didn't cause any errors.

## Day 17 Part B – Python

This basically works the same way as part A, but I add a new regex pattern and do all the '+'s before the '*'s in string_solve

## Tips and Commentary

There are very simple (minimal code required, as opposed to easy) ways to solve this one, if you take advantage of some of the built in functions for your preferred language

You may have an easier time if you subdivide the tasks of 'dealing with parenthesis' and 'doing the actual math'

If you're having trouble with your results, it may help to compare to a 'known good'. For example, some of my equations weren't active properly, but I couldn't figure out which ones, because all the ones I validated by hand came back correct. So I used someone else's method to calculate all the individual equations and compared it to my results. That helped me isolate the few equations that were giving me trouble. This method can be extremely viable in the 'real world' but that depends on the nature of the work you're doing

If you end up swapping around portions of your equations using something like python's replace method, be careful that you're only swapping out what you want to, and not grabbing anything extra by mistake. For example, one of my equations looked like this:

When it should have looked like this:

PythonRepo Link

## Part 1

This took me a lot longer than I had hoped... I started off by doing a recursive descent parser and a recursive evaluator and that worked fine for Part 1 and can be seen here. Unfortunately, Part 2 requires precedence and I didn't know how to do that with recursive descent...

So after hours of trying all sorts of random things, I took the hint from @JRandomHacker and looked up the Shunting-yard algorithm and decided to go with that since I do know how to evaluate RPN expressions. So long story short, I use the algorithm to convert the infix expression into an RPN/postfix expression and then evaluate it.

## Part 2 (diff)

Once the Shunting-yard algorithm was in place, all I had to do for Part 2 was add an additional condition to ensure I move operators from the operators stack only if they have greater or equal precedence to the current token. Fortunately for me, '+' > '*', so I didn't have to anything special for this comparison.

## Part 1 (Recursive Descent)

After getting some sleep, I decided to lookup how to handle operator precedence and association with recursive descent and found that an Operator-precedence parser isn't too bad (I just didn't know about it). Below is a working solution for Part 1 and 2 using this approach.

## Part 2 (Recursive Descent, Diff)

Once again, Part 2 was just a minor change. In this case, I just made '+' a higher precedence in the table and the algorithm does the rest!

Fucking hell. Once again, I initially got stuck on a parenthesis bug that that only happened with a particular arrangement not present in the test examples. I tracked it down by trying a bunch of simple equations and eventually found that "(1 + ((1 + 1 + 1)) + 1)" equaled 4.

I guess part 2 was rather simple if you set it up correctly but, of course, I didn't. My solution is an ugly mess of recursively splitting up the expression until I can get a few blocks of additions that are multiplied at the end. I think I assume that numbers don't include zeroes and other silly stuff like that. I think I now need to look up other people's solutions to see how to do this sanely.

## Part 1+2

This one was (is?) tough for me. I'm sure it's as textbook as some others have said but my knowledge here is primarily of the informal sort. Either way, I went for a recursive solution for part 1, but it's getting late, so I'll come back with part 2 tomorrow.

EDIT: Part 2 was much easier than I thought, but I ended up not able to get to it until today. Playing catch up now!

## Part 1

## Part 2 Diff

ElixirI took a while on this one because I really wanted to find a way to do all the work in one pass, but part 2 made that too messy by having two different ways of changing evaluation order (parens and

`*`

). So I ended up processing each expression in two passes: first, convert each line to a list of`value`

s, where^{? is a convenience operator to get the ascii codepoint of a given character. ?a == 97}The nested lists represent quantities (parenthetical expressions).

From there I have a recursive function that processes the expression one

`value`

at a time and calls itself whenever it finds a quantity.For part 2, the only difference was that whenever we find a

`*`

we evaluate everything to the right of it first before evaluating the multiplication. In order to avoid copy-pasting a bunch of the same code from my part 1 evaluator I just added a flag argument to the function so that it can know whether it's evaluating part 1 vs part 2 and act accordingly when it sees a`*`

.A small trick to avoid needing special logic for the start of the evaluation was to prepend each expression with

`0 +`

. This made it so the evaluator could always perform an operation as soon as it found a numerical value—even if the expression started with a number`n`

, it would be treated as`0 + n`

which could be evaluated immediately. You can see this in action with the default argument of`{0, &+/2}`

for`evaluate/3`

's accumulator.## Parts 1 and 2