Monster Messages

Advent of Code 2020 Day 19

Task: Solve for X where...

X = the number of messages that completely match rule 0

Example input

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

It represents:

• The rules valid messages should obey
• A list of received messages (valid and not)

Variations in the rules:

• A string, matching one or more characters
• A list of sub-rules that must be matched in order - first rule must be matched in the text first, with second rule being matched somewhere in the text thereafter
• Two or more sets of sub-rules, of which all rules from at least one must match

One last caveat for rule 0:

• The whole message must match all of rule 0; there can't be extra unmatched characters in the message.

Part 1

1. Visualizing the example rules with a Tree
2. Inspecting my puzzle input
3. Parsing the input
4. Giving up earlier than planned
5. Browsing other solvers' solutions

Visualizing the example rules with a Tree

0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

              0
    4         1         5
    a     2       3     b
        4   4   4   5
        a   a   a   b

          or      or
        5   5   5   4
        b   b   b   a

              or
          3       2
        4   5   4   4
        a   b   a   a

          or      or
        5   4   5   5
        b   a   b   b

    a   a   a   a   b   b
    a   a   a   b   a   b
    a   b   b   a   b   b
    a   b   b   b   a   b
    a   a   b   a   a   b
    a   a   b   b   b   b
    a   b   a   a   a   b
    a   b   a   b   b   b

Inspecting my puzzle input

• The rules are not in order
• There are over 100, closer to 130
• The most complex rule has one pipe separating two sets with two sub-rules each
• Two rules match a and b like the example
• Most - if not all - other rules include a reference to one of the two rules matching a and b
• The messages are mostly 24 characters long
• The messages that aren't are of lengths divisible by 2
• Rule 0 matches two sub-rules, neither are the rules that match a or b - not shocking at all

Parsing the input

• This felt like its own sub-puzzle!

Split the input at the double-new-line character into two strings
Split the second string at each new line character and store in an array of strings as messages
Split the first string at each new line character and store in an array of strings as unprocessed rules

Create an array of the same length as the rules strings array, to be filled with each processed rule

For each rule string
  Split it at the colon-space character pair to separate the rule id from the rule itself
    If the rule contains a quote, it is one of the "a" or "b" base rules
      Insert in the other array at the index of the rule's id the string of the rule
    If the rule contains a | character, it has a pair of 1 or two sub-rules
      If, after splitting at the | character, either pair has a space character, it is a two-sub-rule pair
        Split on the space character
        Coerce each string to a number
        Insert in the other array at the index of the rule's id an array with two arrays, each with the two respective numbers
      Else - each set is a one-sub-rule pair
        Coerce each string to a number
        Insert in the other array at the index of the rule's id an array with two arrays, each with the respective number
    Else - the rule only contains one group of sub-rules
      Split at the space character
      Coerce each string to a number
      Insert in the other array at the index of the rule's id the array of numbers just constructed

Here's a visualization of that parsing algorithm

Giving up earlier than planned

• My brain couldn't piece together how I might solve this puzzle algorithmically
• Even though I parsed each rule into nested arrays, I didn't know how I was going to use them to derive the list of potential matching strings...even in the small example input

Browsing other solvers' solutions

• The winning pattern seemed to use regular expressions and/or recursion...and for some, Tree data structures
• I struggle understanding - and even more writing - all three
• Many solutions were 100 +-50 lines long
• This puzzle is clearly too far outside my abilities to solve

I lack the computer science skills to critically identify and implement a solution.

Bummer.

Onward!

SMALL UPDATE: Learning Regex

• I completed the 33 exercises freely available in this FreeCodeCamp module on Regular Expressions
• I discovered and completed the lessons and practice modules at Regex Crossword - a game-ified tutorial for learning Regex
• I discovered RegexOne - an interactive series of tutorials for learning and practicing Regex
• I intend to seek more resources for practicing Regex so that challenges like this don't block me as much in the future