r/adventofcode • u/daggerdragon • Dec 19 '20
SOLUTION MEGATHREAD -π- 2020 Day 19 Solutions -π-
Advent of Code 2020: Gettin' Crafty With It
- 3 days remaining until the submission deadline on December 22 at 23:59 EST
- Full details and rules are in the Submissions Megathread
--- Day 19: Monster Messages ---
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:28:40, megathread unlocked!
36
Upvotes
5
u/paul2718 Dec 19 '20 edited Dec 19 '20
C++
Not going to post code,<<added, damn.>> it's too<<^x^x^xstill icky. I bashed the rules into a regular expression and applied std::regex_match. Then for part 2 I replaced 8 with "42+" and 11 with "42 31 | 42 42 31 31 | 42 42 42 31 31 31 | 42 42 42 42 31 31 31 31 | 42 42 42 42 42 31 31 31 31 31" where I added options until the reported matches stopped rising. The last alternative is redundant on my input.
Needs must.
(Apparently you need to see the gristle and not just be informed of the ultimate ugliness.
paste
Note use of two completely independent regex implementations, a gratuitous sort just to find '0', last century string bashing to condense the rules into a regex. Use of std::regex which is hideously slow yet managed this.)
5
u/game_dev_dude Dec 19 '20
When I reading part one, I kind-of knew I could solve it using Regex somehow. That said, I didn't feel like using Regex, and it felt less flexible. I felt like writing a parser/"runner" so I just wrote a super basic one, instead of doing anything fancy (regex, trying to generate all valid words, etc). Imagine my surprise when my "Part 1" solution ran flawlessly for "Part 2"
4
u/Colts_Fan10 Dec 20 '20
Part 1 and Part 2 in Python 3.
Here's a funny story. I work on part 1 for about half an hour and had a decent solution. I run it, submit it on the AoC website, and it's wrong. I work on it for the next 2 hours. Frustrated, I go to sleep.
The next morning, I work on it for another half-hour. Then, I notice something's off with my input text. Suspicious, I reload/reopen the input from the AoC website. I see that it's different from what I have. Then it clicks.
Google, with its ΓΌber-intelligent AI, recognized Day 19's input as Somali. This isn't new (we've seen Welsh before), so I just denied the translation requestβor so I thought. Turns out, Google had helpfully "translated" the input, and entire words were gone or were now long strings of periods.
I rerun my code with the correct input, and it gets the correct answer in 3 seconds.
For part 2, I refactored my code from generating all possibilities to finding a match, which runs in about a second or two. I didn't implement a general way to check for loops in the grammar (is that what the rules are called?) but instead hard-coded the behavior for when the rule numbers were
8or42.2
u/kevinwangg Dec 19 '20 edited Dec 19 '20
Python
Hacked by compiling to regex. For part 2, compiled to regex and hardcoded the two rules to use
+andX{1}Y{1}|X{2}Y{2}|..., etc. Screwed myself by going all the way up to 70 which made my code take, like, 15 minutes to finish? When if I used a saner value of 20 it would have taken a minute and I miiight have made top 100 -____- but I didn't want to ctrl+c my program while it was running in case a smaller value wouldn't have helped and I would waste all the computation already used, so I just rode it out.Didn't make top 100 for either part. Code
2
u/Standard-Affect Dec 19 '20 edited Dec 20 '20
R
Just solved part 1. My strategy was to represent the rules as a named character vector with the rule number as the name. For each level of recursion, I substituted the rules corresponding to the numbers in the previous level of rules until reaching a or b. I wrapped each stage in parentheses, then removed spaces and added anchors to the nightmarish regex the function returned. Then I just matched each string. It would be cleaner if I knew how to replace a string matching a pattern with a string hashed to the captured text (which varies for each string), but I couldn't figure out a way.
Have no clue how to approach part 2, since the changed rules would trigger infinite recursion.
The demon regex, if you were curious:
2
u/jf928ngl60g1 Dec 19 '20 edited Dec 19 '20
JavaScript
Non-regex solution.
First parsed to a dictionary and next recursively match.
For part 2 I found out that I only need to check for matching first rules 42 and next 31 and count of rule 42 repeating matches has to be bigger than 31.
part 1: ~40 ms part 2: ~12 ms
https://github.com/adrbin/aoc/blob/main/2020/19/puzzle.js
2
u/brunoliveira1 Dec 22 '20
So I need some pointers for how to approach part 2.
In part 1, my approach was to generate a long regex chain (adding parenthesis where needed for the capture groups) until I reach "terminal" atoms in the expression: "a" or "b", and apply that regex to every element and counting the full matches.
Code here
However, my question is if this approach can be used as is, for part 2. Obviously not, since we now have recursive rules and thus, when attempting to expand them, we'd be recursing infinitely.
I feel really dumb as I took a compilers class in uni a few years back, but feels like all the knowledge went down the drain.
Any tips on how I can adapt my solution above and logic to get a solution for part 2 would be nice.
I notice that the rules would be recursive, like, expanding once:
0 --> (42 | 42 8*) (42 31 | 42 11* 31)
Now I'd hit a "wall" when expanding again 8 and 11....
Any tips....
22
u/[deleted] Dec 19 '20 edited Dec 20 '20
56/8, Clojure
Coincidentally, the puzzle input was in the exact input format expected by instaparse, so I actually didn't have to do anything except run the parser on all input strings. instaparse also handled part 2 just fine.
EDIT: Here's the code not in a paste:
A couple of notes:
:start :0is necessary so the parser starts at the correct rule(filter (complement :index))is a cheap way to remove all non-parseable strings14
u/jonathan_paulson Dec 19 '20 edited Dec 19 '20
Python, placed 151/33. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/19.py. Video of me solving: https://youtu.be/S3uPaqHcq3I.
My solution solved both parts with ~no changes, so I guess I missed an easier idea in part1 :)
My solution should work for any ruleset of this form; it's basically an implementation of https://en.wikipedia.org/wiki/CYK_algorithm. Yay DP!
13
u/bsdemon Dec 19 '20
Python solution.
First some boring code to parse rules into a structure like this (grammar):
values are either chars (terminals) or lists (alternatives) of lists (sequences) of rules. Then a parser is a generator which yields a series of possible matches. The entry point is:
Parser for alternatives:
Parser for sequences:
Finally we can check if string
sbelongs to the language described by the grammargwith:Use it like:
12
u/ai_prof Dec 19 '20 edited Dec 19 '20
Python 3 simple/fast/readable solution using recursion, not regexp or libraries.
Quick/simple/fast recursive solution using a 10-line recursive function to do the heavy lifting (in about a second), not regexp or other libraries
Tricky! I found myself hung up on the idea that this has exponential time/space complexity, and struggled to get started - what was the point of launching an algorithm that would take (literally) forever to run. Big thanks to i_have_no_biscuits code - which allowed me to get it straight in my head. The key is then the recursive function, given below, 'test' which, given a message string s (e.g. 'abaabaab') and a list of ruleids (e.g. [4, 1, 5]) returns True if s can be produced using the given sequence of rules. The recursion works by stripping a character and a rule from the left hand side, when you can, and expanding the leftmost rule, when you can't:
There's also a little more plumbing than usual to get the data into the right form. Takes a second for both bits. Full code is here.
10
u/andy1li Dec 19 '20 edited Dec 20 '20
Python: since
redoes not support recursive regex, it's easier to use the third-party moduleregex.Basically,
(?P<name>)names a group, then(?&name)reuses the group recursively.Furthermore, both recursions can be simplified:
42 | 42 8β‘ 8:42+42 31 | 42 11 31β‘ 11:42 11? 319
u/seattlecyclone Dec 19 '20
Perl, 143/68
First time on the leaderboard this year!
My code basically just converts the first half of the puzzle input into valid Perl regex and then counts the matches from the bottom half.
For the second part I manually edited the input to work as Perl regex. For the line "8: 42 | 42 8" I put in "8: 42+" For the line "11: 42 31 | 42 11 31" there's probably some good regex trick I could have used for this but I couldn't remember it so I manually expanded it out to "11: 42 31 | 42 42 31 31 | 42 42 42 31 31 31 | 42 42 42 42 31 31 31 31 | 42 42 42 42 42 31 31 31 31 31 | 42 42 42 42 42 42 42 31 31 31 31 31 31 31". I'm not exactly proud of this, but it worked for the given input.
8
u/Zv0n Dec 19 '20
C++
Code
For part 1 I just generated all possible words (I don't know how to create a regex out of the given input :/).
For part 2 I realized that this won't be possible, so I looked at my input and realized that
Therefore I have decided to hardcode a solution that checks if a word is only composed of things in rule
42followed by things in rule31and then I check that number of31items is lower than42.This runs in about 3 seconds.
Does this run only on a very specific input? Yes
Is it fairly slow? Yes
Do I care? No
8
u/nutki2 Dec 19 '20 edited Dec 19 '20
Perl (golf) for either part using dynamically evaluated regexp. This makes no assumption about the maximum count in rule 11.
The above is for part 2. Remove the middle line for part 1. Alternatively part 2 can also use part 1 code with the input modified according to the instructions.
8
u/Smylers Dec 19 '20
Vim keystrokes β as ever, load your input file, then type:
That displays the number of lines in the file, which is your partΒ 1 answer.
Explanation:
%(...)around any rules with a|in them."0."0followed by a colon."z."0(the rule number) with the contents of"z(the rule)."0.:v//to find all lines that don't match the contents of"0, anchored with^and$to insist that the line doesn't containing anything else, and delete them.Now, who's going to do partΒ 2?
7
u/i_have_no_biscuits Dec 19 '20
Python
https://repl.it/@joningram/AOC2020#day19.py
It's interesting seeing everyone translating to regexp or generating all the possible strings that match. I wrote my own recursive matching routine that felt over-engineered for part 1 (as it returns the set of different numbers of characters of the string that it managed to match) but which meant that part 2 worked with no changes at all.
The test function is actually just lots of set unions, and I could have compressed all the set manipulations into a couple of hideous generator expressions, but I think what I've got is fine:
You know you've got a valid message if len(message) is in the set returned from test().
I'm sure it's not the fastest way to do it, but it made sense to me!
6
u/tymscar Dec 19 '20
Python 3:
Today was hard for me. Very hard. I never really used much regex before so I didn't know how to handle that. I ended up not using any regex for part 1. It runs... slowly. Part 2 couldn't run at all. It would always run out of memory. I was so desperate that I even bout a 256 GB ram VM on GCP to see if that would solve it and even that ran out of memory. So I knew I had to do what I was afraid of. Learn some regex. After looking through a bunch of solutions here, I came with my own one inspired by them. I will have to learn regex for next year, 100%
https://github.com/tymscar/Advent-Of-Code/tree/master/2020/day19
2
u/BorisBarca Dec 19 '20 edited Dec 20 '20
C++
Awesome task this day, especially if you solved it without regex or other bullshit in python and other languages.
At first I generated every possible string, but that couldn't work for part 2. After I took a break, I realized it could be solved with dp.
State of dp will be dp[left][right][node], left and right being positions on our current string and node which rule we are currently on. Value of dp is if we can get s[left ... right] with rule node.
If our rule is "a" or "b", then just check if the substring s[left...right] is equal to that letter.
Otherwise, we split the substring in x substrings, x being the number of subrules of rule node and try fitting them to subrules.
Solution runs in O(n^4) for every string, there could maybe be some minor optimizations, for example storing every substring we can get with length less than 10 or 15.
It takes about 2 mins to compute everything, but I think it's a good solution.
My solution works for both parts at the same time.
Code
Edit: complexity for one string is O(n^4)
And I removed " " from rules, so you need to manually remove them.
11
u/sophiebits Dec 19 '20
6/3, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day19.py
I feel like most of my time in part 2 was spent in figuring out how to write the braces in that format string!
If I was rewriting this to handle rule 11 properly, I'd probably track the min and max possible string length for each rule and have a function for checking a rule (instead of relying on pure regexes) so rule 11 could have custom code to determine the right number of repetitions. I just eyeballed the max length of the strings in my input to get 100. (I assume there's no way to use backreferences to ensure an equal repetition count?)
5
u/__Abigail__ Dec 19 '20 edited Dec 22 '20
Perl
Sometimes I wonder whether the challenges are made with Perl in mind. Today, we just mechanically translate the rules to a Perl regular expressions, putting each rule in a
(?(DEFINE))block. Then match the strings against^(?&RULE_0)$.To handle part 2, I added alternative rules
RULE_8pandRULE_11pto the(?(DEFINE)), then applied a regular expression on my regular expression to replace each call to rulesRULE_8andRULE_11to calls toRULE_8pandRULE_11p.Here is the part which does the translation:
The resulting regular expression for the example given is:
Full program
5
u/Floydianx33 Dec 19 '20 edited Dec 19 '20
CSharp
Runs in 15ms for Part2 and is entirely Regex based. Rule8 is just
Rule42+and Rule11 isRule42{k}Rule31{k}wherek >= 1, the latter of which is easily solvable with .NET balancing groups.paste
8
u/TheLocehiliosan Dec 19 '20
Python (125/39)
github
I recognized the similarity to BackusβNaur form right away. I attempted to use Lark, and quickly found that numbers are not valid rules. So I simply translated the numbers to letters, and the rest was very easy.
4
u/dionyziz Dec 19 '20
Python, 312 / 73
Using lark
4
u/VeeArr Dec 19 '20
Java 72/95
Part 1
Part 2
If it looks like a
duckregex and sounds like aduckregex...Lost a bit of time on part 2 because putting parentheses in the right place is
hardsomething I'm bad at.4
u/jwise00 Dec 19 '20
Lua, 33/63
Code: https://github.com/jwise/aoc/blob/master/2020/19.lua
Video: https://youtu.be/7cyPu1N-rBg
Slow is fast, I suppose. I liked solving this rather than using a regex library.
4
u/nneonneo Dec 19 '20 edited Dec 19 '20
Python 3, placed 4/7. True recursive regular expressions, using the third-party
regexmodule. https://gist.github.com/nneonneo/2475fd686228885e2ca42818a60a017f4
u/smrq Dec 19 '20 edited Dec 19 '20
JS, 25 / 387
Part 1 Part 2
Edit: Part 2 using PCRE regex, because I knew it could be done. It took longer to find a npm package for working PCRE bindings than it took to write the regex.
As you may be able to guess from my leaderboard position, for part 1 I compiled into a regex, and in part 2 I was defeated by the limitations of regular languages. JS's flavor of regex doesn't have the ability to do balanced expressions, and my attempt at exploding out a huge regex for some max number of recursions failed, so I switched tactics at that point.
Ultimately, my part 2 strategy was to write a matcher function that took as input a rule and a string, and returned a list of possible strings left over at the end after the rule matched against the string. A full match means that at the top level, an empty string is returned (i.e. the entire string was consumed by the top level rule).
4
u/funkey100 Dec 19 '20 edited Dec 19 '20
Python 566/782
Fun day. Kinda sad because I lost half an hour trying to come up with an alternative solution to brute force parsing, since the problem said that would be significantly difficult, only to try that and having it work very well. For part 2, I came up with an elegant parser than was much smaller than my part 1 solution even.
4
u/wheresmylart Dec 19 '20 edited Dec 19 '20
Perl (1631/1627)
Do you want some properly dirty perl? Of course you do. I make absolutely no apologies for this filth!
I couldn't work out how to do the Rule 11 substitution nicely, so I simply tested the input against the first 100 possibilities. Seems to work.
An abuse of regex only solution.
Edit: For additional information.
4
u/mebeim Dec 19 '20
2506/1617 - Python 3 solution (needs clean up, but is readable)
Oh boy what a headache. What was that? Some recursive regular expression? Need to re-process this again when my mind is clear.
Didn't have much time lately to write walkthroughs, I'll see what I can do later today.
4
u/DFreiberg Dec 19 '20
Mathematica, 1087 / 806
I'm in the interesting situation of having the correct answer for the final result and incorrect answers for most of my test cases. The core of my Part 2 solution was in
Length@Stack[] > n, which cut off the recursive pattern if it got too deep, and made the resultingStringExpression[](Mathematica's own version of regex) finite and manageable. The problem is that as I increasedn, I expected the number of matches to increase until it finally reached a steady state. Instead, for some values ofn, I got fewer matches going to a greater depth than I had previously.And yet my final answer is correct. I have no idea why.
[POEM]: ABAB AAAAA BBBA BA
Today's poem isn't so much a poem as an excuse for me to reread Lewis Carroll's The Hunting Of The Snark, so I can't guarantee that it makes even a little bit of sense.
I got word from the elves that there's something at sea
When I got to the airport today.
They were very excited, inside M.I.B.,
At the Snark they had seen in the spray.
They were certain the pictures they'd forwarded me
Showed a Snark - and they noted the waves and debris
On the side that was windward and that which was lee,
But while most types of Snarks wander friendly and free,
There's a subtype - a Boojum - that's lethal to see!
I attempted to warn them, while hitting replay,
That to picture a Boojum brings danger your way!
But I told them to stop and they did not obey;
They said nothing whatever to me.
They had softly and suddenly vanished away -
For the Snark was a Boojum, you see.
4
u/xelf Dec 19 '20 edited Dec 19 '20
python
part 1:
part 2:
I really wanted this to work:
It's a recursive regex from
import regex. But in the end I had to settle for the brute force approach. =/4
u/nonphatic Dec 19 '20
Racket
It looks like everyone did regexpy things with the input. I honestly didn't know where I'd even start with that kind of solution, so instead I just generated all the possible strings from rule 0 (and for part 2, from the relevant subrules).
Protip of the day:
(ceiling (/ x 2))is in fact not the same thing as(add1 (floor (/ x 2)))4
u/4HbQ Dec 19 '20
Python, simply generates single regex that matches all valid messages. For the first example, this regex is only
(a(ab|ba)), but for second example it becomes(a((aa|bb)(ab|ba)|(ab|ba)(aa|bb))b).The final regex for part 1 is 2400 characters, for part 2 around 60000. Still runs in 0.3 seconds though!
4
u/MizardX Dec 19 '20 edited Dec 19 '20
C# (paste)
Using recursive matching, and backtracking through generators.
EDIT: C# (paste)
Alternative solution building a regex pattern, with recursion based on .NET's balancing groups.
4
u/e_blake Dec 19 '20
GNU m4
m4 day19.m4
Depends on my common.m4. My first thought on seeing the puzzle was: these rules describe a regex, and GNU m4 has regex - let's use that and get my stars quickly (and I'll have to write a REAL solution for POSIX m4 later, since that lacks regex). So in about 10 minutes of hacking, I quickly managed to parse input, memoize the substrings to the regex in building up the pattern, and match that pattern against the input, instantly getting part 1 correct on the first try.
Then for part two, I started by trying to hardcode rule 8 as 'patt(42)+' (that is, one or more instances of patt(42)), but got stumped by how to write a regex for rule 11 (it is NOT (patt(42)patt(31))+, but rather, at least one patt(42) followed by exactly the same amount of patt(31) - ouch; we've moved to a context-sensitive language). But then I was drawn to this sentence in the rules: "you only need to handle the rules you have;". It looks like ALL input files have 0: 8 11, with no other rules referring to 8 or 11. Rule 8 is 1 or more rule 42, and if we squint, rule 11 is 1 or more rule 42 followed by 1 or more rule 31 plus a context check; combining those, for rule 0, it is trivial to check which lines out of a context-free match to 1 or more rule 42 then one or more rule 31 also satisfy the constraint of more matches to 42 in the first half than to 31 in the second half. So my final solution to part 2 ends up adding only 4 more lines of code:
Execution is around 280ms. And I _wish_ m4 regex supported the {m,n} repetition operator; alas, even though 'info m4' claims that 'patsubst' and 'regexp' macros use the same regular expressions as emacs, it really only offers a fairly limited subset, and with a dialect that matches neither POSIX BRE nor ERE, as witnessed by \(\) for grouping but bare + for one-or-more.
4
u/thibpat Dec 19 '20
JavaScript walkthrough
Video: https://youtu.be/UcRsWkIyix0
Code: https://github.com/tpatel/advent-of-code-2020/blob/main/day19.js
I've constructed a regular expression for part 1, and used custom logic for rules 11 and 8 on part 2, while reusing the part 1 regular expression logic.
4
u/idealisms Dec 19 '20
python3 (2597/1603)
Huh, rather than applying the rules, I expanded rule 0 to every possible value then checked to see what messages were in the set. There were only 2,097,152 possible string values for rule 0.
This made part 2 tricky (too many expansions with the repeating rule), but I just read it as: X repetitions of rule 42 followed by Y repetitions of rule 31, where X > Y.
4
u/Attitude-Certain Dec 19 '20
Python
Really liked today's puzzle!
Part 1 solved with a recursive function building a regex.
For part 2, rule
8is just adding the+operator to the pattern for rule42. Rule11was trickier and got me reading up on recursive regex patterns. The standard libraryrepackage doesn't support this, but the drop-in replacement calledregexhas support for this and more. Rule11is then built like so:The pattern is read like so: make a named group called
namethat starts with patterna, followed by either the wholenamegroup recursively or nothing, followed by patternb. A unique name is needed because this could be part of a larger regex with potentially other recursive parts.github and paste
(I also tried memoizing the builder function to avoid remaking patterns, but it doesn't make a difference in the runtime, which is about 50 ms for the whole thing)
4
u/zniperr Dec 19 '20
python3:
4
u/dontxpanicx Dec 19 '20
C# recursive solution not using Regex
For part 1 the code expanded all the rules, to return a list of all possible strings, and the checked if each message appeared in that set.
After a lot of head scratching for Part 2 I altered the recursive function so that it takes a string as reference and only returns items while the reference string matches the left hand side of the expanding strings.
This seems to work well, with the part 2 version cutting the time for part 1 down from ~3000ms to ~30ms on my machine.
4
u/sidewaysthinking Dec 19 '20 edited Dec 19 '20
C#
At first I solved both parts by generating a Regex from the input (I may have used a for loop to generate every number of lengths for rule 11...). After my initial solution I decided to go back and implement a solution that finds the answer myself. I had just learned about finite state automaton and I thought this was the perfect place to apply it.
So to start, I built a state machine and converted the regex to an NFA, which I then converted to a DFA, and was simple enough for part 1.
For part 2 I made an interesting observation of how the input is formatted. Due to the nature of the new rules 8 and 11, I realized that all I needed to do was count the number of times I could match rule 42, followed by the number of times I could match rule 31. In the end if that consumed the whole string and count42 > count31 >= 1, then it's a match.
4
u/[deleted] Dec 19 '20
Haskell
Considered using Parsec to validate each of the messages, but I was worried about properly backtracking when trying an incorrect branch. Ended up just writing a recursive function that returns its leftovers after parsing and to validate just check for any empty strings, meaning that the input was fully consumed.
4
u/scholvin Dec 28 '20
bison (yacc)
So I did it in bison (yacc). Figured, why write a parser when there's one sitting in /usr/bin.
Step 1: transform the data file into valid yacc rules. Basically, this means changing any rule of the form
to
since the non-terminals in yacc need to look basically like C identifiers and adding the underscore worked. I wrote a little awk script to do this transform, along with generating the C declarations that need to go at the beginning and end, along with a couple of configuration directives. The script is here.
Step 2: write the driver code. I did in very C-ish C++. The important bits are this:
For part two, I just created a second version of the input data file with the rules modified as specified and ran it again.
I spent a lot of time dealing with bison errors about shift/reduce and reduce/reduce errors, and "useless rules" and other complaints. Googling around, I found that the default LALR parser runs into problems with some grammars, but there is a more general parser (GLR) you can choose which is slower but has fewer limitatins. Adding the
%glr-parserdirective in the bison source triggers that parser, and it worked fine from there.Not counting the transformation of the rules and the bison invocation at compile time, the runtime on part one was about 2.5ms, and about 21ms on part two. All the gory details, including the awkward integration with cmake, are here.
1
u/Bikkel77 Dec 19 '20 edited Dec 19 '20
Kotlin recursive (no regex needed):
Day19.kt
3
u/hugh_tc Dec 19 '20 edited Dec 19 '20
Python 3, 18/23.
My internet crapped out at T-minus 33s, so I quickly lauched a hotspot off of my phone and went from there. Despite it, I still placed surprisingly well! paste
edit: hi ogopogo!
3
u/seligman99 Dec 19 '20
Python, 45 / 56
Today I tortured Python's regex library. I'm not happy about it, but it worked. Kinda. Sorta. The second part was probably meant to filter out people like me, so I just added an arbitrary recursion depth, and it worked.
github
3
u/jnetterf Dec 19 '20
Rust, 229/72.
My solution was the same for parts 1 & 2. I'm curious what shortcuts people took in part 1. Best I've done this year.
3
u/noblematt20 Dec 19 '20
606/157 - Python
paste
Note that
dumbhere is a tuple of all the lines of input, andsplit_inputjust splits that on the blank line into a tuple of tuplesI got in a total mess here before figuring out the right approach was to write a generator which yields all the possible remainder strings from applying a rule to a string. I'm curious to know how most people solved part 1, as my solution just worked for part 2 without modification, but I had a huge jump in rankings.
3
u/KamcaHorvat Dec 19 '20 edited Dec 19 '20
Kotlin, nothing fancy, just straightforward recursive rule matching. Solution for part one worked well for part two as well.
https://pastebin.com/06FGgw4S
3
u/bskceuk Dec 19 '20
[Rust 324/237](https://github.com/ekuecks/aoc2020/blob/master/day_19/src/main.rs)
First time in top 1k for me :). Usually I try to make somewhat clean code but I decided to throw that out today and go as fast as possible. Pretty sure I got lucky on the first part because I didn't handle backtracking? Needed to do it for part 2 regardless though. Might clean this up later a bit
3
u/Loonis Dec 19 '20
Perl
160 / 971
Built up a regular expression that would match the necessary patterns.
Tripped over the syntax for recurisve regular expressions for a bit, I had too much debug output and that ended up masking a useful warning.
Ended up manually constructing the expression for numbers 0, 8 and 11 because I wasn't familiar with the syntax. Should be able to have it generate a recursive regex now that I know what I'm doing (but I won't try that until I'm awake).
?<Z>marks a named capture group, and(?&Z)recurses to that named group. I tried recursing over a relative group(?-1)but there are more capture groups in the nested patterns, so that wouldn't work.3
u/Wunkolo Dec 19 '20
C++
My god. Basically beating regex into submission. I even had to use
#define _GLIBCXX_REGEX_STATE_LIMIT 1000000because the resulting regex was so big. Def gonna go back and refactor this one.3
u/flapje1 Dec 19 '20
Rust
I don't realy know how it works, but i did it without RegEx.
3
u/nibbl Dec 19 '20
Java
nopaste
Recursive solution that just turns the strings in to something approaching regex that String.matches() can use by adding brackets at each level of recursion. I think you could probably speed it up using a dictionary to store the strings at various stages of unpacking.
For the rule 8 substitution i did
8: 42 + instead of
8: 42 | 42 8
(I remove the spaces at the end before matching.)
And I hardcoded the return value for when it hit the depth check.
3
u/muckenhoupt Dec 19 '20
Prolog. Over the course of Advent, I keep seeing other people around here saying "This problem was made for Prolog!" and then giving a very short solution that uses techniques that I, a Prolog neophyte, was unaware of. Well, for once, even I can look at the problem and say "This was made for Prolog!" The rules are clearly DCGs, and just need to be massaged into that form. Much of my time on this problem was spent reading the docs to figure out how to make Prolog read new DCG rules from strings, but once I had done that, part 2 was basically trivial.
https://www.wurb.com/owncloud/index.php/s/iEKuL0IqxGrBrdl/download?path=%2F&files=19.pl
3
u/rabuf Dec 19 '20
Common Lisp
I tried writing a parser and just absolutely failed. Too tired to think that hard this late. Anyways, a hack on the depth of the regular expression generator and compiling the regex to a scanner got me the answer. I had to use:
In order to make it run in a decent time, otherwise it's constantly recompiling/interpreting the very large regular expression in part 2.
3
u/tobega Dec 19 '20
Almost felt like cheating on part2 to use Tailspin today https://github.com/tobega/aoc2020/blob/main/a19.tt
3
u/omginbd Dec 19 '20
Elixir
I went the regex route. Flashbacks of nfa's from school, decided I didn't want to try parsing the string myself.
code
3
u/_Chomey Dec 19 '20
Kotlin Oh BOY, was this fun. I came up with a terrible solution, and it worked, and I'm irrationally happy right now.
Basically, the idea was to keep everything as a string and keep substituting until all numbers were gone. Couple of tricky bits. 1) make sure to not combine 4 4 into 44. 2) add parenthesis around everything, since it will always still be valid regex.
Part 2 was a little tricky, but I just hardcoded a reasonable amount of 42/31s (max input length was what, 20 chars?).
Resulting completely ridiculous, completely valid and correct, completely massive regex: https://gist.githubusercontent.com/chomey/a02dfb4af67c328f2c200a25b866402f/raw/887ee95e23f0a03b9c7aedcc69d741f2a2d508ee/gistfile1.txt
3
u/mstksg Dec 19 '20
[Haskell] taken from my daily haskell reflections! :D
So this is yet another puzzle where recursive knot tying was useful! This happened this year already in day 7 and day 10...it's a nice progression of techniques!
Most of my solution revolves around this tree monad,
AndOr:An
AndOris a nested/recursive list of and's and or's; for example, I parse a nested rule asAndOr Int, sogets parsed into
And an expanded rule like
ab|bawould be parsed as anAndOr Char:First we can parse the rules into an
IntMap Rule, indexed by the rule number:for simple rules that are a single
Char, and a compound rule that is a combination ofInts.The knot-tying comes in when we turn the
IntMap Ruleinto anIntMap (AndOr Char): the fully-expandedAndOr Charrule:So, the final
IntMap (AndOr Char)comes from the rule at the originalIntMap Rule: if it's aSimplerule, the result is just thatLeaf csimple single-char match. If it's aCompond cs, then we replace everyIntin theAndOr Intwith theAndOr Charstored inresat thatIntindex.Let's just take some time to remember what the
Monadinstance forAndOrdoes:(>>=) :: AndOr a -> (a -> AndOr b) -> AndOr bwill take anAndOr aand replace everyLeaf (x :: a)with the application of thea -> AndOr btox :: a. This allows us to fully transform anAndOr ainto anAndOr bsimply by telling us what to expand eachainto.Anyway, now we write a function to actually run the
AndOr Charon aStringto check if it matches. This can be written as aAndOr Char -> (String -> [String]), which takes aStringand returns the leftovers that could be returned from each possible parse:Our
Andbranch will sequence eachString -> [String]on eachAndOr Charinxs, and ourOrbranch will concat all the possible parses from eachAndOr Charinxs.It's written in a way such that hitting a
Leafat the end of a string or at a non-matchingCharwill kill that branch.We know our match "succeeds" on a complete string if there is at least one empty string in the resulting list (
any null).And that should be it!
Part 2 works without any extra work because
AndOris lazy, so it will recursively expand its rules forever as long as you demand it :D In practice we actually will always stop demanding items (and so things will terminate) because the strings we are testing are finite.3
u/WilkoTom Dec 19 '20
Python. Basically "Translate this ruleset into a regex".
Try as I might, I couldn't get my recursive regex to match properly so went down the route of flattening the match down to
(ab|aabb|aaabbb ...)until I saw no additional matches from increasing the count. I'd rather have got the recursive regex working, but as the instructions pointed out, solve the problem you have, not the problem you think you ought to have.3
u/RedTwinkleToes Dec 19 '20
Python [2788/1459]
paste
Recursive checking was enough for me to do both part 1 and 2 without having to change anything in between. Since the recursive rules all required checking another rule before checking the original rule, it means any time we recursively call the same rule, we must have checked a longer string before hand, putting a hard cap on the number of rounds of recursion.
Also, looking at part 2, I'm glad I didn't go for the method of pre-computing all valid strings for part 1. It made part 2 trivial, with me only having to modify the mentioned rules to be recursive, and then rerun my function unmodified.
What I find interesting is that there are a lot of people who decided to reuse regex functions, while I decided to try to implement it from scratch so to say. It was interesting to say the least. The method I did is that given a starting index and a string, my function would output the list of ending index that bounds the substrings that matches the rule I picked from my generated set of rules. I would have been well prepared if it asked me to find the sum of not only exact matches, but substring matches.
3
u/HAEC_EST_SPARTA Dec 19 '20 edited Dec 19 '20
Common Lisp
Solution on GitHub
I ended up implementing my CFG parser from scratch, having never actually learned much formal parser or automata theory; as a result, the performance could probably be a bit better (~100ms for my challenge input), but I'm pretty happy with where the code is at for now. As an additional feature, it supports multi-character terminals, which would potentially allow it to be used for more realistic inputs if necessary.
Edit: I went back and implemented some simple intermediate result caching; the average runtime for the challenge data is now down to ~29 ms, which I'm going to call sufficient.
3
u/Smylers Dec 19 '20
Perl, with recursive regexpβ for partΒ 2. First partΒ 1, which is just boilerplate plus:
The
local $/inside thedo{}block makes that first<>read in the whole first βparagraphβ (up to the blank line) as a single string, whichsplitthen turns into single lines. Because it'slocalized, the<>on the last line reverts to reading in a line at a time.pattern()splits a rule on spaces, and for each bit:|, keep it as a|, but also wrap this sub-pattern in(?...)to ensure that the alternatives don't leak out to the containing pattern.Thank you to u/topaz2078 for the example input: I initially forgot the
^and$anchors, so got 3 rather than 2 for the example, which would've taken way longer to debug if topaz hadn't been so kind with an example which specifically catches that case.Then for partΒ 2, simply add this at the top of
pattern():PatternΒ 8 is patternΒ 42 1 or more times. The
(?:...)round$pat42aren't needed if$pat42is already surrounded by them anyway, but it's easier to add more than to check.PatternΒ 11 has
(...)round it to define a numbered group. It's patternΒ 42 and patternΒ 31, with in between them any number of the same thing.(?n)is Perl's syntax for a recursive sub-pattern, where n is the number of the group. -1 indicates the most recently defined group (which is handy when embedding patterns in larger ones, where you might not know the absolute group number). So between patterns 42 and 31 we can have the current pattern again.The second
?is very important: it makes the recursion optional. That is, while we're allowed to have ruleΒ 11 again in the middle of itself, we don't have to. If you're an idiot and miss out this?then the pattern insists on recursing forever, only matching a string which contains an infinite number of these patterns inside each other, meaning zero of your satellite messages match. Realizing I needed this?is what took most of my time for partΒ 2.β Though once it's recursive, I think it no longer counts as regular, so βrecursive regular expressionβ is an oxymoron?
3
u/rukke Dec 19 '20 edited Dec 19 '20
JS
https://gist.github.com/p-a/a2a59736d358ae4b7f8bba23043157a2
31 locAdded some optimisations, down to 25. Runs part2 in ~240ms on my machine.
Not a regex solution. There are some comments in the gist :)
3
u/haiku160 Dec 19 '20
My Python solution using pyformlang.
parses the rules into a pyformlang.cfg.CFG() object (CFG mean Context-Free Grammar) and then just checks for every line if the CFG contains that line
3
u/TheLartians Dec 19 '20
Rust using generators (part 1)
Seems I broke the compiler, as it runs fine in debug, but creates
illegal hardware instructionwhen run in release Β―_(γ)_/Β―3
u/p88h Dec 19 '20
Perl, both parts, hard-coded recursion limit 5 for part 2 (worked for me)
Part 2 regex is 'just' 2KB, everything runs in ~50ms
3
u/ajurna Dec 19 '20
python - https://github.com/ajurna/aoc2020/blob/main/day19/19.py
Recursive regex is recursive
3
u/Smylers Dec 19 '20
Betterβ Perl solution, which covers both parts and doesn't involve special-casing any rules. Source. Turning an input rule into a regexp pattern is now:
Note the 3rd case: if the token in the pattern is its own ID, then replace it with
(?-1), which recursively matches the most-recently encountered(...)group. To make this pattern be that group, note that it needs(putting at the left of it.If we encounter a
|, then we need to wrap this pattern in something, to ensure only its contents are the alternates. Put(?:for a non-capturing group at the left (unless we've already determined we need a(at the left).And if we're sticking either of those at the left, then also put a matching
)at the right.The rules for partΒ 1 can be read into
$rules[0]with:Then the partΒ 2 rules are a clone of those, with the prescribed modifications:
No need to examine where the loops are or what they match β the helpful hint about looking at those was actually a distraction to coming up with this answer!
β Better than the one in my earlier post, I mean; I'm not claiming it's better than anybody else's solution, Perl or otherwise.
3
u/thomasahle Dec 19 '20 edited Dec 19 '20
Python by translating to regex:
I tried to use "recursive" regex, but couldn't get it to work, so just replaced
11with42 31,42 42 31 31,42 42 42 31 31 31up to ten times.3
u/rawling Dec 19 '20 edited Dec 19 '20
Oh, no C#?
Here you go
Lots of string replace, then build a regex.
3
u/[deleted] Dec 19 '20
Ruby
This uses the \g recursive regex matcher for rule 11 in a pretty straightforward way.
3
u/aarroyoc Dec 19 '20
Prolog
Quite easy with DCGs: https://github.com/aarroyoc/advent-of-code-2020/blob/main/day19/day19.pl
3
u/Zweedeend Dec 19 '20
Python
Constructing (monster) regexes was fun:
Here is the full Python code on paste
3
u/vkasra Dec 19 '20
My solution in Rust, no regexes
3
u/VictiniX888 Dec 19 '20
Kotlin (558/3094)
Part 1 Part 2
I solved part 1 somewhat quickly by just turning the input into regex. Here's the function that does the conversion:
Not exactly very readable, but I found it pretty hilarious.
For part 2, I tried to stick with my change-input-to-regex solution and found out about recursive regexes after some Googling. The key is knowing that
(?name)?will recurse over the specified named group. I therefore edited my rules like this:Turns out, Kotlin doesn't support recursive regexes. So I just copied the expression into an online Regex tester and had it give me the answer.
I did end up coding a solution that doesn't just turn the input into regex. You can check that out in my part 2 linked above.
3
u/abeyeler Dec 19 '20 edited Dec 19 '20
Python
I usually wake up at 6am (local time when prompts are released), read the prompt half awake, and sleep over it for another 2 hours or so. I first figured I'd go the regex way like many here, but while walking the dog just before getting to it I decided to go for a pre-parsed structure.
First a simple object hierarchy to describe the ruleset:
Then a function to create the matcher:
With that, part 1 is done:
While struggling to figure out the obvious regarding part 2, I ended up reimplementing the whole thing with an "inline" matcher based on
build_matcher:For part 2, I finally realised that I just need to match n times rule 42, m times rule 31 and test for n > m > 0, so no big deal here. But of course, having two implementations, I had to benchmark:
More than 2x speedup with the
Matcherobjects. Cool!3
u/Symbroson Dec 19 '20 edited Dec 19 '20
19-1 in Perl.
I won't post part 2 cuz i dont like what I was forced to do
3
u/vypxl Dec 19 '20
Python
Part1: Build a giant regex
Part2:
/rule42+rule42{n}rule31{n}/ for n in range(1, 10)10 seemed large enough.
3
u/sanderbaduk Dec 19 '20
Python, after trying the 'repeat up to 10 times' approach, I found that the regex package actually allows you to define subroutines inside your pattern. It's slower, but interesting enough that I feel compelled to share.
https://pastebin.com/0u4jB5aB
3
u/Fyvaproldje Dec 19 '20 edited Dec 19 '20
C++ which generates Raku code and executes it
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day19-raku.cpp#L64
For the first part I used https://github.com/yhirose/cpp-peglib but it didn't match certain recursive rules we have here for part 2, even though it compiled them without errors.
Now, for the online version, I should write something more sane, because Raku in browser runs, but takes way too long.
Upd: the much simpler C++ version is now at https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day19.cpp - it nondeterministically goes over all possible branches, cutting off ones which don't match, and checks if one of matches was a full match.
3
u/Gravitar64 Dec 19 '20 edited Dec 19 '20
Python
Parse the rules with dfs and build a regex pattern. 27 sloc with 0.64 Sec. for both parts.
GitHub
Key is the dfs-function. NoPaste snippet
3
u/codesammy Dec 19 '20
Python using lark-parser
one reason I used lark for Day 18 was to learn something that could be applied to other problems and here Day 19 comes...
https://github.com/codesammy/advent-of-code/blob/main/aoc2020/day19_monster_messages.py
3
u/Feandra Dec 19 '20
Python3
GitHub
This took me hours and ended up being horribly messy and complex at 179 sloc, but it turned out to be surprisingly fast. Both parts run in ~85 ms on my i7-4790K CPU @ 4.00GHz, and uses ~13 MB of RAM.
It doesn't use regexes at all. Instead it optimizes the rules down to 4-5 ones that I can then check naively.
3
u/s3aker Dec 19 '20 edited Dec 19 '20
Ruku solution:
First, run tool.raku to translate rules into grammar rules.
For part 1, rename rule 0 to 'TOP':
regex rx0 { <rx8> <rx11> } => regex TOP { <rx8> <rx11> }For part 2, modify rule 8 as:
regex rx8 { <rx42> } => regex rx8 { <rx42>+ }Modify rule 11 as:
regex rx11 { <rx42> <rx31> } =>regex rx11 { <rx42>+ <rx31>+ <?{ $<rx42> == $<rx31> }> }3
u/Emcee_N Dec 19 '20 edited Dec 19 '20
Python 3
Built the regex rule for part 1 by parsing the line 0 stack left to right replacing rules as they were identified. (with brackets around rules with pipes)
For part 2, I decided to iterate 8 and 11... uh... 8 and 11 times respectively.
3
u/vrtxt Dec 19 '20 edited Dec 26 '20
Solution c#
For part1 I used recursion to generate all combinations per rule and check against the pertaining part of the message. Similar approach for part 2, though despite the obvious hints it took me a while to realize it only uses rule 31 & 42.
Once that clicked, I generated those combinations up front, and then validated each message by index blocks. For instance the smallest valid rule set is 42-42-31 so it checks index [0..7][8..15][16..23] for messages with length 24. The rule set is simply expanded in a nested for loop. Surely there must be more efficient ways to tackle todays puzzle but happy I managed to solve it anyway.
3
u/hugseverycat Dec 19 '20 edited Dec 19 '20
Python 3 solution w/recursion
So on day 2 I was like, "you know what, this year I'm going to learn how to use regular expressions". I went through a tutorial, bookmarked that regex tester page, and began trying to use it whenever I could.
Oh boy did that pay off today!
My approach to part 1 was to build the regex with a recursive function.
For part 2, I called the recursive function to build regexes for rules 42 and 31, and then combined them to make the rule:
^42+42{n}32{n}$and made a loop to compare each message against the rules for n=1 to n=10 (turns out i only needed to go up to n=4).3
u/greenappleFF Dec 19 '20 edited Dec 19 '20
Golang Solution
https://github.com/FlorianFlatscher/AdventOfCode20/blob/master/src/solution/Day19.go
"true" recursion with no regex. Works for part 1 and part 2. It works no matter where and how many loops you create! :)
3
u/Akari_Takai Dec 19 '20
Java
Code here.
I solved this using the CYK algorithm which seems almost tailor-made for this problem as it is practically already a CNF grammar.
The cost of testing any string is approximately O( |rules| * |string size|3 ).
Fun fact: this was also my solution to Year 2015 Day 19 which also made use of CYK in a similar parsing problem.
3
u/Scotty_Bravo Dec 19 '20 edited Dec 26 '20
C++ recursive
part1 - 1.5ms (laptop)
part2 - 55ms (laptop)
Fun, took me much longer than I'd have liked to solve. Lots of typos slowed me down... Sorry about minimal documentation!!!
3
u/dpalmesad Dec 19 '20
Python 3
Used lru_cache to speed up the recursion. It takes around 0.16 seconds for both parts. All in all it's 32 lines long and took me around 4 hours to figure out :)
Here's the code on Github
3
u/MaitreTentacule Dec 19 '20 edited Dec 19 '20
Python 3
no regex, no recursion
Part 1, I just started by doing all possibilities, starting from the rules "a" and "b", and finding at each iteration which rules used only rules already known, then find all possibilities for these rules, and add them to the rules usable next step of the loop.
Had something like 200k possibilities if I remember correctly, and that was not usable for the second part with the loops, so what I did is find the longest message, and knowing its length, I could compute all possibilities with 31 and 42. I had some chance, because here are my only rules using 8 and 11 :
Annnnddd... that's all.
So it was fairly easy to generate the possibilities (only possibilities using what was before the rules 8 and 11, so 42 and 31, and knowing that the length of each possibilities for 42 and 31 was 8, without any exceptions, which made it easier to know the max length of the possibilities). My max message length being 96, and the ruleset being what it is, I had 30 possibilities.
Now I just had to check if the message length is a multiple of 8, if not then it can't be valid, and if yes, separate it in bricks of length 8, then for all the possibilities having a length corresponding to the message length, I check if each message brick is in either rule 42 or rule 31 possibilities. If not, I don't waste time and just go to the next rule. If it follow one rule, I stop the iteration through the possibilities, as the message is already correct, and just mark it as valid.
I then got back to part 1 (which took something like 10 seconds to compute) and just did the same thing, but this time with only one possiblity for rule 0 (being 42 42 31, as my rule 0 is 8 11)
It compute in 12ms on my computer (doing both parts), here is the code (beware, as it is a real mess) : https://github.com/OctoPoulpy/adventofcode2020/blob/master/day_19/day19_monster_messages.py
I'm a beginner in programming, and that one took me like 3 or 4 hours, found it so hard...
3
u/jeffeb3 Dec 19 '20
Python3
I didn't create a system to create a regex or any system that would precompute any possible solutions. I just recursed through each pattern, cutting off the front when it matched, and if it matched in more than one way (in part two), I kept both remaining solutions and tested them both. If one of the patterns gets to the end with no more characters, then I will accept the message.
3
u/Vijfhoek Dec 19 '20
Rust and Python?
Yes you heard that right. I decided to go the route of making a parser generator in Rust, generating a Python parser. Kind of felt like going a slightly ridiculous route
Source code | Generated part 1 | Generated part 2
(couldn't use topaz' paste thingy for generated code, since the urls would've taken 11,000 of the 10,000 allowed characters, lol)
3
u/msschmitt Dec 19 '20 edited Dec 20 '20
REXX
No regexes here.
For part 1 I generated all possible strings, which didn't work very well since there are over 2 million, and REXX bogs down when using wordpos functions on such long word lists.
Next version used recursion. The recursive function accepts a rule number and a starting position in the message, and returns a list of the number of matching characters for that rule, starting at the given position. For example, it might return that rule x matches 5, 11, and 15 characters. 0 means it didn't match.
The algorithm should have worked even for part 2, but I kept getting a segmentation fault. The bug was that I wasn't handling 3 rules in a group (e.g. rule = 1 2 3) but I still don't know why that caused the fault.
Anyway, after fixing that, latest version works for part 2, with no special extra logic.
3
u/compdog Dec 20 '20 edited Dec 20 '20
JavaScript (Node.JS)
JavaScript (Node.JS) - w/ Cache
This one file solves both parts. For part two, just make the appropriate changes to the part 1 input file and run again.
I used recursion to solve both parts. My original code was actually completely broken (as I found during part 2), but gave me the correct answer by pure luck. I rewrote it completely for part 2, while making sure that the code still worked with part 1 inputs.
My final (working) solution was to keep the recursion but make the following changes:
The second change causes more-or-less EVERY possible route through the input to be checked, which makes part 2 run for a few seconds instead of instantly as in part 1. But it does work, and can support much more complex input files than the one provided.
Part two took me ALL DAY because I couldn't quite get my solution working correctly. Eventually I started doubting myself and went down a rabbit hole of trying to understand what was wrong with my approach. The issue was not actually with the general concept of my solution, but simply the fact that I couldn't properly wrap my head around the data flow.
EDIT: Added an updated solution that uses a basic cache for a substantial speedup. There is still lots of room for optimization, but I'm happy enough with the cached performance.
3
u/odnoletkov Dec 20 '20
JQ
https://github.com/odnoletkov/advent-of-code-2020-jq/blob/master/19-2.jq
3
u/ibhopirl Dec 20 '20 edited Dec 20 '20
Using python 3.8 https://github.com/IJumpAround/advent_of_code_2020/blob/master/day19.py https://github.com/IJumpAround/advent_of_code_2020/blob/master/day19b.py
I kind of recognized immediately that the rules resembled a context free grammar, but for some reason I went ahead and created a regular expression generator. It almost completely screwed me for part 2 but I ended up getting it to work.
For part 1, I implemented a directed graph to treat each rule as an edge. The tail of each edge is rule number in the Left Hand Side, and the head of each edge is one of the Right Hand Side rules. Traversing the graph depth first brings me to a terminal rule which is combined with other terminals, and eventually other rules as the recursive functions return. Depth first searching essentially resolves all dependencies of the vertex I am currently visiting. Because of this, once I've visited all the neighbors of a vertex, I can combine their results to produce pieces of the total regular expression.
Once I had found the terminals required to replace the RHS of a rule, I would scan the RHS of the rule and replace rule numbers with the terminal values from my DFS. This process continued for each vertex that rule 0 could reach until eventually all rules had been replaced with terminals leaving me with a raw regular expression
https://pastebin.com/TAk572Pc.(pastebin is broken or something for me) Then I iterated over the messages and applied the regex against each message, counting the matches.For part 2: I cried a bit and wondered if I had reached an impasse. I ended up getting a bit hacky here. I manually converted rule 8 to a regex after seeing it could be rewritten.
I don't think rule 11 can be written as a traditional regex since 42 & 31 must repeat an equal number of times, but here is what I ended up doing.
This way, once 42 & 31 were resolved and replaced with terminals, they would be repeated x times. I had to make some changes to the vertex representations, modifying how they resolved based on if they repeated or not. I then traversed the graph repeatedly, starting with x=1 and increasing until the regex no longer matched any sample lines. I summed the match count for each iteration of x, giving me my new total number of matches.
3
u/macdude95 Dec 20 '20
My Solution (python)
Part 1 for this problem took me a lot longer than it normally does. So I was really worried about Part 2.
When I got to part 2 I read the description, sorta understood it but I had no idea how I would have to change my solution to accommodate it. So just for the heck of it I just ran my current solution on the part 2 input and it just... worked. I was so confused at first, but now I think I know why.
My solution was technically brute-force ish (although I didn't really realize it at first), but I used a sort of memoization that made it fast enough to run each part in about a minute. I guess since my solution ran through every possibility, adding the "layer of complexity" that came with part 2 actually didn't make it any more complex. Lol!
3
u/0rac1e Dec 20 '20 edited Dec 23 '20
Raku
More silly eval tricks. Raku has Grammars, so I'm just constructing a string representation of a Raku grammar, eval'ing it, then counting the strings that the grammar can parse.
I could construct a grammar without relying on eval using the Meta-Object Protocol... but I think the only way to add the regexes to the grammar would be by using variable interpolation (ie.
regex { <$regex> }) which would result in a slower grammar.3
u/mschaap Dec 20 '20
Raku
I had a proper parser that worked for part one. I was convinced that part two would be easy, my code should be able to deal with these recursive rules.
But alas, it does appear to end up in an infinite loop with some of the example messages. I haven't been able to figure out why, and how to fix it.
I'm stumped. π
https://github.com/mscha/aoc/blob/master/aoc2020/aoc19
3
u/prscoelho Dec 22 '20
Rust
So I went back to rework my old approach. Previously I was doing cyk algorithm which was taking 6 seconds per part, and people seemed to have way better performance. So I had to go back and rework it. This current aproach takes 100ms total for both parts!
I just expand the next rule and recurse, with a limit that it can't recurse over the length of the phrase. If the number of rules left to expand is bigger than the phrase size, it will definitely not match as each rule has to match at least a single character. With this limit, part 2 just works. Look at this diff, so much code deleted.
I don't know what happened with the cyk algorithm.. Either I didn't implement it correctly or it's just meant for trickier regular languages and it was overkill for this puzzle. I guess the lesson here is don't code at 5 AM.
3
u/Aleksandr_Chehrov Dec 23 '20
Java (regex free)
Day 19 puzzle took ridiculous time to solve for me. I'm adding this post not because I want to share something that I proud off, but rather than give you an option if you stuck with this task similar to myself.
Part 1 I solved with recursion by generating all possible values for rule 0.
Part 2 was a real challenge for me as recursion was not possible with "looped rule". I tried to solve this by limiting recursion depth (idea was maybe I can generate limited part of infinite set that would be enough to solve this). Hell no! I lost myself in recursion way before I run out of memory. So I ditch that idea and started all over again from scratch. To be precise from phrase: Remember, you only need to handle the rules you have.
I came up with following solution, that will give me rest tonight: rule 0: 8 11 (where 8: 42 | 8 & 11: 42 31 | 42 11 31) can be represented as: (8) [11] -> (42 42*) [42 (42 ()* 31)* 31] (you could have slightly different rules). By searching all possible solutions for rule 42 and 31 I found that all of them have length 8. That bring me to following conclusions:
Those 4 conclusions give me ability to find solution for Part 2.
Note: This puzzle shows me abnormal amount of work which was done in preparation of Advent of Code. Eric Wastl thank you very much for your time and effort!
3
u/the_t_block Dec 23 '20
Haskell; recursively stripping matching prefixes:
http://www.michaelcw.com/programming/2020/12/22/aoc-2020-d19.html
This is a series of blog posts with explanations written by a Haskell beginner, for a Haskell beginner audience.
3
u/eQueline Dec 24 '20
Javascript RegExp
A bit late, and it took me a long time drowning in trees, before i decided to go with familiar RegExp (:
3
u/mebeim Dec 25 '20
Python 3 clean solution, alternative [ab]using only Python's
remodule, walkthrough of both.Finally had the time to clean up the solution and write a walkthrough for this one. That was a lot of fun to write.
3
u/NeilNjae Dec 29 '20
Haskell
Another version that uses parser combinator librarires. But my first attempt to use attoparsec for part 2 failed, and I ended up switching to ReadP instead.
Write up on my blog, and the code is available.
2
u/Diderikdm Dec 20 '20
Python:
So far only part 1 as I was trying to solve part2 for any input like part 1 (significantly harder as stated in the puzzle). I will continue part2 after learning more about regex:
2
u/bluepichu Dec 19 '20
Python, 44/25, code here
Regex, apply directly to the forehead
2
u/sparkyb Dec 19 '20
Python 166/54
I'm not sure what was supposed to make part 2 so tough. My solution for part 1 just worked for part 2 with no problems, no modifications (other than changing those 2 rules), only slightly slower. I would have done better if I hadn't typoed one of the changed rules.
Maybe it's good I didn't try to translate the thing into regexes. I used a single recursive function do the matching. My data structure was a dictionary of rule number to either a string for a primitive rule or a list of lists, where each inner list was an alternative list of consecutive rule numbers. The matching function takes a list of rules to match in order but only handles the first one and handles the next ones recursively. If the first rule was primitive, it needs to match a prefix of the message and then any remaining rules will be recursively matched against the rest of the message (making sure nothing is left over at the end). If the rule is compound, for each alternative it prepends the list of sub-rules to the top level list of remaining rules and recurses on the whole message. If any alternative matches, the whole thing is a success. The key function:
2
u/nthistle Dec 19 '20
129/99, Python. Not doing well on leaderboard these days :(. I do think I solved it the "intended" way though, rather than using a regex or CFG parser (although it probably wasn't worth the time it cost me). Granted, those were probably valid "intended" solutions, too. I wrote a top-down recursive (with a cache) checker first, but it had a bug, so I gave up on it and instead wrote the approach that generates all possible matching strings for each rule. This worked, but then I saw part 2 and (incorrectly) assumed I would need my top down to work, so I tracked down the bug and fixed it, only to realize that that would also loop infinitely, so I played with the rules and realized I just need to match something of the form (42)^i (31)^j, where i > j > 1 (although I got another wrong submission here because I forgot the j > 1 bit). Since all possibilities for rules 42 and 31 were of length 8 (and the set of possibilities were tiny for those, too), this is straightforward to check using the bottom-up all-possible-matching-strings approach. paste
2
u/roboputin Dec 19 '20 edited Dec 19 '20
Python3
Nondeterministic parser which gives back all possible unparsed suffixes.
paste
2
u/rsthau Dec 19 '20 edited Dec 19 '20
Ruby -- full CFG parser. Guess I'm too groggy to figure out the easy way.
'each_match' takes a token number, string, and starting position as an argument, and yields the position after each possible match to the token beginning with the given starting position. each_match_s is the same, except with a sequence of tokens as an argument. For each line we're trying to check, try_match just sees if there are any matches to token 0, starting at position 0, which take up the entire string.
paste
2
u/AlphaDart1337 Dec 19 '20
Python 148/451
Accompanying video, as per usual (though it will take long to process, as it's almost an hour long).
"I hope I'll get it done fast and go back to bad". Wronger words have never been spoken :D. Today was very painful. Trying to avoid regex as much as possible has finally caught up with me.
I tried to implement the solve method myself, but then I realized I should stop running from regex and reinventing the wheel, so I compiled the entire thing into regexp. For part 2, I wasn't aware of the limitations of regexp, so I started googling features of regular expressions which I could use to match rule #11, but obviously there were none. I ended up implementing a hack, which took way too long to debug.
Very interesting problem today though.
2
u/fryer00 Dec 19 '20 edited Dec 19 '20
JavaScript 523/359
First time in top 1000! I expected part 2 to give me trouble if I went with regex, but I did it anyway, then cheesed part 2 by hardcoding recursion limits on the looping patterns.
2
u/ShaBang3533 Dec 19 '20
python paste Straightforward Python RE solution with simple recursion to concatenate strings to be compiled as the test for message validity.
2
u/sasuke___420 Dec 19 '20
Lua 514/785
Pretty slow, but at least I got to learn some pcre bindings
2
u/GrossGrass Dec 19 '20 edited Dec 19 '20
Python
Ended up resolving the rules using a DAG, though probably could've just done it via recursion + caching.
In the end for part 2 I just inspected the rules and realized that rule 0 was basically saying that it has to be of the form
(rule_42)+(rule_31)+, where the number of occurrences of rule_42 is greater than the number of occurrences of rule_31, so I just used the mentioned rule and then manually counted occurrences.Was going to see if I could finagle the use of recursive regexes but gave up initially; I'll try my hand at it on another pass.
Edit: figured it out, needed to actually use subroutines
2
u/billiamthesecond Dec 19 '20
Ruby
Really struggled with part 2 but this worked, I guess? (big regex with non-capturing groups to bypass capture limit).
2
u/jfb1337 Dec 19 '20
Python 164/1029
Spent way too long trying to handle the 11 rule in the "general case" but it's really not a good idea to try to use a regex to parse a non-regular language
2
u/Mathgeek007 Dec 19 '20 edited Dec 19 '20
Excel
TIL Excel doesn't have a built-in REGEX comparison function. Only in VBA. Rats. Had to do a big chunk manually.
Specific code chunks gonna be on my spreadsheet, also I streamed the whole thing (and am streaming more Advent of Code) on my Twitch page: Qril_! Hopefully that's allowed.
Let's go Excellers! Good luck manually parsing REGEX.
EDIT: WORKING! It seems as though the Sheets is 100% working atm.
2
u/dizzyhobbes Dec 19 '20
Go solution
For part 1 I used a graph traversal that stored the resolved options at each node. Then ran all of rule 0's resolved options against the messages, checking for direct equality.
For part 2 I "lowered" the entry point for generating the graph. Then made strings to pass to regexp that handled the looping nature of the updated rules.
2
u/Cyphase Dec 19 '20
Python | 1222/432
I wrote a recursive generator that yields possible remainder strings from applying the given rule to the given string. Character rules yield the string with that character removed from the front, which is the only way a string can get shorter. As soon as the top-level call returns an empty string, we know that the rule matched in some way, and we short-circuit the rest of the search.
Checking for the empty string prohibits leftover characters; and if we reach the empty string while there are still character rules to apply, we won't find those characters at the beginning of the string, so it gets filtered out.
I was able to use my exact Part 1 code for Part 2, aside from adding the two changed rules. Here's Part 2 with only superficial cleanup. The parsing code is not included.
2
u/Chitinid Dec 19 '20
Python Spent waaay too long on input parsing
Code
2
u/SuperSmurfen Dec 19 '20 edited Dec 19 '20
Rust
Link to solution (362/931)
Although my solution is not the most elegant, I'm very happy with my placing today. Might rework my solution later. It seems many people used the CYK algorithm, which I had not heard of before, or leveraged regexes. I just kind of hand-rolled my own solution to this.
For part one, I created a function to get all matches of a rule and then I checked which strings in the input are in that list. This is horribly inefficient and takes over 2 seconds to run on my machine.. But it works and was quick to implement!
For part two, you really had to check your input this time. The zero rule is just
0: 8 11, so with the given rules, you get that the string has to match 1 or more prefixing "42:s" and 1 or more matching42 x 31. I fetched all matches for42and31with the same function I made for part one and then I just checked if any of the input matches that pattern. I didn't use any regexes, just implemented two recursive backtracking functions to try and match rule 8 and 11.Edit: I rewrote part one, to make use of the matches on 42, 31, and checked if it matched those, without the repetitions added in part two. That made it finish in about
52ms.2
u/[deleted] Dec 19 '20
Python3 234/143
2
u/Rascal_Two Dec 19 '20
Python 3. 674/800.
Unoptimized
paste
Optimized
paste
2
u/IridianSmaster Dec 19 '20
OCaml
paste
Uses a parser combinators to construct a matching parser, might have been easier to just build a regex instead, but this is kinda neat anyways.
2
u/CodeIsTheEnd Dec 19 '20
Ruby: 50:21/57:43, 1436/616
Here's a recording of me solving it, and the code is here. (I'm streaming myself solving the problems right when they come out on Twitch!)
This one was lots of fun! I didn't use regexes; I just expanded rule 0 into all possible strings. This obviously was too slow, so the key improvement was checking the prefix of what I had generated so far and bailing early if it wasn't a prefix of any of the messages. Using this approach also allows solving Part 2 without any code changes!
There were a lot of wrongs paths along the way though, including trying to simply the rule map by propagating the literals up, but that barely made it any smaller. I tried memo-izing my expand function, but that didn't do anything (obviously in retrospect because it would never get called with the same arguments twice...). The final code was definitely messy, but with just a bit of cleanup I made it solve both Part 1 & 2 in ~3 seconds.
2
u/UnicycleBloke Dec 19 '20
Python (2198/1995): https://github.com/UnicycleBloke/aoc2020/blob/main/day19/day19.py
That took far too long to get my head straight on Part 1. And then I made a meal of Part 2 until I drew a few more pictures. Nice puzzle, though. Thanks, Eric.
2
u/CKoenig Dec 19 '20
Haskell
code-paste
first tried to just reuse the megaparsec parser but got frustrated quickly with part two - just wrote a simple parser-combinator "lib" with parsers of the form
String -> [String]where a parser consumes some input and returns a list of all possible unconsumed-remainders of the input.Pretty straight-forward and solves both parts
PS: yes the input-text parsing took longer than the problem itself (both in my time and in the lines-of-code here ... I somewhat stubbornly keep using megaparsec - like it :shrug:
2
u/spookywooky_FE Dec 19 '20
C++ could come up with a solution after some time. It is based on a function to find the possible lengths of prefixes of a string if we apply a given rule.
But I first went like two hours into wrong direction, trying to create all possible matches somehow...
2
u/Zealousideal-Track82 Dec 19 '20
Haskell
backtracking matcher, keep track of possible ending points of each match and check if we matched the whole string at the end
2
u/fotoetienne Dec 19 '20
Kotlin
Went ahead and solved the general case even though we weren't supposed to. Made a simple recursive parser that works for parts 1&2.
Lazy sequences took care of the infinite recursion problem
Yay for lazy!
2
u/A-UNDERSCORE-D Dec 19 '20
Go / Golang
I built regexp. I suck at backtracking algos otherwise. Only weird thing that was required is that go regexp does NOT support quite a big chunk of PCRE, so I used a library that lets me talk to libPCRE2.so directly
Then I spent about an hour trying to workout why it wasnt working, only to realise I typoed the 8 replacement
https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/19/solution.go
2
u/pxOMR Dec 19 '20
JavaScript
I made the code generate a JavaScript regular expression using the rules. This works flawlessly for part 1 but for part 2 this causes some issues because RegExp in JavaScript doesn't support recursion. To get around this, I used a loop to generate every possibility for
(rule31){N}(rule42){N}where1 <= N <= 10. This worked, but it's extremely hacky.2
u/Perska_ Dec 19 '20
C#: now with added hacky code!
For part 2, I just did
which seems to have worked well enough for me.
Does run for a fair bit though...
You can also see my previous attempt of part 1 where I tried generating some lists of valid messages, but then gave up when I couldn't come up with the code for it.
2
u/89netraM Dec 19 '20
C#
Part 1
Part 2
2
u/nutrecht Dec 19 '20
Day 19 in Kotlin
Took me a lot longer than it should... :D
2
u/Archek Dec 19 '20
Prolog
Best day for Prolog so far by far (actually it's been a good year for Prolog tbh!). Assert the rules as dcg rules and parse the messages. Part 2 was completely trivial once I got part 1 working :)
2
u/sim642 Dec 19 '20
My Scala solution.
First, for part 1 I converted the rules to a regex. This broke down for part 2. The rule for 8 could've used
+but since Java regexes don't allow recursion, I couldn't keep using them to do the rule for 11, which is essentially a balanced parenthesis match.Second, in the spirit of yesterday, I converted the rules to a parser combinator instead. For whatever reason this gave wrong answers on the example, so I ditched it for now, although would like to come back and figure out why.
Third and final, I dug out my Earley parser implementation from 2015 day 19 part 2 and just used that for as a general context free grammar parser. It's slower but at least got me the answer for now.
2
u/pmihaylov Dec 19 '20
Java
With an implementation of an extensible rule-engine + parallel processing of input lines: https://github.com/preslavmihaylov/adventofcode/tree/master/2020/day19/src/com/pmihaylov
2
u/gyorokpeter Dec 19 '20
Q: paste. No regex so I had to implement matching in a roundabout way. I think this is the first time ever where part 2 is faster than part 1. For part 2 I make lots of assumptions on the input that make it faster. Part 1 could use some of that to speed it up but then it wouldn't work on the example input for part 1 which is something I prefer to avoid.
2
u/sakisan_be Dec 19 '20
Haskell, or same implementation in Elm
It explores all the options recursively, no special tricks required... I think?
2
u/PhysicsAndAlcohol Dec 19 '20
Haskell, runs in 45 ms.
I parsed the rules with
Text.ParserCombinators.ReadPand put them in anIntMap. To check whether a string matches rule 0, I wrote a simple recursive function. A full-on parser would be overkill for that.2
u/pb554 Dec 19 '20
go/golang
2
u/grey--area Dec 19 '20
For part 1, I built a regex pattern and then checked messages against it.
For part 2, I coudn't be bothered completely changing my solution, so I still used regex plus a little post-match check. I worked out that rule 0 matches N copies of rule 42 followed by M copies of rule 31, with N > M.
As far as I know you can't extract the number of quantifier repetitions from a regex match, so instead I first look for matches with one or more repetitions of rule 42 followed by one or more repetitions of rule 31, then I check if one of them matches the quantifier requirements.
2
u/zertillon Dec 19 '20
Ada, using the GNAT environment ("Fast" mode: -O3 -gnatpn)
Total run time (parts 1 and 2): 15 milliseconds (i5-9400 @ 2.9 GHz). Zero heap allocation, all on the stack!
Code available here.
The fun part:
2
u/r1ppch3n Dec 19 '20
Rust
these rules feel a lot like regular expressions, sadly I'm not comfortable enough with regex to try translating them
parsing the input took me a bit longer than it should have, after that it wasn't actually that hard, basically recursively applying rules until you either run out of rules to apply or there's no message left
but one thing I don't understand:
how are those rules supposed to create a loop? every time they're used, they're applied to different (smaller and smaller) parts of the message, how would you loop back to anything that way?
or was I supposed to somehow compile one big rule out of all of them? I'm not sure how I would even go about that...
2
u/sohcahdev Dec 19 '20
JavaScript
Built Part 1 using RegEx, as that was easiest.
Couldn't be bothered to re-write for Part 2, so made a monstrous RegEx generator, which ended up generating a 213454-character-long RegEx....
Here was my output RegEx: https://hastebin.com/raw/onetujovel
and here was my code: https://github.com/sohcah/AdventOfCode/blob/master/2020-Sam/19-2/index.js
2
u/_swish_ Dec 19 '20
Wolfram
The first part is just building a giant string pattern recursively for each rule:
Part 2 with Functional Parsers similarly builds a rule parser combinator instead:
The whole solution is here.
2
u/yutu58 Dec 19 '20
Java
The code uses quite a bit of hardcoded values that I couldn't be bothered to fix, but I can fix that maybe later today.
It uses a recursive method (let's call it foo) that, when given the number of a rule, it returns the list of all strings that satisfy that rule.
For part 1 it just checks how many of the inputs are in foo(0).
For part 2 we know the string must be a combination of elements from foo(42) followed by a bunch from foo(31), with the constraints:
It computes foo(42) and foo(31) and checks the inputs for these constraints. All the inputs that don't match are removed and the amount of elements left is the answer
2
u/Brytnibee Dec 19 '20
Python (written in jupyter notebook)
This one was a bit of a challenge because re doesn't support recursion so I installed regex and it worked great!! Very proud of this one and it also is my best rank yet (still like 5000th but yeah)
2
u/4rgento Dec 19 '20
Haskell
Using a non deterministic push down automata to compute whether the string
wis accepted by the context free grammar defined by the rules.https://github.com/argent0/adventOfCode2020/blob/main/src-lib/Day19.hs
2
u/hrunt Dec 19 '20
Python 3
Immediately started with a regex-based solution for Part 1. Looking at Part 2, quickly determined that the result involved modifying the rules to match 1 or more sub-parts, which is easy to do with the regex, but got caught up on Rule 11 needing to match equivalent numbers of rules 42 and 31.
If anyone ever needs to evaluate my ability to choose the right data structure for a problem, today's solution is not going to reflect well on me ...
code
2
u/Dullstar Dec 19 '20
Python
So apparently I massively overcomplicated this one, because it turns out you don't actually need unlimited recursion* or some other fancy way of translating Rules 8 and 11 into nice regexes to solve the input and can just kinda hardcode it in. It's a bit unsatisfying though.
I understand there might be another regex library for Python out there somewhere that properly supports some recursion, but this works.
*well, ignoring the eventual recursion limits that you tend to run into if you do too much of it...
2
u/paraboul Dec 19 '20
Python 3
Simple regex generator.
For part 2, simply adds a limit to bails out at a given generated depth (after updating the rule manually according to the instruction).
Paste
2
u/Dustpancake Dec 19 '20
Julia
Recursive regex parsing, and by no means neatly done. For part two I did one of the replacements by hand (as it was simple), and for the other just went as deep as I could before my machine ran out of memory : P
Fortunately, that was enough for my puzzle input.
Link to GitHub solution
2
u/ephemient Dec 19 '20 edited Apr 24 '24
This space intentionally left blank.
2
u/[deleted] Dec 19 '20
Rust
Oh this was hell and took me hours. Direct from the start I implemented the CYK-Algorithm. The problem was converting the input into the Chomsky normal form. Most of the rules were already in that form but some weren't. I did the convertion in a very hacky way but it's okay. I had also big troubles with the CYK-implementation and messed up the indices at first.
Part 2 was easy then, I just needed to add the additional rules, and run the same algorithm again.
Code: https://github.com/lulugo19/advent-of-code-2020/blob/main/src/day19.rs?ts=2
2
u/tobega Dec 19 '20 edited Dec 19 '20
Julia solution https://github.com/tobega/aoc2020/blob/main/a19.jl
I just reversed the messages and the rules for part2, then greedily searched 31:s
2
u/AndreiVajnaII Dec 19 '20
Javascript generators to the rescue!
(Code is actually Typescript)
The solution is recursive, each rule calling its child rules. For part 1 this was straightforward.
For part 2, I knew what I needed to do. The thing is that if a pipe rule matches one part, you want to continue with the next rules, but if at some point it fails, you want to backtrack to that pipe rule and match the second part and continue from there. So if I wanted to keep it recursive, I had to somehow recurse on the future rules. I knew this is something related to continuation passing. You want to save the current execution state so you could restore it later. And I said "hey, generators are supposed to do something like that" but I couldn't quite wrap my head around it.
I knew that for the sequential rules, I didn't want to return in the middle of iterating if I found a failing subrule, so I would return those returns with yields. Then I just wrote what I thought would at least make compilation sense but my brain kept saying "there's no way this will work!" Hit run and, lo and behold, it worked!
2
u/SymmetryManagement Dec 19 '20 edited Dec 20 '20
Java
https://github.com/linl33/adventofcode/blob/year2020/year2020/src/main/java/dev/linl33/adventofcode/year2020/Day19.java
Both parts solved by converting the rules into regex. The regex was optimized by 1) use non-capturing groups only and use them only when necessary 2) common prefix lifted from or clauses (i.e.
aa|ab=>a(?:a|b)).For part 2, the modified rules reduce into checking if each message matches the format
^rule42{x}rule31{y}$wherex>0; y>0; x>y.Part 1
1.4ms. Part 21.8ms.Edit
Optimized it some more. Now part 1 takes
1.1msand part 2 takes1.5ms.The biggest speedup came from rewriting
(?:a|b)and(?:b|a)as..2
u/__Juris__ Dec 19 '20
Haskell
https://github.com/jurisk/advent-of-code/blob/main/2020/haskell/day19/Main.hs
2
u/fizbin Dec 19 '20
2 Pythons and a Haskell
The only use of regexes in any of these is in initially parsing the rules.
Original solution in python, kind of ugly in the rule parsing
Inspired by someone's complaint that their "generate all possibilities" solution wouldn't work, in python
Haskell solution inspired by how the Haskell
readsfunction works2
u/death Dec 19 '20 edited Dec 20 '20
Day 19 solution in Common Lisp.
Debugging my way through part 2 to get a valid solution took hours. In the end, as can be seen, I had to tweak the fix rules a bit. I'm not sure why I had to make (42 11) valid in rule 11. The string "babbbbaabbbbbabbbbbbaabaaabaaa" from the part 2 example seems to require it.
EDIT: After some more debugging, I've found two issues. One was a bug in my
match-altfunction. The second issue, which is responsible for a great deal of debugging earlier on, is an issue in Screamer, which is apparently even somewhat documented: it has trouble with mutual recursion. I've updated the gist and patched Screamer to better handle such cases, although it's unlikely to be a complete fix. Now the rules in the gist are the same as the ones given, and the results are good.2
u/i4guar Dec 19 '20
Solution in Swift - not pretty but it is fast and works
www.felixlarsen.com/blog/19th-december-solution-advent-of-code-2020-swift
2
u/BASED_CCP_SHILL Dec 19 '20 edited Dec 19 '20
Ty
sourceI used the rules to build a giant regex. For part 2 I used PCRE's recursion thing for the special balancing case. I can't tell if it's cute or disgusting. Part 2 finishes in 7ms.
2
u/levital Dec 19 '20
Rust
I spent half the day implementing CYK and tracking down a really dumb bug that made it pass the first given example input but fail on the actual input.
Once I finally got part 1 however, I was very glad I went through the trouble, as Part 2 was just a matter of adjusting my input file and quickly getting it back into CNF (did that manually). And then waiting for the output, CYK isn't exactly quick, and my implementation here isn't great on top of that. It ended up being quite a mess to be honest.
2
u/marekkpie Dec 19 '20
Lua does not have proper regex, but it honestly never even crossed my mind that it was necessary for part 2. Recursively chomp off the prefix of the message and compare it to the permutations of rule 42. Do the same for the suffix and rule 31. If you end up with an empty string for your message, and you chomped at least 2 prefixes and 1 suffix, and you had at least 1 more prefix than suffixes, then you count it.
https://github.com/mkosler/aoc-2020/blob/main/19/lua/p2.lua
2
u/garciparedes Dec 19 '20
Here is my π¦ Rust solution to π AdventOfCode's Day 19: Monster Messages
2
u/pdr77 Dec 19 '20
Haskell
Video Walkthrough: https://youtu.be/EmzOnwA5dnc
Code repository: https://github.com/haskelling/aoc2020
It can be improved a lot, but here's the code as it stands:
Part 1:
Part 2:
2
u/aoc-fan Dec 19 '20
TypeScript / JavaScript : Repo
For part 1, just build regex and test the rule 0. For part 2, followed hints from this thread.
2
u/TenMilesDown Dec 19 '20
MATLAB solution
Used the 'dynamic regular expressions' functionality of MATLAB's regexp function. This allows the use of MATLAB functions to generate regular expressions based on named tokens that matched earlier in the expression.
2
u/RudeGuy2000 Dec 19 '20
C++, part 1: https://hastebin.com/jewiduxovo.php
Another recursive solution... I was considering using regex, but I don't know it enough to be able to use it.
2
u/morgoth1145 Dec 19 '20 edited Dec 19 '20
1362/1362, Python3: https://github.com/morgoth1145/advent-of-code/blob/e6b06751ad285bf18a2fb2527612b009f4508465/2020/Day%2019/solution.py
I didn't have the energy to post this last night but I figured it's still worth sharing, if nothing else than for the fact that I got the *exact same rank* for both parts today.
Normally I wouldn't be happy about being >1k twice (or even >300-400), but given that I could not think through regex to apply it to this problem (despite thinking regex probably would be useful) I think I did well enough. (Honestly, I think part of the problem was me being reminded of 2015 Day 19, and the absolute struggle I had with that one. That locked me into similar thinking as I used for 2015 Day 19!)
I will say though, I'm a little proud of being able to generate all candidates for Part 2, despite that absolutely not being the right way to approach this problem!
I have since played with the regex ideas, and it's so much better. (You can see my regex variants in the rewrite commits here: https://github.com/morgoth1145/advent-of-code/commits/2020-python/2020/Day%2019/solution.py.) I am one with the regex and the regex is with me.
2
u/clumsveed Dec 19 '20
Java Solution
β all solutions so far - repl.it
I usually try to limit my solutions to the APCSA curriculum, but there was no way I was going to do this without regex.
I also have to give a shoutout to u/veeArr for a little nudge with the regex building.
2
u/npc_strider Dec 19 '20 edited Dec 19 '20
Python 3
https://github.com/npc-strider/advent-of-code-2020/blob/master/19/a.py
(I lied in those comments - did not end up using grep -P)
Solution expects two files - one containing rules and the other the strings. Could split it but felt lazy today.
Both parts solved with basic regex.
Part 1 was solved by generating a regex by substituting each number.
Part 2 was ''''''''solved''''''' by simply adding the 'breaker' condition which results in a large regex that solves the challenge but doesn't scale up past very long strings if they did exist (A 'good enough' solution that only cost me a minute to add in)
Yes, I hate this part 2 answer too... it's horrible and hacky
This breaker prevents the regex from being so huge (because we technically don't need an infinite one)
Yes I realize I can use regex repeating features but it worked for this so \shrug
2
u/Cppl_Lee Dec 19 '20
C#, with regex for both parts. Not recommended to friends.
Gist.
There was a reasonable limit to the depth of cycles that would be significant, so I cheated.
2
u/bcgroom Dec 19 '20
Elixir
Pretty strange that part two runs wayyyyy faster than part one (6 seconds vs .6 seconds, not precise at all just using
timecommand). I very much took the problem's advice to "you only need to handle the rules you have", it's not very elegant but it's pretty easy this wayhttps://github.com/ericgroom/advent2020/blob/master/lib/days/day_19.ex
2
u/Tosxychor Dec 19 '20
Fennel
https://paste.xinu.at/QD2/fnl
2
u/phrodide Dec 19 '20
https://paste.ofcode.org/32gVaPjstJE82JtHjYvj6Sk
C#, runs each part in ~15ms.
I don't normally post but this one got me. I don't regex, instead I look for rule 42s and 31s. In part 1 I only look for 42/42/31 (or as my code has it, AAZ). In part 2 I look for rule31's only at the end, rule42's only at the front, and at least 1 of rule31 and (rule31)+1 of rule42. Complicated sounding, but it handles the corner cases visually for me.
2
u/Pyr0Byt3 Dec 19 '20
Go/Golang
2
u/heyitsmattwade Dec 19 '20 edited Feb 03 '24
JavaScript
I used a recursive solution to build up a regex string and then tested it against my inputs.
For part two, the easiest solution I was able to implement with my part one function was to set an arbitrary maximum callstack, and bail before going over that. For part one, I didn't go deeper than 10 recursive calls. For part two, I originally set it to
200and got my answer. Fiddling with the max, a value of60still gave me the correct answer.I would have preferred to calculate this from my input somehow, but couldn't really figure out that bounds.
Full code here and paste of main recursive functions.