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

[Shalvah]

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