Ryan Palo

Posted on Dec 19, 2020

Advent of Code 2020 Solution Megathread - Day 19: Monster Messages

#adventofcode #challenge

Yesterday was officially the first day I failed to complete the puzzle on the day, due to a busy schedule. I'm still planning on getting caught up and saving Christmas, but now I've got a bit of a hill climb. How caught up are you?

The Puzzle

In today’s puzzle, the elves have cooked up some sort of graph-based regular expression tree, and they need help parsing through it to get messages from their satellite in order to get pictures of a sea monster! These elves sure do spend a lot of time coming up with their own custom interfaces and protocols.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 07:10AM 12/19/2020 PST.

Language	Count
JavaScript	2
Haskell	2
Java	1
F#	1
Perl	1
Rust	1

Merry Coding!

Top comments (8)

Neil Gall • Dec 19 '20

Spent more time on today's than any previous one. I of course saw it as a parser combinator problem, whereas I think most people will see it through a regex lens. So I spent a lot of time trying to make it both backtracking and error-reporting before realising the error reporting isn't part of the problem. This simplification fixed it for me then a few refactoring iterations later I've got it to the following. My solution is general for all tail-recursive sequences, not specific to the problem posed as suggested in the text. No string copies, as few Vec copies as I can get away with, and I'm actively looking into reducing the final ones as I have a similar problem in another project I'm working on and want to make as efficient as possible.

use std::collections::HashMap;
use parser::*;

// --- model

type RuleID = usize;

#[derive(Debug, Clone, PartialEq)]
enum Rule {
    MatchChar(char),
    Sequence(Vec<RuleID>),
    Alternative(Vec<RuleID>, Vec<RuleID>)
}

#[derive(Debug, PartialEq)]
struct Rules {
    rules: HashMap<RuleID, Rule>
}

type MatchResult<'a> = Vec<&'a str>;

impl Rules {
    fn get(&self, id: &RuleID) -> &Rule {
        self.rules.get(id).unwrap()
    }

    fn match_seq_tail_recursive<'a>(&self, seq: &[RuleID], input: &'a str) -> MatchResult<'a> {
        let mut results = self.match_seq_non_recursive(seq, input);
        let mut remaining = &results[..];
        while !remaining.is_empty() {
            let mut new_results = remaining.iter().flat_map(|r|
                self.match_seq_non_recursive(seq, r)
            ).collect();
            let from = results.len();
            results.append(&mut new_results);
            remaining = &results[from..];
        }
        results        
    }

    fn match_seq_non_recursive<'a>(&self, seq: &[RuleID], input: &'a str) -> MatchResult<'a> {
        seq.iter().fold(vec![input], |remainings, rule| {
            remainings.iter().flat_map(|remaining|
                self.match_rule(rule, remaining)
            ).collect()
        })        
    }

    fn match_seq<'a>(&self, id: &RuleID, seq: &[RuleID], input: &'a str) -> MatchResult<'a> {
        if seq.last() == Some(id) {
            self.match_seq_tail_recursive(&seq[0..seq.len()-1], input)
        } else {
            self.match_seq_non_recursive(seq, input)
        }
    }

    fn match_rule<'a>(&self, id: &RuleID, input: &'a str) -> MatchResult<'a> {
        match self.get(id) {
            Rule::MatchChar(c) => {
                if input.chars().next() == Some(*c) {
                    vec![&input[c.len_utf8()..]]
                } else {
                    vec![]
                }
            }

            Rule::Sequence(rs) => {
                self.match_seq(id, rs, input)
            }

            Rule::Alternative(xs, ys) => {
                let r = self.match_seq(id, xs, input);
                if !r.is_empty() {
                    r
                } else {
                    self.match_seq(id, ys, input)
                }
            }
        }
    }

    fn match_all<'a>(&self, input: &'a str) -> Result<(), &'a str> {
        let r = self.match_rule(&0, input);
        match r.iter().next() {
            None => Err("no match"),
            Some(s) if s.is_empty() => Ok(()),
            _ => Err("extra unmatched input")
        }
    }

    fn apply_modification(&mut self) {
        // self.rules.insert(8, Rule::OneOrMore(42));
        self.rules.insert(8, Rule::Alternative(vec![42, 8], vec![42]));
        self.rules.insert(11, Rule::Alternative(vec![42, 31], vec!(42, 11, 31)));
    }
}

