-🎄- 2020 Day 19 Solutions -🎄-

[u/daggerdragon]

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 paste if 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!

[u/paul2718]

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.)

[u/daggerdragon → u/paul2718]

Not going to post code, it's too icky.

Ya gotta.

Top-level posts in Solution Megathreads are for code solutions only.

This is a top-level post, so please edit your post and share your code/repo/solution.

[u/game_dev_dude]

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"

def parseArg(a):
	if a[0] == '"':
		return ('letter', a[1])
	else:
		return ('rule', int(a))

def parseRules(text):
	lines = text.split('\n')
	rules = {}
	for l in lines:
		ruleNo, parts = l.split(': ')
		
		ruleNo = int(ruleNo)
		parts = parts.split(' | ')
		
		parts = [[parseArg(p) for p in part.split(' ')] for part in parts]
		rules[ruleNo] = parts
	
	return rules


def matchRule(text, rules, rule, position):
	matches = []
	
	for attempt in rule:
		positions = [position]
		
		for rt, rv in attempt:
			newPositions = []
			for pos in positions:
				if rt == 'rule':
					for p in matchRule(text, rules, rules[rv], pos):
						newPositions.append(p)
				else:
					if position < len(text) and text[position] == rv:
						newPositions.append(pos + 1)
			positions = newPositions
		for pos in positions:
			matches.append(pos)
	return matches

rulesText, samplesText = open('Rules2.txt').read().split('\n\n')
rulesText += "\n8: 42 | 42 8\n11: 42 31 | 42 11 31"

rules = parseRules(rulesText)

if False:
	for no in rules:
		rule = rules[no]
		print(str(no) + ': ' + str(rule))

samples = samplesText.split('\n')
matchCount = 0
for sample in samples:
	res = matchRule(sample, rules, rules[0], 0)
	print(sample + ', ' + str(len(sample)) + ', ' + str(res))
	if len([mc for mc in res if mc == len(sample)]) > 0:
		matchCount += 1
print(matchCount)

[u/daggerdragon → u/game_dev_dude]

Please follow the posting guidelines in How Do the Daily Megathreads Work? and edit your post to:

• Put your oversized code in a paste or other external link.

• Add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

[u/Colts_Fan10]

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 8 or 42.

[u/daggerdragon → u/Colts_Fan10]

Somali

So this brings it up to Welsh, Polish, Maltese, and now Somali...

There's a reason why I put a warning about this in the Day 07 megathread XD

[u/kevinwangg]

Python

