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

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(())); } } 

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

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) 

{-# 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 

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 

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