// --- parser

fn parse_rules(input: &str) -> ParseResult<Rules> {
    let rule_id = integer.map(|i| i as RuleID);
    let space = match_literal(" ");

    let match_char = any_char
        .between(match_literal(" \""), match_literal("\""))
        .map(Rule::MatchChar);

    let raw_sequence = one_or_more(right(space, rule_id.clone())).boxed();
    let sequence = raw_sequence.clone().map(Rule::Sequence);

    let alternative = pair(left(raw_sequence.clone(), match_literal(" |")), raw_sequence,
        |a, b| Rule::Alternative(a, b)
    );

    let rule = pair(
        left(rule_id, match_literal(":")),
        match_char.or(alternative).or(sequence),
        |id, def| (id, def)
    );

    let rules = one_or_more(whitespace_wrap(rule))
        .map(|rs| Rules {
            rules: rs.into_iter().collect()
        });

    rules.parse(input)
}

// -- problems 

fn count_valid_messages(rules: &Rules, messages: &[&str]) -> usize {
    messages.iter().filter_map(|m| rules.match_all(m).ok()).count()
}

fn main() {
    let input = std::fs::read_to_string("./input.txt").unwrap();

    let mut sections = input.split("\n\n");
    let mut rules = parse_rules(sections.next().unwrap()).unwrap().1;
    let messages: Vec<&str> = sections.next().unwrap().lines().collect();

    println!("part 1 {}", count_valid_messages(&rules, &messages));

    rules.apply_modification();
    println!("part 2 {}", count_valid_messages(&rules, &messages));
}

#[cfg(test)]
#[macro_use] extern crate maplit;

#[cfg(test)]
mod tests {
    use super::*;

    fn sample_rules() -> Rules {
        use Rule::*;
        Rules {
            rules: hashmap![
                0 => Sequence(vec![4, 1, 5]),
                1 => Alternative(vec![2, 3], vec![3, 2]),
                2 => Alternative(vec![4, 4], vec![5, 5]),
                3 => Alternative(vec![4, 5], vec![5, 4]),
                4 => MatchChar('a'),
                5 => MatchChar('b')
            ]
        }
    }

    fn part2_sample_rules() -> Rules {
        parse_rules(
            "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
").unwrap().1
    }

    fn part2_sample_rules_modified() -> Rules {
        let mut rules = part2_sample_rules();
        rules.apply_modification();
        rules
    }

    fn part2_input() -> impl Iterator<Item = &'static str> {
"abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
bbabbbbaabaabba
babbbbaabbbbbabbbbbbaabaaabaaa
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
bbbbbbbaaaabbbbaaabbabaaa
bbbababbbbaaaaaaaabbababaaababaabab
ababaaaaaabaaab
ababaaaaabbbaba
baabbaaaabbaaaababbaababb
abbbbabbbbaaaababbbbbbaaaababb
aaaaabbaabaaaaababaa
aaaabbaaaabbaaa
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
babaaabbbaaabaababbaabababaaab
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba".lines()
    }

    #[test]
    fn test_parser() {
        let rules = parse_rules(
            "0: 4 1 5
             1: 2 3 | 3 2
             2: 4 4 | 5 5
             3: 4 5 | 5 4
             4: \"a\"
             5: \"b\""
        );

        assert_eq!(rules, Ok(("", sample_rules())));
    }

