# Setup ------------------------------------------------------------------------
test_input <- c(
  '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"
)
real_input <- readLines('input.txt')

# Functions --------------------------------------------------------------------

# Helper function, extracts a pattern-match from a string
extract <- function(str, pattern) {
  regmatches(str, regexpr(pattern, str, perl = TRUE))
}

# Helper function, given a vector of input lines, returns a named vector of 
# parsed validation rules
get_rules <- function(input) {
  input <- gsub('["\']', '', input, )      # Strip any quotes
  split_index <- which(input == "")        # Identify the blank line
  rule_strs <- input[1:(split_index-1)]    # All lines above the blank line
  
  rule_keys <- extract(rule_strs, '^\\d+')         # Rule name, the leading number
  rule_values <- extract(rule_strs, "(?<=: ).+$")  # Everything after the ':'

  # Wrap the values in regex capture groups, except for the static 'a' and 'b'
  # rule values
  root_rule_i <- grepl('[ab]', rule_values)
  rule_values[!root_rule_i] <- paste('(', rule_values[!root_rule_i], ')')
  
  names(rule_values) <- rule_keys  # Add names to the vector of rules
  rule_values
}

# Helper function, given a vector of input lines, returns a vector of 
# messages to validate
get_messages <- function(input) {
  input <- gsub('["\']', '', input)
  split_index <- which(input == "")
  as.character(input[(split_index+1):length(input)])
}

# Helper function, given a rule name (`key`) and the list of validation rules 
# (`rules`), returns the rule text if the rule is in the list of rules, 
# otherwise returns the given `key`. Sometimes, this function will receive
# 'a' and 'b' as `key`s, so it just gives those back.
fetch_if_exists <- function(key, rules) {
  rule <- gsub('[\\^\\$]', '', rules[key])
  if (is.null(rule)) { key } else { rule }
}

# Helper function, given a validation rule `rule`, returns all the references
# to other validation rules.
extract_rule_names <- function(rule) {
  unique(unlist(extract(rule, '\\d+')))
}

# Helper function, given a reference to a validation rule `rule_name` and the 
# list of validation rules `rules`, continuously evaluates the references to
# other validation rules contained in rule `rule_name` until it contains no
# more rule references, then returns the result.
expand_rule <- function(rule_name, rules) {
  rule <- gsub('[\\^\\$]', '', rules[rule_name])  # Remove the string start/end matches
  
  # So long as the rule string contains references to other rules...
  while (grepl('\\d', rule)) {
    
    rule_names <- extract_rule_names(rule)  # The referenced rule names
    
    # Replace each referenced rule name with the text of the referenced rule
    for (name in rule_names) {
      # Wrap the name in word boundaries, to avoid replacing part of a 
      # reference, i.e. the '5' in '15', for example
      pattern <- paste0('\\b', name, '\\b')
      replacement <- fetch_if_exists(name, rules)
      rule <- gsub(pattern, replacement, rule, perl = T)
    }
    
  }
  
  # Remove spaces and add the string start/end matches back
  paste0('^', gsub(' ', '', rule), '$')  
}

# Processing -------------------------------------------------------------------
input_to_process <- real_input              # Which input to process
rules <- get_rules(input_to_process)        # Get rules
messages <- get_messages(input_to_process)  # Get messages
rule0 <- expand_rule('0', rules)            # Expand rule['0'] to regex

# Check each message against rule['0'] to see if it matches
matches <- sapply(messages, function(x) grepl(rule0, x, perl = TRUE))
answer1 <- sum(matches)  # The number of matches

# Setup ------------------------------------------------------------------------
source('exercise_1.R')

test_input <- c(
  "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"
)

real_input <- readLines('input.txt')

# Processing -------------------------------------------------------------------
input_to_process <- real_input              # Which input to process
rules <- get_rules(input_to_process)        # Get rules

# Replace rules '8' and '11' with recursive versions, as described in the
# puzzle instructions. These have been modified to include the relevant
# regex rules for each. For rule['8'], this meant replacing the self-reference
# to rule '8' with the regex for one or more matches to rule '42'. For 
# rule['11'], this meant wrapping the second part of the rule in a named
# capture group ('rec') and replaced the self-reference with a recursive regex
# match to the named capture group `&rec`. 
rules['8'] <- "(42 | (42)+)"
rules['11'] <- "(42 31 | (?'rec' 42 (?&rec)? 31))"


messages <- get_messages(input_to_process)  # Get messages
rule0 <- expand_rule('0', rules)            # Expand rule['0'] to regex

# Check each message against rule['0'] to see if it matches
matches <- sapply(messages, function(x) grepl(rule0, x, perl = TRUE))
answer2 <- sum(matches)  # The number of matches