One more week until Christmas! Hopefully all of the code is leaving you extra jolly rather than grinchy. Let's take today to meditate on all of the blessings in our lives. 😊 Also, fun fact: Haskell was the top submitted language yesterday! Go functional languages!
The Puzzle
In today’s puzzle, is all about math. Side note: I 100% knew what the video linked in the beginning of the instructions was going to be before I clicked on it. Math is math! Why would they change math!? Well, today, it's no longer "Please Excuse My Dear Aunt Sally." It's "Left to Right No Matter What. P.S. Suck It."
I'm excited to write this parser. Let's get to it!
The Leaderboards
As always, this is the spot where I’ll plug any leaderboard codes shared from the community.
Ryan's Leaderboard: 224198-25048a19
If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.
Yesterday’s Languages
Updated 07:43AM 12/18/2020 PST.
Language | Count |
---|---|
Haskell | 2 |
Perl | 1 |
Ruby | 1 |
Python | 1 |
JavaScript | 1 |
Merry Coding!
Top comments (10)
My Haskell solution. It uses the shunting-yard algorithm to convert it to a postfix string and then evals the postfix string. Today's part 2 was obvious the moment I read part 1 so I went for this approach. So to solve part 2 I only had to change a
2
to a3
. Took 24 seconds from submitting the answer to part 1 to submitting the answer to part 2.It's a syntax parsing problem, right? So we just use PEG to parse it like we would any programming language. This takes away the heavy lifting of implementing parsing of individual characters, and let the library deal with all the recursion and traversal, leaving us to just provide methods which get called to evaluate the nodes of the AST as it traverses. The result is some clean and compact high-level code:
Took me a while to dig through some docs to find what I wanted, but I wrote a parser in F# using
FParsec
.Javascript solution part 1, I'll see what I can do about part 2.
I used iteration to solve this instead of parsing algorithm
thingamajigs
, and now I feel I should have gone that way :/Minified,
My Perl solution. I used the Marpa::R2 library to write a parser. It supports rule precedence, so solving the part 2 took me just a minute.
For part 2, the DSL is
At first I wasted some time trying to get my parsers to produce an expression AST but they're not that advanced. Tokenising the text and using Dijkstra's shunting yard algorithm was a much better approach. I was also pleased to avoid copying token objects in the shunting yard algorithm - it just returns a new vector with the same objects the parser output, just reordered. Efficient!
Today's problem is the perfect candidate for using a recursive divide-and-conquer approach
Basically what I did is to solve the innermost expressions in the parenthesis and use this partial result to solve the outer expressions recursively. In case of part two, it is a bit trickier, since there is operator precedence. In this case when I encountered a multiplication, I've split the expression in 2 parts, basically solving the additions first and applying the multiplications afterwards for the partial results.
Here is my code in Java. It's a bit hefty, because Java, but it does the job:
All my solutions can be found at: github.com/Ernyoke/advent-of-code-...
Well today was done in less that 10 minutes, which I have to say was nice as I had a lot on today :-) Parsed expressions into AST, as I have multiple Haskell parsers for DSP programming languages that I've developed over the last few years and so it was a simple cut paste, rename, and factorize for part one and two to work with the same parser.
Here's my solution. Doesn't quite support arbitrary levels of precedence, but we only needed two max, and that's what it works for. I'm comfortable with the knowledge that I could probably have put together an arbitrary precedence interpreter together if I had needed to. 😁
My JavaScript walkthrough:
I've used a bunch of regular expressions and it helped keep my code small :)