    fn no_match() -> Vec<&'static str> {
        vec![]
    }

    #[test]
    fn test_matcher_success() {
        let rules = sample_rules();
        assert_eq!(rules.match_rule(&0, "ababbb"), vec![""]);
        assert_eq!(rules.match_rule(&0, "abbbab"), vec![""]);
        assert_eq!(rules.match_rule(&0, "aaaabbb"), vec![("b")]);
    }

    #[test]
    fn test_matcher_failure() {
        let rules = sample_rules();
        assert_eq!(rules.match_rule(&0, "bababa"), no_match());
        assert_eq!(rules.match_rule(&0, "aaabbb"), no_match());
    }

    #[test]
    fn test_match_all() {
        let rules = sample_rules();
        assert_eq!(rules.match_all("abbbab"), Ok(()));
        assert_eq!(rules.match_all("aaaabbb"), Err("extra unmatched input"));        
    }

    #[test]
    fn test_part2_rules_without_modification() {
        let rules = part2_sample_rules();
        let messages = part2_input();
        assert_eq!(messages.filter_map(|m| rules.match_all(m).ok()).count(), 3);
    }

    #[test]
    fn test_part2_rules_with_modification() {
        let rules = part2_sample_rules_modified();
        let messages = part2_input();
        assert_eq!(messages.filter_map(|m| rules.match_all(m).ok()).count(), 12);
    }

    #[test]
    fn test_part2_rules_with_modification_individual_cases() {
        let rules = part2_sample_rules_modified();
        assert_eq!(rules.match_all("bbabbbbaabaabba"), Ok(()));
        assert_eq!(rules.match_all("babbbbaabbbbbabbbbbbaabaaabaaa"), Ok(()));
        assert_eq!(rules.match_all("aaabbbbbbaaaabaababaabababbabaaabbababababaaa"), Ok(()));
        assert_eq!(rules.match_all("bbbbbbbaaaabbbbaaabbabaaa"), Ok(()));
        assert_eq!(rules.match_all("bbbababbbbaaaaaaaabbababaaababaabab"), Ok(()));
        assert_eq!(rules.match_all("ababaaaaaabaaab"), Ok(()));
        assert_eq!(rules.match_all("ababaaaaabbbaba"), Ok(()));
        assert_eq!(rules.match_all("baabbaaaabbaaaababbaababb"), Ok(()));
        assert_eq!(rules.match_all("abbbbabbbbaaaababbbbbbaaaababb"), Ok(()));
        assert_eq!(rules.match_all("aaaaabbaabaaaaababaa"), Ok(()));
        assert_eq!(rules.match_all("aaaabbaabbaaaaaaabbbabbbaaabbaabaaa"), Ok(()));
        assert_eq!(rules.match_all("aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba"), Ok(()));
    }
}

Neil Gall • Dec 19 '20

I managed to avoid most of the Vec copies by building an iterator structure for the whole thing. This means almost the whole matcher is now lazily evaluated. Just in the tail recursion part I need to iterate the results twice so there's no choice but to collect into a temporary Vec. Lots of lifetime annotations needed to make it work as it's a big old complex data structure in memory, but it's cool to see this sort of thing can be done if needed with compile time memory management.

type MatchResult<'a> = Box<dyn Iterator<Item = &'a str> + 'a>;

impl Rules {
    // ...

    fn match_seq_tail_recursive<'a>(&'a self, seq: &'a [RuleID], input: &'a str) -> MatchResult<'a> {
        let mut remaining: Vec<&str> = self.match_seq_non_recursive(seq, input).collect();
        let mut results: MatchResult<'a> = Box::new(empty());
        while !remaining.is_empty() {
            let next_remaining = remaining.iter().flat_map(|r|
                self.match_seq_non_recursive(seq, r)
            ).collect();

            results = Box::new(results.chain(remaining.into_iter()));
            remaining = next_remaining;
        }
        results
    }

    fn match_seq_non_recursive<'a>(&'a self, seq: &'a [RuleID], input: &'a str) -> MatchResult<'a> {
        seq.iter().fold(
            Box::new(once(input)),
            |remainings, rule| {
                Box::new(remainings.flat_map(move |remaining|
                    self.match_rule(rule, remaining)
                ))
            }
        )
    }

    fn match_seq<'a>(&'a self, id: &RuleID, seq: &'a [RuleID], input: &'a str) -> MatchResult<'a> {
        if seq.last() == Some(id) {
            self.match_seq_tail_recursive(&seq[0..seq.len()-1], input)
        } else {
            self.match_seq_non_recursive(seq, input)
        }
    }

    fn match_rule<'a>(&'a self, id: &RuleID, input: &'a str) -> MatchResult<'a> {
        match self.get(id) {
            Rule::MatchChar(c) => {
                if input.chars().next() == Some(*c) {
                    Box::new(once(&input[c.len_utf8()..]))
                } else {
                    Box::new(empty())
                }
            }

            Rule::Sequence(rs) => {
                self.match_seq(id, rs, input)
            }

            Rule::Alternative(xs, ys) => {
                let mut r = self.match_seq(id, xs, input).peekable();
                if r.peek().is_some() {
                    Box::new(r)
                } else {
                    self.match_seq(id, ys, input)
                }
            }
        }
    }

    fn match_all<'a>(&self, input: &'a str) -> Result<(), &'a str> {
        let mut r = self.match_rule(&0, input);
        match r.next() {
            None => Err("no match"),
            Some(s) if s.is_empty() => Ok(()),
            _ => Err("extra unmatched input")
        }
    }
}

