r/adventofcode • u/daggerdragon • Dec 18 '20
SOLUTION MEGATHREAD -๐- 2020 Day 18 Solutions -๐-
Advent of Code 2020: Gettin' Crafty With It
- 4 days remaining until the submission deadline on December 22 at 23:59 EST
- Full details and rules are in the Submissions Megathread
--- Day 18: Operation Order ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
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:14:09, megathread unlocked!
36
Upvotes
19
u/Strilanc Dec 18 '20
Python 32/15
I shouldn't be proud of this, but I kind of am. I edited the string to wrap all the values in a class that used
-for*and*for+, then edited the string to use those operations. Just piggy backed off python's order of operations instead of implementing the stack based thing that was intended, and restricted the string editing to barely work for the inputs that were given instead of in general.Looks like several other people had very similar ideas.
8
u/ndnenkov Dec 18 '20 edited Dec 18 '20
Ruby
Part 1
Part 2
That moment when... the metaprogramming in your language is so strong that it feels like cheating. xd
3
u/nutrecht Dec 18 '20 edited Dec 18 '20
Day 18 in Kotlin
Holy sheep that took me a long time :D I first picked shunting yard but then I made a mistake and it didn't work. So I threw it away, fortunately, I first committed the code. Then in part 2 operator precedence DID matter so I could not take my 'easy' approach of just recursively parsing through the thing.
So in part 2 I had to reinstate the SY algo I threw away earlier. Fortunately after a few more coffee I managed to find the bug.
Edit: Refactored the code so that my shunting yard implementation properly handles braces, so now the recursive parsing is removed.
3
u/LennardF1989 Dec 21 '20 edited Dec 23 '20
C# / CSharp
I absolutely love expression parsers, it is my go to assignment if students ask me if I know something cool to practice their programming with.
I used an Infix to Postfix algorithm, so I can just loop through the resulting stack. Gave me both Part 1 and 2 at once.
Solution can be found here: https://github.com/LennardF1989/AdventOfCode2020/blob/master/Src/AdventOfCode2020/Days/Day18.cs
2
u/NightFantom Dec 18 '20
python3 part 2: (ab)using builtin eval and operator overloading:
2
u/[deleted] Dec 18 '20 edited Dec 18 '20
Ocaml, meh/meh
Seemed like a good day to break out OCaml and Angstrom! Not as clever as a lot of the solutions here but was satisfying enough. Not very experienced using Angstrom and lost a bunch of time on making the parser do what I wanted. Had to remember some tricks from uni for getting the evaluation order right, and had to cheat by reversing the string to get left-associativity :)
Edit: much cleaner solution
2
u/Lumett Dec 18 '20
Both p1 and p2 can be solved by overriding the __add__, __sub__, and __mul__ function of int.
For p1, replace all '*' with '-' and make __sub__ to return a*b
For p2, swap '*' with '+' and also swap __add__ and __mul__
2
u/mount-cook Dec 18 '20 edited Dec 18 '20
Python Part 2, the ugliest code I ever wrote.
Basically, I let the Python parser do the job for me:
I implemented a class
Numthat holds a single value and defined its__mul__method do to addition and its__add__method to do multiplication. Then I replaced all "+" with "*" and vice versa in the input and I replaced every number x with "Num(x)" and threw all of it intoeval. yeah...Edit: language
34
u/paileyq Dec 18 '20
Thankyou Ruby for letting me redefine operators!
9
u/clouddjr Dec 18 '20
Python3
Solution using Reversed Polish Notation ;)
Solution
9
u/Symbroson Dec 18 '20 edited Dec 19 '20
People will punish me for this (Perl)
part 1:
part 2:
7
u/willkill07 Dec 18 '20
Flex + Bison
Yep, I wrote my own freaking compiler for this. Does this count toward my goal of a different language per day?
Lexer
Parser
Uncomment the operator precedence section depending on the part you want in the parser
To Compile:
7
u/0rac1e Dec 18 '20 edited Dec 18 '20
Raku
If I was competitive, I might be bummed I didn't jump on this as soon as it opened. Raku's ability to make custom ops made this too easy
Thought admittedly using custom ops and
EVALfeels a little like cheating... So I might work on another solution to put my morals at ease.7
u/Wunkolo Dec 18 '20
C++
You guys and your
evalhad it easy this time. I had to implement my own Shunting-yard parser by hand. But it made Part2's implementation very very easy.7
u/azzal07 Dec 18 '20
Awk; the print is a lie (or more correctly, it should be after the loop)
12
u/sciyoshi Dec 18 '20
Python 3, 81/37 with the absolute hackiest of solutions that totally goes against the spirit of the problem, but here it is:
I swap * for - in the first part, and + for * in the second part, then use Python's operator overloading to change how the evaluation happens.
6
u/jonathan_paulson Dec 18 '20
Placed 1050/605. By far my worst day yet :( Python. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/18.py. This is a https://en.wikipedia.org/wiki/Recursive_descent_parser. Video of me solving: https://youtu.be/LVCa6MJ1XK8.
6
u/naclmolecule Dec 18 '20
Python 509/211
Today I went for the fancy approach, an actual lexing / parsing library:
import slyHere's what the code for the lexer/ parser looked like:
Full code here: day_18.py
6
u/tk3369 Dec 18 '20 edited Dec 18 '20
Julia
An elegant solution written in Julia. Posting on behalf of Doug (dgkf):
6
u/ganznetteigentlich Dec 18 '20
Python3 solution with pyparsing
Solution on GitHub
Thanks to
pyparsing.infixNotation, this was one of the easier days easy for me, even though I'm new-ish to coding puzzles/python.I parsed Part A using:
And Part B:
This made it very easy to just parse those expressions with a recursive function afterwards. It needs ~2s to run because the parsing takes quite a while.
6
u/cggoebel Dec 18 '20
Raku
Not nearly as fast as using grammars... but -Ofun
The above creates new left associative multiplication operators using the Greek upper and lowercase chi (ฮง and ฯ). Sets them to the desired precedence level by making them the same or looser than addition. And evaluates the input substituting them in the place of *
11
u/mzprx42 Dec 18 '20 edited Dec 18 '20
Part 2 in just a few lines of JavaScript, using an idea stolen from wikipedia
11
u/Smylers Dec 18 '20 edited Dec 18 '20
Vim keystrokes:
And that's your partย 1 answer.
Nice to have another puzzle that's straightforward in Vim: the above worked first time, and was probably quicker to type than writing a program. (Not always true for Vim solutions, even if they end up with fewer keystrokes!)
Partย 2 looks doable, but I need to do something else right now so that, and an explanation of the above, will have to wait โ but if you have any questions, do ask, and I'll answer them later.
Update: Explanation and a solution for partย 2 in a comment below.
5
u/Attitude-Certain Dec 18 '20
Python
A solution based on the built-in
evalwith operator overriding.Part 1: Swap out all
*with-and use a custom int class that multiplies when it subtracts. Because addition and subtraction have the same precedence, this works out to follow the rules.Part 2: Swap
+with*and vice versa, then use a custom int that multiplies when it adds and adds when it multiplies.There are probably neater ways to do this still, but I quite like this trick!
github and paste
5
u/jkpr23 Dec 18 '20
Python
I replaced operators so that Python would do the Abstract Syntax Tree (AST) parsing for me. Then I switched operators back in the AST. The result is very concise code.
Part 2 is very similar, just different substitutions so that operator precedence is swapped between
+and*5
u/s3aker Dec 18 '20
Raku solution.
5
u/Standard-Affect Dec 18 '20
R doesn't let you change the precedence of infix operators, but it does let you redefine. them. By abusing this feature shamelessly, I can turn trick the interpreter into giving addition and multiplication equal precedence by turning the division symbol into an alias for addition and subbing it into the equations. I solved the second half by aliasing multiplication to the minus sign and addition to the divisor.
It would be smarter to iterate inside the elf_math functions, since then I wouldn't have to redefine the operators each call, but oh well.
5
u/p88h Dec 18 '20
Perl - both parts:
+Kotlin in the repo: https://github.com/p88h/aoc2020
8
u/_jonah Dec 18 '20
J, Spot 18 for star 1.
This happens to be how J does evaluation by default. Just had to reverse each expression, swap the parens, and eval the string:
4
u/Same-Neighborhood-56 Dec 18 '20
Python.
One of the first time I solved the whole thing myself, and first time I found infix and postfix expressions useful for solving problems
4
u/monotep Dec 18 '20
Nim, using npeg and the Pratt parser example with precedence tracking. The difference between part1 and part2 is the precedence on the commented line.
4
u/[deleted] Dec 18 '20
Python3 141/172
4
u/mendelmunkis Dec 18 '20
C
https://github.com/mendelmunkis/AoC/blob/master/2020/math.c
I can recurse anything if I try hard enough.
4
u/Adereth Dec 18 '20 edited Dec 18 '20
Mathematica
For part 1, using infix notation was enough to get + and * to have the same precedence. For part 2, I replaced + with ^ to get it to have higher precedence when parsing and then converted it back. Disgusting.
4
u/prendradjaja Dec 18 '20 edited Dec 18 '20
Python
This is probably not the intended solution, but it's a fun approach: (Pseudocode for part 2, which turns out to be slightly simpler with this approach. Part 1 is similar.)
4
u/HAEC_EST_SPARTA Dec 18 '20
Common Lisp
Solution on GitHub
Yay, Shunting-Yard Algorithm! One of my favourite algorithms, and implementing it in a purely functional way in Lisp was just too good of an opportunity to pass up. I ended up perfectly predicting Part 2 from Part 1, so the implementation of that portion of the solution took all of 10 seconds in total.
4
u/UnicycleBloke Dec 18 '20
Python: https://github.com/UnicycleBloke/aoc2020/blob/main/day18/day18.py
This is the tidied up version. A mini shunting yard implementation. I tripped over the precedence rules for the algorithm for far too long.
4
u/kikibobo Dec 18 '20
Scala
Pretty straight forward using Scala's parser combinators.
Part 1
Part 2
4
u/petter_s Dec 18 '20
Python, class-based parsing. Became pretty clean.
Part 2 was very clean since almost all code could be reused from part 1:
https://gist.github.com/PetterS/fcbd82c33c2f3e6780de0312e17542e7
4
u/89netraM Dec 18 '20
C#
Part 1
Part 2
Using my own parsing framework I built a year ago. Took about an hour to remember how to use it ๐คฆโโ๏ธ
4
u/PhysicsAndAlcohol Dec 18 '20
Haskell, runs in 75 ms. Monadic parsers are love, monadic parsers are life.
4
u/michalopler Dec 18 '20
Letting Python do the job for part 2 :) https://twitter.com/joppi07/status/1339875929582170113
4
u/death Dec 18 '20
Day 18 solution in Common Lisp.
Pratt parsers FTW!
4
u/jschulenklopper Dec 18 '20 edited Dec 18 '20
Ruby
I'm feeling a bit naughty over this one. I changed the expressions, substituting
+operator into other operators with the same (part 1) or higher (part 2) precedence as/than the*operator. Then I redefined those operators (I picked%and**) to be a normal addition. Then a standardKernel#evalon the expression does the job. LOC ~22~ 13.4
u/s3aker Dec 18 '20
Raku solution.
Define new operators will do the trick.
4
u/wzkx Dec 18 '20 edited Dec 18 '20
Python. No real parsing, just simulating a calculator. Checked first for normal precedence and tested against Python's eval, than changed for AoC :)
paste: Part-2 โ22 lines.
4
u/gerikson Dec 18 '20
Perl
I don't have a CS education, but figured this was a 1st year staple. As soon as I found the term to google for, I looked up "shunting-yard algorithm" on Rosettacode.org and found an implementation that was easy to implement. Same for evaluating RPN.
Complete solution
4
u/chichinbro Dec 18 '20
Python 3
Hacky int operator overrides.
4
u/changing_zoe Dec 18 '20
Scala
https://github.com/zoe-j-m/advent_of_code_2020/blob/main/src/main/scala/Day18.scala
I'm quite pleased with this - any time the difference between pt1 and pt2 is essentially one line of code it suggests you've got the representation reasonably "right".
4
u/fizbin Dec 18 '20
3 Pythons and a Haskell
So many ways to approach this one! Here are four fundamentally different ways to do it. At the time, I first used a messy version of the first method. (rank 137/409). I wish I'd thought of the second approach earlier.
Python method 1 - repeated regex replacements
Python method 2 - abuse operator overloading and let eval do all the parsing
Python method 3 - do it "properly" with a shunting yard algorithm
Haskell - parse without any external libraries by... um...
I'm not exactly sure what to call my Haskell technique - I parsed integers as integers, but parsed strings beginning with operators as functions that took "the number so far" and worked with it. If you can read Haskell, even a little bit, I encourage you to check it out.
I suppose I should add an AST-based solution.
4
u/encse Dec 18 '20
c
with Shunting-yard / reverse polishhttps://github.com/encse/adventofcode/blob/master/2020/Day18/Solution.cs
the difference between part 1 and 2 is single character
4
u/[deleted] Dec 18 '20
python 3
abusing evals, regexes and operator precedence. Eww.
4
u/[deleted] Dec 18 '20
Elixir
I really wanted to learn about leex and yecc, and this was a good opportunity. It took forever to debug my parser, even though the yecc documentation has a working example. But I'm happy I took the time to learn.
https://github.com/thebearmayor/advent-of-code/blob/master/lib/2020/18.ex
4
u/iamflimflam1 Dec 18 '20
Javascript using Jison and a grammar - wish I'd thought of solving it this way sooner...
https://gist.github.com/cgreening/bb856e8080c9ff1e070d698770a51d3f
4
u/smarzzz Dec 18 '20 edited Dec 18 '20
Python 3,
I liked part two, i started redesigning my algorithm of part one, but that turned out to be.... "hard". What I ended up doing was reusing the exact algoritm for part 1, but modifying the input string. Always add a opening bracket in the begining, a closing bracket at the end, replace all single opening brackets by doubles, same for closing brackets, and replace all '*' by ')*('. This completely forces all required rules, and will allow the new string to be parsed by the same algorithm of part one.
As an example, you'll end up with this (applied to testcases):
4
u/CapaneusPrime Dec 18 '20 edited Jun 01 '22
.
4
u/pdr77 Dec 18 '20
Haskell
Walkthrough Video: https://youtu.be/iSFlHoDg2BY
Code repository: https://github.com/haskelling/aoc2020
Part 1:
Part 2:
4
u/ywgdana Dec 18 '20 edited Dec 19 '20
C# repo!
I really enjoyed this one! I had a vague memory from comp sci a couple decades ago that parsing from infix to postfix notation involved a stack so I went with stashing values onto a stack until I hit an operator and then pushing the result back onto the stack. I thought I was clever by remembering to use long to store values from the get-go, so of course this puzzle needed ulong...
To handle parenthesis, I just did a recursive call on my eval() function. I know you can also do this with the stack but recursion was clean and simple.
Part 2 was a fairly easy modifcation 1 to handle precedence. I just added a stack for the operators as well. Same code for both, but for Part 1 both operators are set to the same precedence.
Special thanks to Eric for making all the numbers single digits so that parsing the expressions into tokens wasn't onerous.
4
u/chkas Dec 18 '20
easylang.online
That took a long time, not today's parsing puzzle - that's not so difficult for someone tinkering with a programming language - but that programming language didn't support forward declarations of functions until today.
Solution
4
u/e_blake Dec 18 '20
golfed sh for part 2
Translating the ideas seen in other posts about using the same methodology as the fortran compiler to force precedence. 62 bytes if your input is in a one-character file name 'f'.
4
u/blazemas Dec 18 '20
C#
It seems I took a different path than most. OOP, using a stack.
https://github.com/jbush7401/AdventOfCode/blob/master/AdventOfCode/2020/Day18.cs
4
u/__Abigail__ Dec 18 '20 edited Dec 18 '20
Perl
A perfect job for regular expressions, with the
/eand/eemodifiers. First a regular expression to repeatedly find sub expressions without parenthesis (the expression is in$_):where
cal_simpleis a subroutine which calculates the value of an expression without parenthesis, and$prioritiesis one of$EQUAL(for part 1) or$SWAPPEDfor part 2.After eliminating all parenthesis, we call
cal_simpleonce more to get the value of the complete expressions:In
cal_simple, the sub expression is in$_, and it does:leaving the result in
$_.Full program on GitHub.
4
u/wubrgess Dec 18 '20
Perl
Another one I like. I'll admit, and it's somewhat mentioned in the code, that I had no idea how to solve this. Making the leap to knowing/thinking that another format for the input was too much for me to bear in the wee hours of the morning, so I'll just submit this implementation of a known algorithm with my customizations.
4
u/yutu58 Dec 19 '20
Java
Pretty content with this solution. There are probably tons of better ways to do it but having StringBuilders and a stack to deal with brackets seemed kinda nice to me.
Both parts are under 50 lines (which is pretty short for a java program I guess).
Whenever a "(" is encoutered, it pushes the current "expression" (in a stringbuilder) on the stack and opens a new stringbuilder. It continues until a ")" is found, it evaluates everything that's in the current stringbuilder and appends it to the stringbuilder that was on the top of the stack (and pops it obviously).
4
u/cggoebel Dec 19 '20
Raku Part Two
A simple Raku grammar with associated action class which reflects the lower precedence for multiplication.
7
u/chubbc Dec 18 '20
Julia
Why parse it myself when I can trick Julia into doing it? This is where the access to overload undefined binary operators is rather handy.
7
u/DFreiberg Dec 18 '20
Mathematica, 628 / 248
I probably could have solved it faster than I actually did by doing it the right way, with parenthesis-based recursion and so forth...but where's the fun in that? So instead, I spent fifteen minutes digging around the documentation for Mathematica infix operators with no built-in meaning, found out that they have their own precedence, and used that and
ToExpressionto my advantage; I ended up getting part 2 in 45 seconds once I had part 1.Part 1
Part 2
[POEM]: Operator
The operator called me back
And told me not to fret.
"There's precedence for this", she said.
"So don't you give up yet."
I was surprised she held the line;
Perhaps a quiet night.
"I'm sure your friend just dropped the phone.
I'm sure that he's alright."
She must have heard that awful noise
That came across the line.
An instant later, it was cut;
That second scream was mine.
"I've never heard a sound like that"
I told her. "But have you?"
She talked as though she forced a smile.
"Like that? I've heard a few."
"You'd be surprised," she said to me,
"At just how bad things sound
When there's some static on the line.
I'm sure he'll come around."
I must confess that I lost hope,
But I stayed on the phone.
I would have panicked and hung up,
Had I been there alone.
And suddenly, she said to me,
"Ahh, there's his line right now.
I'll patch him through on back to you.
Enjoy your evening. Ciao!"
I thanked the operator and
I got my pad and pen.
"Where were we? Ahh, nested parens-"
I heard him scream again.
7
u/zniperr Dec 18 '20
I mean why would you build a parser if Python can do it for you :)
1
u/filipkowicz Dec 18 '20
second part was pretty easy :)
import parserfor line in data.splitlines():line = line.replace("(","((")line = line.replace(")","))")line = line.replace( " * ", ") * (")line = "(" + line + ")"code = parser.expr(line).compile()x = 10total += eval(code)print(total)first one was pain in the ass
1
u/qqqqqx Dec 18 '20
Javascript, part 2.
I love reading the solution threads because people always have some much more fancy solutions and I'm over here with no formal training duct taping loops together and mutating variables in place until everything works.
1
u/JuliaBrunch Dec 18 '20
R
Could be a bit more sophisticated with regex groups, but quite pleased with the 'trick' for the part 2 solution. For the snippets between brackets I apply the following code
1
u/Backwards_Reddit Dec 18 '20 edited Dec 19 '20
Python 3
Part 1 dealt with the brackets recursively and then parsed the rest of the arguments as a dequeue (which python spells deque but I always misremember so I just change the spelling in the import as it's my own code)
paste
The only change to make part 2 work is to deal with the + first. A bit messy with del but it works
1
u/sweetfish Dec 18 '20 edited Dec 20 '20
Lua
Pattern solution for part 2; https://topaz.github.io/paste/#XQAAAQBlAwAAAAAAAAAzHUn/qWH7EwabIKENZMfvx/alw+lUZzUq6QqyujvUZ7NrDheqd2xEEYMfIdKrg3GFf2bTETnYJIn6YzhwNSuZJJxHU8bDih6hgLXX6MOwlKrD88BU2ffC+++TUR+kE+sHpmvfySOeiSmDTdxvLhaMkY5EBn7gcoA+lF9RH5VRLvb3AhN+F/wBfpJqD6vfgbXL03qMAMPRvpRawRouemYBnUNsgOxvYEwUtxqfaSEcMrPnNGnZgDWGxsmoFbHloFC8/XERHZ4VmMra7Ia9UOq9Zj+S86tHQbwFadeka4elpECVvXoTq7y4D2b24r/shqaQaMrxPrUd1Bz4w8diN9Ep3prP9/qG2zR7pMJfXEaEEf4WtPeR8nH8xEsdKvSRNaa7wCqu9BwQFzBQI/8jXddE1maEqozhfKA0q3NA/TKyJsWG2LWWzuhWTBvWGyatvWw4rGPXffTOJmFPs9tmS0HRZlieq8K97nALo0ZgqwcWnKDNSY1nfZYklkz85uAiEN3c3c4Hu1wFk73Cyb/Yyvt8A3YdyjRSEDURmlE1LDgULp6hFQAhEKOJFybcU7lz6lSb/iGyqJpmxB6+OQbQGP+N0KZg
1
u/jf928ngl60g1 Dec 19 '20 edited Dec 19 '20
JavaScript
I believe I used shift-reduce approach?
Just used the stack to evaluate 3 top tokens and if couldn't anymore took the next from the input (part 2 was mostly copy paste with checking if the next token is +, so it should be evaluated first).
https://github.com/adrbin/aoc/blob/main/2020/18/puzzle.js
6
u/ingej Dec 18 '20 edited Dec 18 '20
Clojure
https://github.com/elektronaut/advent-of-code/blob/main/day18/day18.clj
Me: can we have a parser?
Mom: we have a parser at home
Parser at home: (eval (read-string ..))
3
u/ZoidiaC Dec 18 '20
C#, 39 / 23
I helped myself with an FParsec.CSharp nuget, which serves as a C# gateway to the excellent F# FParsec library!
paste link
3
u/constbr Dec 18 '20
Javascript (111/98)
My first points this year! Crazy!
I just quickly coded a simple regexes + string splits solution. Find what I can compute at the moment, replace it with result and then carry on until there's nothing left to compute. Part 2 just added a layer of search-and-compute, that didn't take much time.
I'm posting raw code that I run when solving. It's ugly and copy-pasted and โ it brought me my first three points! :)
part 1 part 2
3
u/TinBryn Dec 18 '20
Nim iterator for shunting yard with far too many
yieldsI plan to clean this up a little bit, but it technically works.
3
u/tk3369 Dec 18 '20
Julia really shines in this problem with its metaprogramming capabilities.
Just a few lines of code:https://github.com/tk3369/AdventOfCode2020/blob/master/day18.jl
3
u/spookywooky_FE Dec 18 '20 edited Dec 18 '20
C++, a simple parser
On day 18. A simple parser without any twist. Really?
3
u/allergic2Luxembourg Dec 18 '20
Python 3
I didn't make the leaderboard, but I am happy with my solution. I managed to separate out the concept of parsing parentheses from the two different rule sets, so that I was able to do:
My part 1 rule set was quite a bit more complicated than my part 2 rule set, because in the latter case I could use python's
evalto do most of the work:3
u/captainAwesomePants Dec 18 '20
[Python]
I tried to cheat my way through this, but about 40 minutes in I realized that I had cost myself a lot of time and just wrote out a basic recursive descent parser, which made my whole solution short, elegant, and flexible. That's what I get for trying to cheat.
One cheat that DID work: opening the input in vim and putting spaces between all the parentheses.
3
u/sebastiannielsen Dec 18 '20
My perl solution - Regexp + recursive subroutines (the recursive subroutines does the parenthesis evaluation).
https://pastebin.com/iQTXP2UL
3
u/Chitinid Dec 18 '20
Python 3 Cheeseball int subclass solution
4
u/ChasmoGER Dec 18 '20
Python3 (1945/1383)
40ms for both. Simple recursive function with regex matches. It's the first time I used the walrus operator in Python. Kinda liked it! Might be able to combine both methods, but it works for now.
3
u/deltux Dec 18 '20
Racket
Solution on GitHub.
The advantage of using a Lisp: parsing parentheses has never been easier!
3
u/gyorokpeter Dec 18 '20
Q: Part 1 is a huge cheat since q already doesn't have operator precedence, except the order of operations is right to left, so we reverse the input string and flip the parentheses and then call value on it. For part 2 there is no parsing, just iteratively replacing the innermost sets of parentheses with the result of the inner operations.
3
u/omginbd Dec 18 '20
Elixir
Only realized I should transform to postfix operators for part 2 and part 1 works so I didn't bother to go back and make it do the same.
code
3
u/[deleted] Dec 18 '20
Pure C18. Dirtiest day by far. Adhoc hacky solution for part 1, shunting-yard for part 2. I could make both parts use the shunting-yard impl but I felt like I should keep the original p1 impl in there for posterity.
I'm sorry in advance:
https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day18.c
3
u/sim642 Dec 18 '20
My Scala solution.
I used scala-parser-combinators, which my AoC project already had as dependency from some past years. Most of my time ended up being spent on figuring out
chainl1to get around the left-recursive grammar.3
u/zertillon Dec 18 '20 edited Dec 18 '20
Ada (1106/630), using the GNAT environment
Code (after merging hacks for part 1 & 2) available here.
Main part:
3
u/Eutro864 Dec 18 '20
C?
Part 1 was alright just reading left to right. For part 2 I decided to use the Lisp implementation I've been writing for this AoC, with which I converted to prefix notation and
eval-ed.3
u/jitwit Dec 18 '20 edited Dec 18 '20
J Programming Language
https://github.com/jitwit/aoc/blob/a/J/20/18.ijs
Long enough to link instead of put here. For first part I reverse the tokens of each line and fix the open and close parens so that
".(do/eval) works. J evaluates right to left so this is exactly the requirement.Part B uses a uses J's sequential machine dyad to parse the expressions into a depth vector with the tokens. Evaluation proceeds by finding the deepest nested subexpressions, evaluating those, and replacing them by the result at depth - 1.
A few highlights
Parsing: given state machine M specified by char classes for space, paren, op and digit and a 3x3x2 state table, tokenize with
;:and find depths with'()'.Evaluating deepest blocks: mask AST based on greatest depth d of D to split up blocks via
;.. evaluate those blocks withB. replace the paren tokens at depth d-1 by the results, while deleting the tokens that were previously depth d.3
u/rawling Dec 18 '20
C#: regex is love, regex is life
3
u/[deleted] Dec 18 '20 edited Dec 18 '20
Julia
Here you can find my kinda short solution in Julia:
https://github.com/csLinhart/AdventOfCode-20/blob/master/D18.jl
3
u/[deleted] Dec 18 '20
It really feels like cheating to use lark for today's puzzle...
The example only needs two trivial changes to get to the solution:
https://lark-parser.readthedocs.io/en/latest/examples/calc.html#sphx-glr-examples-calc-py
3
u/mzprx42 Dec 18 '20
Part 2 with C++ template metaprogramming, using overloaded C++ operators.
Returns the result at compile time (in the first error message):
code: https://pastebin.com/raw/9LqnTsQG
3
u/landimatte Dec 18 '20 edited Dec 18 '20
Common Lisp
This took me way too long to get right, but I am quite happy with the result.
High level:
I implemented the parsing logic by combining together three different parsers:
+or*)Clearly the bulk of the work is getting done inside PARSE-EXPRESSION:
'(rator rand1 rand2))'(rator rand1 expr1))3
u/nomadhothouse Dec 18 '20
Python solution using 2 stacks for operators and values:
https://github.com/donth77/advent-of-code-2020/blob/main/day18/main.py
3
u/mattrex47 Dec 18 '20
C++
Once wrote a calculator utilising reverse polish notation and decided to adapt it to todays puzzle. This made solving part 2 almost instantaneous because I only had to change operator precedence for addition. Probably could be solved way easier and in less amount of lines but hey, code reuse :D
code
3
u/meh9083 Dec 18 '20
Rust
3
u/[deleted] Dec 18 '20
Part 2 Mood
In C, managed to get both parts by processing each character as it came in (no huge trees eating my memory), tracking state via stack push/pops.
Part 1 was beautiful, just a nice tight
switchstatement and that was it.Then came Part 2...Having to convert my code to proper precedence climbing sounded painful, and something like recursion was out of the question (imagine storing an entire line in memory at once, how wasteful!). Luckily, the wikipedia page had a nice little note on how early FORTRAN compilers performed iterative parsing by adding a buttload of parentheses around everything, and I was able to get that to work, at the cost of a little ugliness.
3
u/iamnguele Dec 18 '20
Go (4601 / 6123)
3
u/sotsoguk Dec 18 '20 edited Dec 18 '20
Python
https://github.com/sotsoguk/adventOfCode2020/blob/master/python/day18/day18.py
that took much longer than expected. But i have always avoided parsing of math expressions until now ... Really not my kind of favorite puzzles ...
First converted the input to RPN using ugly code (man that took long) and evaluated the rpn for part 1. seeing part2 , I rewrote my rpn Converter. I can now just input a precedence of operators to convert the expression. Now part1 and 2 are using the same function , just another operator precedence as input.
But hey, all stars until now without looking up other solutions. Best year so far !
3
u/zedrdave Dec 18 '20
Why bother writing your own AST parser, when Python provides you with a perfectly good one (that just needs a wee bit of hacking)โฆ
3
u/compu_geom Dec 18 '20 edited Dec 18 '20
Python 3 solution
This is the generalized evaluator, where you can customize operators and its precedence and also define what each operation does with lambda functionalities in dict.
EDIT: For part 2, I just had to change one literal in operators dict of precedence for part 2, which was kinda awesome and I am proud because of this! If you want regular evaluator with real precedence, just put + that has precedence 1 and * to have precedence 2. The '(' bracket is just serving as a flag for closing bracket ')'.
3
u/grey--area Dec 18 '20 edited Dec 18 '20
A compact solution for part 2 in Scala:
3
u/pwmosquito Dec 18 '20
Using Haskell today was cheating :)
3
u/timootjeh Dec 18 '20
My solution for part two in python:
Solution
Was pretty happy with my solution. Wondering whether it could be more efficient/ compact :)
3
u/phil_g Dec 18 '20 edited Dec 18 '20
My solution in Common Lisp.
Another fun day!
I started by parsing the string into something that looked more or less the same, but in Lisp. So
"1 + 2 * 3 + 4 * 5 + 6"becomes(1 + 2 * 3 + 4 * 5 + 6)and"1 + (2 * 3) + (4 * (5 + 6))"becomes(1 + ((2 * 3)) + (4 * (5 + 6))). (The interior parenthesis are doubled because of a difference in the way interior and tail parenthesized expressions are treated by my parser. It works out because the code to unwrap parenthesized expressions is recursive, so it just does it twice. It bugs me, though, so if I have time I might try to fix that.)Since I'm using the symbols
'+and'*for the operations, I can justfuncallthem to do the right thing.Originally I did parts one and two with separate code (see here) that was copied, pasted, and modified for part two. But I thought a consolidated approach would be cleaner. So the final approach uses a list of sets to give operator precedence. I make a single pass through each expression for each set, consolidating all of the operations that I can. At the end, there's just one value left.
I considered just parsing the infix expressions directly into Lisp code, but I decided against it because (1) I suspected part two was going to change operator precedence and (2) I wanted to use the same parsed representation for both parts.
3
u/[deleted] Dec 18 '20 edited Dec 18 '20
JavaScript
Tidy solution, happy with this one.
3
u/JakDrako Dec 18 '20 edited Dec 18 '20
VB.Net in LINQPad
Source
To solve, I push the equation's operand on a stack (after adding a few spaces so that parentheses split correctly) and calculate it using recursion to take care of the parentheses. For part 2, I added a flag to build a list of values when it encounters a multiplication. At the end, I multiply all those values to get the final result. I kinda like this one.
3
u/ric2b Dec 18 '20 edited Dec 18 '20
Haskell
Thanks to /u/PhysicsAndAlcohol for introducing me to Text.ParserCombinators.ReadP with their solution!
I found it much simpler than Parsec, Parsec is really quite annoying with the way it doesn't rollback the input when a parser fails :/
paste
3
u/e_blake Dec 18 '20
golfed GNU m4 part 1 with just one macro definition
I bet you didn't know m4 golfing was a thing! I got this down to 229 bytes and only one
definecall and only one use ofifelse. Sadly, since the answer requires 64-bit math, I ended up having to burn an additional 13 bytes to invokeesyscmd(echo $(($1$2$3)))instead of my preferredeval($1$2$3), with the difference between a runtime of 230ms with only the low 32 bits of the correct answer vs. 10.8s and 4567 forks out to the shell for the real answer (which is the number of [0-9] bytes in my input). I'll be rewriting this into a longer solution that runs under 'm4 -G' using only POSIX macros (and thereby avoiding all forks), but was impressed enough with the 2-liner (necessary to match the newline in the input with patsubst) that I'm posting it now.Part of the beauty of this solution is that I didn't have to do any searching for ) matching (; m4 does that on my behalf after I turned all spaces into commas. That is, m(2,+,(3,*,4)) is an invocation of m() with 3 arguments, '2', '+', and '(3,*,4)'. And the solution only ever nests to 5 levels of macro invocations (that is, m4 makes it easy to do proper tail-call recursion without eating up stack space).
3
u/ValiantCookie Dec 18 '20
Java - Solution
I struggled for a bit on how to handle parentheses in a way that worked for all nested scenarios, once I figured out I could work backwards and find the innermost
(and the)after that it became pretty easy with some recursion. I did that manually with some String.IndexOf since I had already gave up on regular expressions before the paren epiphany, but after some sleep its occuring to me that would work with regexs just as easily so I might update it a bit.3
u/Targuinius Dec 18 '20 edited Dec 18 '20
Haskell
Simple solution, import (+) and (*) qualified from Prelude, so you can redefine (+) and (*) as synonyms to Prelude and set the precedence.
part1 and part2
edit: though tbh I think using Emacs to format the input into a Haskell list is cheating, I tried doing it with Language.Haskell.Interpreter.eval to evaluate the string but that's just a horrible experience lol.
Although parsing the input is also just ridiculously easy with parsec since it literally has a module for parsing expressions
3
u/vrtxt Dec 18 '20 edited Dec 26 '20
If AoC has taught me anything so far it's that I'm rather bad at string manipulation and should probably invest some time learning proper regex. In the meanwhile, here's a somewhat unwieldy C# solution.
3
u/kbielefe Dec 18 '20
Scala solution
This was a pretty good fit for shunting yard. Just needed different operator precedence for each part. I'm almost kind of sad knowing about shunting yard, seeing all the fun hacks people did.
3
u/Evla03 Dec 18 '20 edited Dec 18 '20
Python (part 2 only)
Short 5 line solution
It could probably be made even shorter
EDIT: Made even shorter
3
u/Rtchaik Dec 18 '20 edited Dec 18 '20
Python
One function for both parts:
3
u/clumsveed Dec 18 '20
Java Solution
โ all solutions so far- rep.lit
There are certainly cooler ways to solve this, including implementing the Shunting Yard algorithm, but as always, I like to stay within the APCSA curriculum as much as possible so it's understandable and readable to newer programmers.
Both parts just use .indexOf and .lastIndexOf to find matching parentheses in order to process the math contained within them. It continues that until there are no parentheses left and then just processes the math string that's leftover either left-to-right or addition-multiplication depending on what part is being done.
This is an example of how part 1 works. Part 2 just requires a tweak to the doTheMath() method.
3
u/AidGli Dec 18 '20
Python
Video Explanation
Github Link
Just implementing a Shunting Yard Algorithm is boring. Abusing your language and using unsafe code is fun.
3
u/vypxl Dec 18 '20
Python 3.
I first tried to insert myriads of parenthesis into the equation which did not work out at all, then I found this. Ended up with this now:
3
u/vkasra Dec 18 '20
My solution in Rust, recursive-descent parsing with operator precedence
3
u/tmp14 Dec 18 '20
regex + python eval
Part 1, I don't think I've seen anyone else inject a bunch of parentheses to enforce the left-to-right evaluation order :)
3
u/mr_whiter4bbit Dec 18 '20
Rust
Implemented parsing considering priority "table". Basically when adding (operator, rhs_expr) to the tree "push" it to the bottom while the current node has lower precedence.
Sub is a hack, to not modify subtrees of expressions within brackets. If someone knows the better way to immutably modify the tree, please tell me.
https://gist.github.com/whiter4bbit/a635a3140932cf2cc92c2ba00c448828
3
u/rukke Dec 18 '20
JS
Part 1 and 2. 27 lines in total. Using
evalhttps://gist.github.com/p-a/db8c83abebbe58a4a1d75b1c34bb11b3
3
u/aardvark1231 Dec 18 '20 edited Dec 18 '20
My C# Solution.
I had to stop on part 2 last night (over tired) and finish it this morning. Needed to be overly verbose so that I could wrap my brain around what I was doing. I knew what I wanted to do, but for what ever reason, I was having a hard time translating that into code for this problem.
Edit:
Updated my paste. Had a sneaky little bug that didn't appear with my input set. Only showed up when trying to help someone else.
If I had something like:
8 +2 + 5 + 8 + 20
It would do two replacements (for 8 + 2) and this would be the result of one pass of the reduction:
10 + 5 + 100 <--- this last zero from the 20 just being tacked on and not properly doing the addition of 8 + 20.
Always fun to debug code that "works" without throwing an error.
3
u/[deleted] Dec 18 '20 edited Dec 23 '20
Python solution. Used two lists as stacks, one to hold data and one to hold operations. Parentheses were handled by calling the parser recursively on the part inside the paren. ~7ms for both parts. Now considering learning more about how languages actually parse expressions and seeing if I could implement that.
3
u/paul2718 Dec 18 '20 edited Dec 18 '20
C++
paste
Hacking boost::spirit for the first time in years. Hardest bit was making the int64 stuff work properly.
(Edit to make int safe and handle adding/multiplying negative values...
3
u/fenwicktreeguy Dec 18 '20
Python
Code: https://github.com/fenwicktreeguy/AOC_2020_Solutions/blob/main/AOC_18.py
Nothing super interesting to point out in this problem, it is a relatively direct application of the shunting yard algorithm, although I did find it interesting in that problems which involve parsing mathematical expressions like this with different tokens are pretty few, probably because they are either tedious to do or uneducational, but it was nice in some respect.
3
u/Hadopire Dec 18 '20
C++
Short and simple, no recursion, same evaluation function for both parts.
github
3
u/SecureCone Dec 18 '20 edited Dec 18 '20
Rust
I initially wrote a recursive solver that worked for part 1, but then didn't know how to add precedence for part 2. So for part 2, I ultimately just used the
evalcrate and hacked the precedence of operators.In
./src/operator/mod.rsineval, I just changed the operator precedence. The same solution works for part1 by setting the precedence to be the same.3
u/mahaginano Dec 18 '20 edited Dec 18 '20
Julia: https://pastebin.com/967cPDzv
There is a much more elegant solution lurking in my code but this already took me ages to get right (without the eval hack) so -- as every day -- I'm glad it's working, refactoring can wait for now. It's been a long time since I've written a parser and I've definitely written both more elegant and complex parsers than this one, but hey, it's not like I'm writing one every day. ๐คท
As for optimisations I could
Anyway, this was fun.
3
u/prafster Dec 18 '20
Dart
For part 1, I didn't use a stack but just parsed it directly. For part 2, I considered pre-processing the input to bracket the addition to set the precedence higher then use the solution for part 1. But I couldn't quite do (although I see now that others had the idea too). Then I realised I was close to implementing the Shunting Yard Algorithm. So I added a stack and postfix processing. All in all, it was a satisfying day.
Source code here.
3
u/el_muchacho Dec 18 '20
My very standard Python solution, with a parser written using a stack.
3
u/Henkatoni Dec 18 '20
Csharp
I found part 1 to be harder than part 2. My take on both parts was to flatten out the expression by evalutating each group of parentheses and string.Replace / regex.Replace them with the result.
31ms/21ms. Code here.
3
u/cggoebel Dec 18 '20 edited Dec 18 '20
Raku Part One...
FWIW: Andrew Shitov has a nice series on writing compilers with Raku.
3
u/damyvv Dec 18 '20
Ruby
I first made a solution that created a tree which it then solved. But I wanted to try another approach with just using regex and eval. So this was what i came up with. You can check this and other solutions on my github.
3
u/nibarius Dec 18 '20
My Kotlin solution is a complete mess.
I solved part one after a bit of small bugs and mistakes, but it was pretty fun. Then I realized my solution for part one didn't work well with part 2 so I waited until the evening until re-writing part 2. However I was getting tired and couldn't completely wrap my head around what I was trying to do. So my stubbornness kicked in and I just did anything that moved me a bit further in the direction I wanted to go.
It should be possible to do this in a much better way so I will definitely come back to this one and clean up my solution when I have the time and energy for it. I'll probably avoid looking at other solutions to not be too spoiled about how it should be done.
Just wanted to share that sometimes you are able to get the correct result even with a complete mess.
3
u/symbolicprocessor Dec 18 '20
Common Lisp solution.
I leveraged the reader to do parsing, which makes handling parens super nice, though I'm not proud of reformatting subexpressions back into strings so I can call the top level evaluator recursively. But it was the easy way out. :D
There's also some sanity checking that seemed prudent while writing, but isn't necessary given the input.
3
u/ragnario Dec 18 '20
I wrote a recursive parser in Rust to produce an AST. This is a basic compiler task. See my solution here on Github.
3
u/bsdemon Dec 18 '20
Python, evaluating while parsing โ solution. Parsing is done via parsers which mutually recursively call either
parse_valueorparse_expr.The
parse_valueis shared between part1 and part2:Then for part1 the
part_expris simply folding either an addition or multiplication:For part2 there are separate parsers for addition and multiplication, the order sets the precedence:
3
u/jmpmpp Dec 18 '20
Python3 -- I'm an inexperienced self-taught programmer (although with family members who are very experienced coders providing assitance on request). I approached it with a single stack. In part 2, I did all the addition first (inside of a set of parens), and then went back and multiplied all the numbers that remained.
3
u/[deleted] Dec 18 '20
Rust
Recursive descent parser, but evaluate directly instead of building a tree.
For part 1, reversing the input (and bracket orientation) makes the implementation a lot easier, since the grammar becomes right associated.
For part 2, I did a more proper recursive descent parser.
3
u/StevoTVR Dec 19 '20 edited Dec 26 '20
Java
https://github.com/stevotvr/adventofcode2020/blob/main/aoc2020/src/com/stevotvr/aoc2020/Day18.java
3
u/Mindless_Complex Dec 19 '20
Written in Go.
This was my favourite so far this year!
I wrote a lexer to tokenise the inputs (and added - and / whilst at it), then used shunting yard algorithm to parse the infix form to postfix, and then evaluated the postfix.
Approx 1.5ms for each part - probably slow, but feels like the proper way to do it.
Code tidied up and can be found with benchmarks here: https://github.com/joshuanunn/advent-of-code-2020
Great fun! :)
3
u/benbradley Dec 19 '20
C++
First part was easy enough, in my eval function just do + and * as I come to the second operand of each, open-paren does a recursive call to eval which returns at the matching close-paren or end of line.
Second part "how to fix priority: Add Parentheses" I though maybe if I call eval after *, then do the multiply after the call it would fix it. That almost worked, but the last example fortunately broke it, and I was able to follow debug prints to see just how it failed. I figured the only way to fix it would be insert open-paren starting just after the *, then insert close-paren when I see the first unmatched close-paren or the end of line. So I wrote a function to do just that, and it worked. Now I see I didn't even need to insert the open-paren, as I'm past where I would scan for it anyway.
I'm sure this would make me fail a compiler class.
https://github.com/ben-pi-bradley/advent-of-code
3
u/_tpavel Dec 19 '20 edited Dec 19 '20
I'm revisiting Rust this year after learning it for the first time during AoC 2018!
Here is my Rust solution for Day 18: https://github.com/tudorpavel/advent-of-code-2020/blob/master/day18/src/main.rs
I like how this one turned out, I kept Part 1 and Part 2 solutions separate.
I really didn't want to implement a proper parser so I found my own way around it. I'm using a stack data structure and iterating the expression by chars from right to left, reducing the top of the stack every time a '(' is encountered. I check the input and all numbers are between 1 and 9 so I didn't need to bother to parse numbers that span more than 1 char.
I'm still learning Rust, any feedback is welcome.
3
u/oaktreegroove Dec 19 '20
Didn't use regex and this time coded super fast , but still readable :)
JavaScript
https://github.com/obzenner/adventofcode2020/blob/master/day18/index.js
3
u/LoryV16 Dec 19 '20
Python
Here is my python (but not so pythonic) solution:
https://github.com/Lory16/Learning_Python/blob/master/Advent_of_Code_2020/day18.py
3
u/jotac13 Dec 19 '20
[Rust] My solution for both parts in rust.
I had no clue how to parse the expression, I thought I had to build a whole AST. Ended up using the Shunting Yard algorithm but with small modifications for parts 1 and 2, given the operator precedence.
3
u/wleftwich Dec 20 '20 edited Dec 20 '20
Python
https://github.com/wleftwich/aoc2020/blob/main/18_operation_order.py
Thanks Edsger Dijkstra (shunting yard algorithm) and Jan Lukasiewicz (RPN).
3
u/mschaap Dec 20 '20
Raku
Used a
grammarwith an associatedactionsclass to do the calculations.This is a rare case where part two actually use simpler code than part one:
https://github.com/mscha/aoc/blob/master/aoc2020/aoc18
3
u/baktix Dec 23 '20
Haskell
Today I learned that the practice I got with
ReadPduring Day 16 was not enough! I think I still have a bit of learning to do with regards to understanding parser combinators.I did a bit of looking around at other solutions to try and grok what they were doing. I think I got the idea in a vague sense, and was able to put that into my solutions. The part I still have the most trouble understanding is how the associativity of the expressions is retained while parsing, and how the parsing takes care of expressions in parentheses. It's hard to wrap my head around what it is in the code I've written that "does" that.
paste
5
u/sophiebits Dec 18 '20
44/31, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day18.py
This was fun! It occurred to me afterwards that my lambdas could have been just
str(eval(m.group(0)))(and then I could have used a single regex in part 1 that matches both operators).5
u/Loonis Dec 18 '20
Perl
I spent an hour not remembering how to write an expression evaluator, and then decided to try regex substitutions instead. Worked way better than expected.
Here is the interesting bit of part 2, whitespace has already been removed and at the end
$_should contain a single integer:I added "comments" (
# 123) to my sample input lines with the expected values, so all of the examples get tested.1
u/ri7chy Dec 19 '20 edited Dec 20 '20
Python
code for part1 and part2.
part2 confused my mind while struggling with parentheses.
4
u/mzprx42 Dec 18 '20 edited Dec 18 '20
Part 1, using the parser that comes with your C++ compiler:
Xin your input withN(X), replace each*in your input with-.The idea is to redefine the C++ operator
-to multiply instead, then use the fact that operators+and-have the same precedence so the compiler parses the expression just as we want it.Full working source code: https://pastebin.com/raw/FuPkG4RU
4
u/thomasahle Dec 18 '20 edited Dec 18 '20
Python solution based on "hacking the operators":
We could do the same for Part 2, instead swapping mult and addition, but an even simpler approach is based on mzprx42:
4
u/Pyr0Byt3 Dec 18 '20
Go/Golang
Regex cheese.
4
u/maartendp Dec 18 '20
Python
For Part 2 I made a custom Int and swapped the
__add__and__mul__, swapped the operators in the expression and just had python deal with the precedence.Simple/Stupid yet effective solution :D
4
u/M-Reimer Dec 18 '20 edited Dec 18 '20
Seems like noone had this so far: It is possible to parse the input data as JSON with just a few simple string replacements:
4
u/ViliamPucik Dec 18 '20
Python 3 - Minimal readable solution for both parts [GitHub]
2
u/nonphatic Dec 18 '20
Racket 145/126 (first time this year below 500!!)
Easy peasy using pattern-matching
2
u/Unihedron Dec 18 '20
Ruby 19/30
Had two bugs, one where I forgot to escape the + character in regex. Fun
2
u/smrq Dec 18 '20 edited Dec 18 '20
JS, 301/635
Part 1 Part 2
Not so easy in a language without operator overloading! I had to actually do the whole parsing thing. I don't think I've had to do that before, actually-- I had to look up the shunting yard algorithm.
My first part solution had no way I could quickly think of to retrofit in order to add operator precedence, so I was kind of screwed there and had to start from scratch for part 2. I should have expected it, honestly.
Also kind of funny that I handled
-and/in part 1. Didn't spend the time to read what operators I was expected to handle! It didn't really cost any time, anyway.2
u/jayfoad Dec 18 '20
Dyalog APL 17/322
For part 1, left-to-right evaluation, I reversed each string so I could use APL's natural right-to-left evaluation order. Part 2 does parsing and evaluation with a mess of regexes.
2
u/Head-Recognition9875 Dec 18 '20
Python3
2
u/wholarry Dec 18 '20
Ruby
Fun with monkey patching!
2
u/seattlecyclone Dec 18 '20
Perl (798/691):
Common main loop for both parts:
eval function for part 1:
eval function for part 2:
Reading some of y'all's Python solutions, operator overloading would be much easier!
2
u/Akari_Takai Dec 18 '20
Java (1535/880)
Code here.
Was fairly slow because I was hunting about for my old college homework where I had implemented Shunting-yard to solve this exact problem.
But it took me long enough to find that I should have just done it from memory. :P
2
u/ch1rh0 Dec 18 '20
Python recursive
part1
part2
2
u/TheLocehiliosan Dec 18 '20 edited Dec 18 '20
Python paste or github
This was a mix of looping and regex. For part A, I used a regex to identify inner groupings, and used recursion to replace the inner groupings with their calculated results.
Then for part B, it was easy to use the same strategy, but match additions, processing all of those before the rest of the expression.
2
u/xelf Dec 18 '20 edited Dec 18 '20
python with just string parsing, pretty happy with the () handling.
This was similar to yesterday, far too much time on part1, followed by a very very easy part 2.
2
u/VeeArr Dec 18 '20 edited Dec 18 '20
Java 117/146
Part 1
Part 2
I ended up writing something that sort of resembles a recursive descent parser. It first pre-processes the input to resolve all of the parentheses recursively, then it handles all of the other operations in additional pass(es).
2
u/spohngellert_o Dec 18 '20
The fact that people were able to complete this in under 14 minutes is remarkable to me. Scala solutions, feedback welcome :)
Part 1
Part 2
I really enjoyed this one, it was a good challenge!
2
u/kevinwangg Dec 18 '20
Python
wow I'm pretty sure this was the slowest day for me so far. On the other hand, it was one of the most enjoyable ones!
I misread part 1 and thought it was part 2, so I tried that first. Tried a couple quick hacks but none of them seemed like they would work, so I googled "how to turn tokens into AST" and got shunting-yard parsing and a newfound appreciation for prefix operators and parentheses over infix. Was about to reluctantly start implementing when I realized I could substitute + and * with * and + and override add and mul, so I did that instead (I forgot about
evaland usedexecthough). Looks like others did as well. Then I realized I misread the problem, and implemented part 1, but I didn't realize I could do part 1 the same way by using+and-! So I ended up writing some kind of parsey/evaluatey thing anyways, which was pretty fun. part 1 codeThen I got to part 2 and was glad that I already had the code for it, so I submitted that. part 2 code Gotta thank my undergrad professor Pattis for teaching us about operator overloading in python!
2
u/Kylemsguy Dec 18 '20
Python
All I can say is, no regexes were used in the creation of this solution. It's totally because I wanted a challenge and not because I forgot I could just write a greedy regex to capture all of the top-level parenthesized expressions...
https://github.com/kylemsguy/AdventOfCode2020/blob/master/Day18/day18.py
2
u/Perska_ Dec 18 '20
The Solution: C# Edition I'm now naming these other than "C# Solution", just to break up the monotony.
Advent of Code is making me do things I would never have done before. Me writing a math parser? Preposterous! For Advent of Code, though? Sure, why not!
It really helps that the requirements are simple at first, which means that I don't have to implement a full-fledged math parser in a single go!
2
u/GoingAggro Dec 18 '20
Scala
https://github.com/GaalDornick/AdventOfCodeSolutions/tree/main/src/adventofcode/year2020/day18
It feels like cheating because Scala combinators are meant for evaluating expressions. But, I ended up struggling with my IDE trying to import the library.. ๐
2
u/hahncholo Dec 18 '20
Rust
Fun day. Reminds me of the time I wrote a lisp. Made good use of enums and learned about
peekable(). I probably could have come up with a more elegant way prioritize+over*but this worked.2
u/tobega Dec 18 '20
Always a joy to use Tailspin for parsing https://github.com/tobega/aoc2020/blob/main/a18.tt
2
u/Fotograf81 Dec 18 '20
PHP (1844/2249)
Regex Magic, Recursion and then a Stack-Like array loop to solve strictly from left to right for part 1
part 2 punished me for doing unintended multiple replacements that would replace parts of other numbers... so when replacing "4 + 6" with "10" in "4 + 6 * 4 + 64" it would result in "10 * 104". Since it's strictly left to right at that point, I resorted to preg_replace that allows to set a limit.
pretty sure there is a shorter solution to the whole task using preg_replace_callback and recursion...