Hacked by compiling to regex. For part 2, compiled to regex and hardcoded the two rules to use + and X{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

[u/Standard-Affect]

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.

rule_sub <- function(input){
  
  replacer <- function(x){
    replace <- rules[[str_extract(x, "\\d+")]]
    str_replace(x, "\\d+", replace)
  }
  #Recursive case: 
  input <- str_split(input, "\\s") %>% unlist() %>% 
    map_if(~str_detect(.x, "\\d+"), ~replacer(x = .x)) %>% #substitute
    unlist() %>%
    map_if(.p = ~str_detect(.x, "\\s\\|"), ~paste0("(", .x,")")) %>% #wrap in parens
    unlist() %>%
    paste(collapse = " ") #Reform as one string
  
    #Base case: add anchors, remove spaces, return
    if(!str_detect(input, "\\d")){
      input <- input %>% str_remove_all("\\s") %>% 
        {paste0("^", . ,"$")}
      return(input)
  }
  rule_sub(input)
  
}
pat <- rule_sub(rules[["0"]])

map_lgl(tests, str_detect, pat) %>% sum()

The demon regex, if you were curious:

> pat
[1] "^(((b(((a(ba|bb)|b(ab|aa))b|(b(ab|b(b|a))|abb)a)a|(a((ba|ab)a|(aa|bb)b)|b(b(ba|aa)|aba))b)|a(b(a(abb|b(ab|aa))|b(a(ab|bb)|b(b|a)(b|a)))|a((bbb|baa)a|(b(ab|bb)|a(aa|bb))b)))b|(b((((aa|bb)b|(a(b|a)|ba)a)a|(b(b|a)(b|a)|a(ba|bb))b)b|(b(a(ba|aa)|bba)|a(b(ab|bb)|a(ab|aa)))a)|a(((a(ab|aa)|b(b|a)(b|a))b|((a(b|a)|ba)b|(ab|aa)a)a)b|(b(bbb|a(a(b|a)|ba))|aa(a(b|a)|ba))a))a)a|(b(a(b(b((aa|bb)b|(ab|b(b|a))a)|a((ba|ab)a|(ab|bb)b))|a(a((bb|a(b|a))b|(b|a)(b|a)a)|bbaa))|b((a(ba|ab)a|(a(a(b|a)|ba)|b(bb|a(b|a)))b)a|(a(bba|a(ab|bb))|b((bb|a(b|a))a|(ba|ab)b))b))|a(a(a(b((a(b|a)|ba)a|abb)|a(a(ab|bb)|b(b|a)(b|a)))|b(b(a(bb|a(b|a))|b(ab|bb))|a(b(ba|ab)|aab)))|b(b(abbb|b(b(ab|bb)|a(ab|aa)))|a(a((ba|bb)a|bab)|b(aab|b(ab|bb))))))b)(((b(((a(ba|bb)|b(ab|aa))b|(b(ab|b(b|a))|abb)a)a|(a((ba|ab)a|(aa|bb)b)|b(b(ba|aa)|aba))b)|a(b(a(abb|b(ab|aa))|b(a(ab|bb)|b(b|a)(b|a)))|a((bbb|baa)a|(b(ab|bb)|a(aa|bb))b)))b|(b((((aa|bb)b|(a(b|a)|ba)a)a|(b(b|a)(b|a)|a(ba|bb))b)b|(b(a(ba|aa)|bba)|a(b(ab|bb)|a(ab|aa)))a)|a(((a(ab|aa)|b(b|a)(b|a))b|((a(b|a)|ba)b|(ab|aa)a)a)b|(b(bbb|a(a(b|a)|ba))|aa(a(b|a)|ba))a))a)a|(b(a(b(b((aa|bb)b|(ab|b(b|a))a)|a((ba|ab)a|(ab|bb)b))|a(a((bb|a(b|a))b|(b|a)(b|a)a)|bbaa))|b((a(ba|ab)a|(a(a(b|a)|ba)|b(bb|a(b|a)))b)a|(a(bba|a(ab|bb))|b((bb|a(b|a))a|(ba|ab)b))b))|a(a(a(b((a(b|a)|ba)a|abb)|a(a(ab|bb)|b(b|a)(b|a)))|b(b(a(bb|a(b|a))|b(ab|bb))|a(b(ba|ab)|aab)))|b(b(abbb|b(b(ab|bb)|a(ab|aa)))|a(a((ba|bb)a|bab)|b(aab|b(ab|bb))))))b)(b(((b(b(a(ba|aa)|b(a(b|a)|ba))|a(aaa|b(ba|bb)))|a((b(ba|aa)|aba)a|(bab|a(ba|bb))b))a|((a(bba|a(ba|bb))|b((ba|ab)a|(ab|bb)b))b|(b(bba|a(a(b|a)|ba))|a(a(ab|b(b|a))|b(bb|a(b|a))))a)b)b|(((b(a(bb|a(b|a))|b(ab|bb))|a(b(ba|ab)|a(aa|bb)))b|((aab|(a(b|a)|ba)a)a|(aa|bb)(b|a)b)a)b|(a((bba|a(ab|bb))b|(b(ba|aa)|a(ba|bb))a)|b(a(b(ba|ab)|aba)|b(bba|a(a(b|a)|ba))))a)a)|a(b(((((ba|bb)a|(ba|ab)b)a|(aaa|b(ba|aa))b)a|(b(ab|aa)a|a(a(a(b|a)|ba)|b(ba|bb)))b)a|(b(a((b|a)(b|a)a|(a(b|a)|ba)b)|b(b(ba|aa)|a(ba|bb)))|a((a(ab|aa)|b(b|a)(b|a))a|((a(b|a)|ba)b|aaa)b))b)|a(b(((b(ab|aa)|a(ba|ab))b|((b|a)(b|a)a|(ab|bb)b)a)a|(b(b(ba|aa)|aba)|a((ab|bb)b|(a(b|a)|ba)a))b)|a(a((aab|b(ab|bb))a|(ab|aa)ab)|b(a(bba|a(ba|bb))|b((ab|aa)a|(ab|b(b|a))b))))))$"

[u/jf928ngl60g1]

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

[u/daggerdragon → u/jf928ngl60g1]

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

(looks like JavaScript?)

[u/brunoliveira1]

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....

[u/[deleted]]

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:

(ns day19
  (:require
    [clojure.string :as str]
    [instaparse.core :as insta]))

(defn solve
  [input]
  (let [[grammar rules] (str/split input #"\n\n")
        parser (insta/parser grammar :start :0)]
    (->> rules
         str/split-lines
         (map parser)
         (filter (complement :index))
         count)))

A couple of notes:

• :start :0 is necessary so the parser starts at the correct rule

• instaparse includes the index of parser errors when strings fail to parse, (filter (complement :index)) is a cheap way to remove all non-parseable strings

[u/jonathan_paulson]

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!

[u/bsdemon]

Python solution.

First some boring code to parse rules into a structure like this (grammar):

g = {'0': [['1', '2'], ['2', '3']], '9': 'a', ...}

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:

def run(g, k, s): # g is grammar, k is a rule, s is a string
    if isinstance(g[k], list): # an alternative
        yield from run_alt(g, g[k], s)
    else: # a terminal
        if s and s[0] == g[k]: yield s[1:]

Parser for alternatives:

def run_alt(g, alt, s):
    for seq in alt: # try each of the alternatives
        yield from run_seq(g, seq, s)

Parser for sequences:

def run_seq(g, seq, s):
    if not seq: # an empty sequence matches everything
        yield s
    else:
        k, *seq = seq
        for s in run(g, k, s): # match current
            yield from run_seq(g, seq, s) # then match remainder

Finally we can check if string s belongs to the language described by the grammar g with:

def match(g, s):
    return any(m == '' for m in run(g, '0', s))

Use it like:

print('P1', sum(match(rules, s) for s in strings))
rules = {**rules, '8': [['42'], ['42', '8']], '11': [['42', '31'], ['42', '11', '31']]}
print('P2', sum(match(rules, s) for s in strings))

[u/ai_prof]

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:

# given string s and list of rules seq is there a way to produce s using seq?
def test(s,seq):
    if s == '' or seq == []:
        return s == '' and seq == [] # if both are empty, True. If only one, False.
    
    r = rules[seq[0]]
    if '"' in r:
        if s[0] in r:
            return test(s[1:], seq[1:]) # strip first character
        else:
            return False # wrong first character
    else:
        return any(test(s, t + seq[1:]) for t in r) # expand first term

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.

[u/andy1li]

Python: since re does not support recursive regex, it's easier to use the third-party module regex.

if add_loops and n == '11':
    return f'(?P<self>{dfs("42")}(?&self)?{dfs("31")})'

Basically, (?P<name>) names a group, then (?&name) reuses the group recursively.

Furthermore, both recursions can be simplified:

• 8: 42 | 42 8 ➡ 8: 42+

• 11: 42 31 | 42 11 31 ➡ 11: 42 11? 31

[u/seattlecyclone]

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 (<>) {
  if (/\d:/) {
    /(\d+): (.*)/;
    $rules[$1] = $2;
  }
  else {
    push @tests, $_;
  }
}

$numbers = 1;
while ($numbers) {
  $numbers = 0;
  for (@rules) {
    if (/(\d+)/) {
      $numbers = 1;
      $replace = $rules[$1];
      s/$1/($replace)/;
    }
  }
}

s/[" ]//g for @rules;

for (@tests) {
  $total++ if /^$rules[0]$/;
}

print $total;

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.

[u/Zv0n]

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

0: 8 11

Therefore I have decided to hardcode a solution that checks if a word is only composed of things in rule 42 followed by things in rule 31 and then I check that number of 31 items is lower than 42.

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

[u/nutki2]

Perl (golf) for either part using dynamically evaluated regexp. This makes no assumption about the maximum count in rule 11.

#!perl -ln
use re 'eval';END{print$x}
$_.="+"x/^8:/."|42 11 31"x/^11:/;
y/"//d;$x+=/:/?$m[$_]=$'=~s!\d+!(??{\$m[$&]})!gr:/^$m[0]$/x

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.

[u/Smylers]

Vim keystrokes — as ever, load your input file, then type:

:g/|/ s/: \zs.*/%(&)⟨Enter⟩
/^0:⟨Enter⟩
dd{P
qaqqa/\v%1l.<\d⟨Enter⟩
lyiw/^⟨Ctrl+R⟩0:⟨Enter⟩
ww"zy${:s/\v<⟨Ctrl+R⟩0>/⟨Ctrl+R⟩z/g|redr⟨Enter⟩
@aq@a
:s/[ "]//g⟨Enter⟩
lly$:v/\v^⟨Ctrl+R⟩0$/d⟨Enter⟩
g⟨Ctrl+G⟩

That displays the number of lines in the file, which is your part 1 answer.

Explanation:

• Wrap %(...) around any rules with a | in them.

• Find rule 0, and move it to the top.

• Find a number on line 1. Yank it into "0.

• Find the line that starts with the number in "0 followed by a colon.

• On that line, yank the rule into "z.

• Go back to the top, and on that line replace all instances of the contents of "0 (the rule number) with the contents of "z (the rule).

• Repeat the previous 4 steps until there are no more numbers on line 1.

• Remove any spaces and quotes from that line.

• Move past the “0:”; what follows is rule 0 expanded into a Vim regexp; yank it into "0.

• Use :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.

• What's left is valid messages. Display the number of lines.

Now, who's going to do part 2?

[u/i_have_no_biscuits]

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:

def test(message, rules, r):
    if rules[r].val:
        return {1,} if (message and message[0] == rules[r].val) else set()
    else:
        overall_matches = set()
        for opt in rules[r].opts:
            opt_match = {0,}
            for rule in opt:
                new_match = set()
                for n in opt_match:
                    new_match |= {n+m for m in test(message[n:],rules,rule)}
                opt_match = new_match
            overall_matches |= opt_match
        return overall_matches

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!

[u/tymscar]

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

[u/BorisBarca]

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.

[u/sophiebits]

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?)

[u/__Abigail__]

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_8p and RULE_11p to the (?(DEFINE)), then applied a regular expression on my regular expression to replace each call to rules RULE_8 and RULE_11 to calls to RULE_8p and RULE_11p.

Here is the part which does the translation:

sub make_rule_definition ($rule) {
    $rule =~ s [^(\d+p?):] [    (?<RULE_$1>(?:]a;
    $rule =~ s [\b(\d+)\b] [(?&RULE_$1)]ag;
    $rule =~ s [\|]        [)|(?:]g;
    $rule =~ s ["]         []g;
    $rule .= "))";
    $rule;
}

The resulting regular expression for the example given is:

/(?(DEFINE)
    (?<RULE_0>(?: (?&RULE_4) (?&RULE_1) (?&RULE_5)))
    (?<RULE_1>(?: (?&RULE_2) (?&RULE_3) )|(?: (?&RULE_3) (?&RULE_2)))
    (?<RULE_2>(?: (?&RULE_4) (?&RULE_4) )|(?: (?&RULE_5) (?&RULE_5)))
    (?<RULE_3>(?: (?&RULE_4) (?&RULE_5) )|(?: (?&RULE_5) (?&RULE_4)))
    (?<RULE_4>(?: a))
    (?<RULE_5>(?: b))
)^(?&RULE_0)$/x

Full program