Shalvah • Dec 19 '20

My Ruby solution.

For the first part, my approach was to generate all valid strings and count the messages that appeared there. This runs in a few seconds since the number of valid strings is relatively small.

Part 2 was really scary, but once I noticed that the modified rules were at the end of the chain (near rule 0), it was easier. Did the first approach to get the matching messages, then did some simplification of the rules + regex matching on each remaining message to find valid ones.

require 'set'

# We'll evaluate the requested rule and generate all valid matches
# Then check if each message is within the list

def parse_rule(rule)
  parsed = {}
  if (match = rule.match(/^"(?<char>\w)"$/))
    parsed[:match] = match[:char]
  elsif rule.include?("|")
    parsed[:or] = rule.split("|").map(&:split)
  else
    parsed[:and] = rule.split
  end
  parsed
end

def generate_matches(rules, rule_number)
  rule_to_evaluate = rules[rule_number]
  parsed = parse_rule(rule_to_evaluate)

  if parsed[:match]
    return [parsed[:match]]
  elsif parsed[:and]
    matches = []
    parsed[:and].each do |dependent_rule|
      dependent_matches = generate_matches(rules, dependent_rule)
      if matches.empty?
        matches = dependent_matches
      else
        gen = []
        matches.each do |match|
          dependent_matches.each do |dm|
            gen << (match + dm)
          end
        end
        matches = gen
      end
    end
    matches
  elsif parsed[:or]
    matches = parsed[:or].flat_map do |dependent_ruleset|
      sub_matches = []
      dependent_ruleset.each do |dependent_rule|
        dependent_matches = generate_matches(rules, dependent_rule)
        if sub_matches.empty?
          sub_matches = dependent_matches
        else
          gen = []
          sub_matches.each do |match|
            dependent_matches.each do |dm|
              gen << (match + dm)
            end
          end
          sub_matches = gen
        end
      end
      sub_matches
    end
  end
end


rules, messages = File.read("input.txt").split("\n\n")
rules = rules.lines.map { |line| line.chomp.split(": ") }.to_h
matches = Set.new generate_matches(rules, "0")
messages = messages.split("\n")
matching_messages = messages.select { |message| matches.include?(message) }
original_matching = matching_messages.count
messages -= matching_messages

# Changing:
# Rule "8" = "42 | 42 8"
# Rule "11" = "42 31 | 42 11 31"
# Rule 8 translates to X, or XX, or XXX, or XXXX... = itself n times, where X is any match(42)
# Rule 11 translates to XY or XXYY or XXXYYY...= X k times, Y k times, where X is any match(42) and Y is any match(31)

matches_42 = generate_matches(rules, "42")
length_of_42_match = matches_42[0].size # All 42-matches have the same length (by inspection)
matches_42 = Set.new(matches_42)
matches_31 = generate_matches(rules, "31")
length_of_31_match = matches_31[0].size # All 31-matches have the same length (by inspection)
matches_31 = Set.new(matches_31)

# Then Rule 0 is "8 11", which means both must match.
# XnWkYk where X and W are matches of 42 (they don't have to be the same match)

rule_42_regex = "((\\w{#{length_of_42_match}}){2,})" # X must appear at least twice
rule_31_regex = "(\\w{#{length_of_31_match}})+"
rule_0_regex = Regexp.new("^#{rule_42_regex}#{rule_31_regex}$")

matching = messages.select do |message|
  is_valid = false
  if message.match(rule_0_regex)
    all_matches = message.scan(Regexp.new(".{#{length_of_42_match}}"))

    checking_31 = false
    matches_for_42 = []
    matches_for_31 = []
    has_matches = all_matches.each_with_index do |match, index|
      # Last item must always be checked against 31
      if index == all_matches.size - 1
        if (matches_31.include?(match))
          matches_for_31 << match
          break true
        else
          break false
        end
      end
      if checking_31
        if matches_31.include?(match)
          matches_for_31 << match
        else
          break false
        end
      else
        # We're checking 42
        if matches_42.include?(match)
          matches_for_42 << match
        else
          # Once we reach the first non-42, we switch to checking for 31
          if matches_31.include?(match)
            matches_for_31 << match
            checking_31 = true
          else
            break false
          end
        end
      end
    end

    if has_matches == true
      is_valid = matches_for_42.size > matches_for_31.size
    else
      is_valid = false
    end
  end
  is_valid == false ? false : true
