2020 AoC Day 19 – Monster Messages

This is a solution to Advent of Code 2020 day 19, written in Raku.

https://adventofcode.com/2020/day/19

Part One

How many messages completely match rule 0?

Implementation

My solution for part one transforms the rules into a regex pattern and then counts the number of messages that completely match the pattern.

unit module Day19;

sub evaluate(Str $input) is export {
    my ($rules, $messages) = $input.split("\n\n");
    my %rules = $rules.lines.map(*.split(': ')).flat;

    sub make-pat($index) {
        given %rules{$index} {
            when /^ (\d+)+ % ' ' $/ {
                join(' ', do for $0 -> $r { make-pat(~$r) });
            }

            when /^ (\d+)+ % ' ' ' | ' (\d+)+ % ' ' / {
                '( ' ~
                join(' ', do for $0 -> $r { make-pat(~$r) })
                ~ ' | ' ~
                join(' ', do for $1 -> $r { make-pat(~$r) })
                ~ ' )'
            }
            when /^ '"' (\w) '"' $/ { "'{~$0}'"; }
            default { fail "Got unexpected " ~ $_; }
        }
    }

    my $pattern = make-pat('0');

    [+] $messages.lines.map( -> $line { $line.match( /^ <$pattern> $/ ).Bool; } );
}

Test

use Test;
use lib '.';
use Day19;

is evaluate('0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

ababbb
bababa
abbbab
aaabbb
aaaabbb'), 2;

ok 1 -

Answer

use lib '.';
use Day19;

my $input = slurp '19-input.txt';

say "Part One";
say evaluate($input);

Part One
226

Part Two

After updating rules 8 and 11, how many messages completely match rule 0?

Implementation

Part two avoids recursion and substitutes rules 8 and 11 with patterns that allow repetition. An additional constraint for rule 11 is that there must be an equal number of matches of sub rules 42 and 31. The embedded interpolation required MONKEY-SEE-NO-EVAL to be enabled.

unit module Day19PartTwo;

use MONKEY-SEE-NO-EVAL;

sub evaluate(Str $input) is export {
    my ($rules, $messages) = $input.split("\n\n");
    my %rules = $rules.lines.map(*.split(': ')).flat;

    sub make-pat($index) {
        given %rules{$index} {
            when $index eq '8' {
                make-pat('42') ~ '+ '
            }
            when $index eq '11' {
                '$<left>=' ~ make-pat('42') ~ '+ $<right>=' ~ make-pat('31') ~ '+ <?{ $<left> == $<right> }>'
            }
            when /^ (\d+)+ % ' ' $/ {
                join(' ', do for $0 -> $r { make-pat(~$r) });
            }

            when /^ (\d+)+ % ' ' ' | ' (\d+)+ % ' ' / {
                '( ' ~
                join(' ', do for $0 -> $r { make-pat(~$r) })
                ~ ' | ' ~
                join(' ', do for $1 -> $r { make-pat(~$r) })
                ~ ' )'
            }
            when /^ '"' (\w) '"' $/ { "'{~$0}'"; }
            default { fail "Got unexpected " ~ $_; }
        }
    }

    my $pattern = make-pat('0');

    [+] $messages.lines.map( -> $line { $line.match( /^ <$pattern> $/ ).Bool; } );
}

Test

use Test;
use lib '.';
use Day19PartTwo;

is evaluate('42: 9 14 | 10 1
9: 14 27 | 1 26
10: 23 14 | 28 1
1: "a"
11: 42 31
5: 1 14 | 15 1
19: 14 1 | 14 14
12: 24 14 | 19 1
16: 15 1 | 14 14
31: 14 17 | 1 13
6: 14 14 | 1 14
2: 1 24 | 14 4
0: 8 11
13: 14 3 | 1 12
15: 1 | 14
17: 14 2 | 1 7
23: 25 1 | 22 14
28: 16 1
4: 1 1
20: 14 14 | 1 15
3: 5 14 | 16 1
27: 1 6 | 14 18
14: "b"
21: 14 1 | 1 14
25: 1 1 | 1 14
22: 14 14
8: 42
26: 14 22 | 1 20
18: 15 15
7: 14 5 | 1 21
24: 14 1

abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
bbabbbbaabaabba
babbbbaabbbbbabbbbbbaabaaabaaa
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
bbbbbbbaaaabbbbaaabbabaaa
bbbababbbbaaaaaaaabbababaaababaabab
ababaaaaaabaaab
ababaaaaabbbaba
baabbaaaabbaaaababbaababb
abbbbabbbbaaaababbbbbbaaaababb
aaaaabbaabaaaaababaa
aaaabbaaaabbaaa
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
babaaabbbaaabaababbaabababaaab
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba'), 12;

ok 1 -

Answer

use lib '.';
use Day19PartTwo;

my $input = slurp '19-input.txt';

say "Part Two";
say evaluate($input);

Part Two
355

raku