end

p original_matching
p original_matching + matching.size

Benedict Gaster • Dec 19 '20

Ah today was fun... I did have to stop and think for part 2 as I'd decided to go down the path of parser combinators rather than regex and it was clearly to late to backtrack! Anywhy managed to handle them directly, I guess it's a bit of hack, but worked out fine.

data Rule = RS [Int] (Maybe [Int]) | RC Char
    deriving (Eq, Show)

quotedString :: Parser Rule
quotedString = do
    TP.char '"'
    xs <- TP.many (TP.noneOf "\"" TP.<|> (TP.char '\\' >> TP.char '\"'))
    TP.char '"'
    return $ RC (head xs)

number :: Parser Int
number = do
  digits <- many1 TP.digit
  TP.spaces
  return $ read digits

ruleSeq :: Parser Rule
ruleSeq = do
    ls <- many1 (TP.spaces >> number)
    rs <- optionMaybe (TP.spaces >> TP.char '|' >> many1 (TP.spaces >> number))
    return $ RS ls rs

rule :: Parser (Int, Rule)
rule = do 
    i <- number
    TP.char ':'
    r <- TP.try (TP.spaces >> quotedString) TP.<|> ruleSeq
    return (i, r)

parse :: Parser a -> String -> a
parse p s =
    case TP.parse (TP.spaces *> p <* eof) "" s of
    Left e  -> error $ show e
    Right x -> x

build :: M.Map Int Rule -> Rule -> Parser ()
build m (RS ls rs) = choice (TP.try (aux ls) : maybe [] (\ rs -> [aux rs]) rs)
    where
        aux [n] = build m (m M.! n)
        aux (n:xs) = do
                        _ <- build m (m M.! n)
                        _ <- aux xs
                        return ()
build _ (RC c) = void (TP.char c)

main = do
    (rs,is) <- readFile "day19_input" 
                    <&> lines <&> span (/="") <&> bimap (M.fromList . map (parse rule)) tail
    let zero = rs M.! 0
        g = isRight . TP.parse (TP.spaces *> build rs zero <* eof) "" 

    print (length $ filter id $ map g is)

    -- part 2 (we need to be a little careful to not get stuck in that loop :-))
    let p42 = build rs (rs M.! 42)
        p31 = build rs (rs M.! 31)
        p = do 
              r42 <- TP.many1 $ TP.try p42
              r31 <- TP.many1 $ TP.try p31
              if length r42 > length r31 then return () else fail "no luck"
        g' = isRight . TP.parse (TP.spaces *> p <* eof) ""

    print (length $ filter id $ map g' is)

Yuan Gao • Dec 19 '20 • Edited

I had a slightly odd approach. Having used PEG in at least three earlier challenges for various parsing needs (including yesterday's), I immediately noticed that the rules are worded identically to PEG. So I thought... what if I just string-manipulate these rules into PEG and use it directly? Turns out this works

The convert() function converts a line of rules provided by challenge input into a line of PEG for the parsimonious library. The rest is just about using this grammar to parse messages, and catching the parse errors.

Part 1 code:

from parsimonious.grammar import Grammar
from parsimonious import ParseError
import re

def convert(line):
    line = line.strip().replace(":", " =")
    line = re.sub(r"(\d+)", r"RULE\1", line)
    line = re.sub(r"= (.*) \| (.*)$", r"= ((\1) / (\2))", line)
    return line

data = open("input.txt").read().splitlines()
rules, messages = data[:137], data[138:]

rules.sort(key = lambda x: int(x.split(":")[0]))
converted = "\n".join(map(convert, rules))
grammar = Grammar(converted)

def parse(line):
    try:
        grammar.parse(line)
    except ParseError:
        return False
    return True

print("sum", sum(map(parse, messages)))

yuuup... didn't think that would work, but it does

Part 2 code isn't that much more, just replace rules 8 and 11, and catch parse exceptions on rule 31, which is a thing they explicitly mention.

Casper • Dec 19 '20

My Haskell solution. I realized regex would be useful, but I didn't find any built-in regex in Haskell, so I went for the parser approach instead. Using a parser library like Parsec would also have been an option, but I couldn't bother installing and spending time learning it just for this. So I made my own shitty parser combinator. Then a little hacky solution for part 2.

{-# LANGUAGE LambdaCase #-}
module Main where

import qualified Data.Map as Map
import Data.Maybe
import Data.Bifunctor as Bf
import Control.Applicative
import Control.Monad

data Rule 
  = Or [Int] [Int]
  | Then [Int]
  | Constant Char

-- I know this generic `a` doesn't make much sense. I just wanted the Monoid stuff.
newtype RuleParser a = RuleParser (String -> Maybe String)

instance Semigroup (RuleParser a) where
  (RuleParser p1) <> (RuleParser p2) = RuleParser $ \s -> p1 s <|> (p2 s <|> Nothing) 

instance Monoid (RuleParser a) where
  mempty = RuleParser Just

pThen :: RuleParser a -> RuleParser a -> RuleParser a
pThen (RuleParser p1) (RuleParser p2) = 
  RuleParser (p1 >=> p2)

pConstant :: Char -> RuleParser a
pConstant c = 
  RuleParser $ \case 
      "" -> Nothing
      (x:xs) -> if x == c then Just xs else Nothing

runParser :: RuleParser a -> String -> Maybe String
runParser (RuleParser p) = p

parseN :: RuleParser a -> Int -> RuleParser a
parseN p n = foldl (\acc _ -> acc `pThen` p) mempty [1..n]

isValidRule :: RuleParser a -> String -> Bool
isValidRule p s = case runParser p s of Just [] -> True; _ -> False

getRule :: Ord k => Map.Map k a -> k -> a
getRule mapping i = fromJust $ Map.lookup i mapping

getParser :: Map.Map Int Rule -> Rule -> RuleParser a
getParser r (Or xs ys) = 
  foldl (\acc i -> acc `pThen` getParser r (getRule r i)) mempty xs
  <> 
  foldl (\acc i -> acc `pThen` getParser r (getRule r i)) mempty ys
getParser r (Then xs) = 
  foldl (\acc i -> acc `pThen` getParser r (getRule r i)) mempty xs
getParser r (Constant c) = pConstant c

-- For part 2, try parsing 8 an increasing amount of times 
-- until 11 successfully parses or until 8 fails.
createParser :: Bool -> Map.Map Int Rule -> RuleParser a
createParser isPart1 r = 
  if isPart1 then
    getParser r $ fromJust $ Map.lookup 0 r
  else
    RuleParser $ \s -> tryParse nEights s
    where nEights = map (parseN (getParser r (getRule r 42))) [1..]
          pEleven = getParser r (getRule r 11)
          tryParse (p:ps) s = 
            case runParser p s of  
              Just rest -> 
                case runParser pEleven rest of 
                  Just "" -> Just ""
                  _ -> tryParse ps s
              _ -> Nothing

parseInput :: String -> (Int, Rule)
parseInput s = 
  if r2 == "" then
    if '\"' `elem` r1 then
      (num, Constant (r1 !! 2))
    else
      let rule = read <$>  words r1
      in (num, Then rule)
  else
    let rs1 = read <$> words r1 
        rs2 = read <$> words r2
    in (num, Or rs1 rs2)
  where (num, rules) = Bf.bimap (read :: String -> Int) tail $ span (/= ':') s
        (r1, r2) = Bf.second (drop 1) $ span (/= '|') rules

parse :: [String] -> (Map.Map Int Rule, [String])
parse ss = 
  (rulemap, msgs)
  where (rules, msgs) = Bf.second tail $ span (/= "") ss
        rulemap = Map.fromList $ map parseInput rules

main :: IO ()
main = do 
  (rules, msgs) <- parse . lines <$> readFile "input.txt" 
  let p1 = createParser True rules
  print $ length $ filter (==True) $ map (isValidRule p1) msgs

  (rules, msgs) <- parse . lines <$> readFile "input2.txt" 
  let p2 = createParser False rules
  print $ length $ filter (==True) $ map (isValidRule p2) msgs

Ryan Palo • Dec 23 '20

It's not pretty. It's not elegant. I'm sure there's some Regex theory that would have made this puzzle easier than it was. But I got it done, and that's all that counts. Hand-decoded Rules 0, 8, and 11 to decouple the infinite looping from the rule resolution algorithm, so I ended up being able to reuse most of my work from part 1. :) Don't look at the code for part 2. Just don't.

from itertools import product, chain, takewhile

class Rule:
    """A Rule consists of all possible combinations of characters that
    match it.

    Properties:
        name (str): the ID of the rule, a positive integer as a string
        rules (List[List[str]]): a list of the initial raw rules that
            are available to match.  Each rule is a list of ID's pointing
            to another rule or a raw character
        resolved_values (Set[str]): concrete strings that this rule matches
    """
    def __init__(self, text):
        name, _colon, tail = text.partition(": ")
        self.name = name
        if '"' in tail:
            self.resolved_values = {tail.strip('"')}
            return

        parts = tail.split(" | ")
        self.rules = [part.split() for part in parts]
        self.resolved_values = None

    def resolve(self, rulebook):
        """A recursive function that resolves this rule and all children
        rules.  Caches its result in self.resolved_values.
        """
        if self.resolved_values:
            return self.resolved_values
        self.resolved_values = {
            "".join(p) 
            for rule in self.rules
            for p in product(*[rulebook[i].resolve(rulebook) for i in rule])
        }
        return self.resolved_values

    def match(self, line):
        """Returns true if this rule matches the line in one of its
        resolved_values."""
        return line in self.resolved_values


def parse(filename):
    """Parses an input file to a set of rules and a set of messages.

    Input files have this format:

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

        abbabacabacabacbbabbab
        bababababa
        baba
    """
    rules = dict()
    with open(filename, "r") as f:
        while (line := f.readline()) != "\n":
            rule = Rule(line.strip())
            rules[rule.name] = rule
        messages = f.read().splitlines()

    return rules, messages


def part1(rules, messages):
    """Return the number of messages that match rule 0."""
    return sum(rules["0"].match(message) for message in messages)


def chunk_message(message, size):
    """Chunk a string up into `size` size chunks."""
    for i in range(0, len(message), size):
        yield message[i:i + size]

def check_recursive(rules, message, chunksize):
    """Rules 8 and 11 are recursive.  Checks that the message matches
    the rule '8 11'.

    Rule 8: 42 | 42 8, which works out to one or more chunks matching
        rule 42.
    Rule 11: 42 31 | 42 11 31, which works out to one or more sets of
        rule 42 followed by an equal number of sets of rule 31.

    Together, these requirements mean that the message must follow the
    following requirements:

        1. The first and second chunk must match 42.
        2. All subsequent chunks must match 42 until:
        3. Chunks must then match one or more 31's.
        4. We have to have matched at least one more 42 than we do 31.

    It's not pretty but it does the job.  TODO: finite state machine.
    """
    chunks = chunk_message(message, chunksize)
    count_42 = 0
    past_42 = False
    count_31 = 0
    for chunk in chunks:
        if len(chunk) != chunksize:
            # Protect against strings that aren't an even multiple of
            # chunksize
            return False

        if not past_42 and chunk in rules["42"].resolved_values:
            # Match one or more 42's and nothing else.
            count_42 += 1
            continue

        past_42 = True  # Stop matching 42.

        if chunk not in rules["31"].resolved_values:
            # Match only 31's the rest of the way
            return False
        count_31 += 1

    # Ensure all requirements were met
    return count_42 >= 2 and count_31 >= 1 and count_42 >= 1 + count_31


def part2(rules, messages):
    """Modify Rule 8 and Rule 11 to be recursive.  Now how many
    messages match rule 0 exactly?
    """
    total = 0
    len42 = len(list(rules["42"].resolved_values)[0])
    len31 = len(list(rules["31"].resolved_values)[0])
    assert len42 == len31, "42 chunks don't equal 31 chunks"
    for message in messages:
        if check_recursive(rules, message, len42):
            total += 1

    return total


if __name__ == "__main__":
    rules, messages = parse("data/day19_test.txt")
    rules["0"].resolve(rules)
    assert 2 == part1(rules, messages)
    rules, messages = parse("data/day19_test2.txt")
    rules["42"].resolve(rules)
    rules["31"].resolve(rules)
    assert 12 == part2(rules, messages)
    print("All tests passed!")

    rules, messages = parse("data/day19.txt")
    rules["0"].resolve(rules)
    print("Part 1:", part1(rules, messages))
    print("Part 2:", part2(rules, messages))