Day 19 Monster Messages

This is my attempt to solve Day 19.

process_file <- function(file) {
  read_file(file) %>%
    str_trim() %>%
    str_remove_all("\r") %>%
    str_split("\n\n") %>%
    pluck(1) %>%
    map(str_split, "\n") %>%
    map(1)
}
sample <- process_file("samples/day_19_sample.txt")
actual <- process_file("inputs/day_19_input.txt")

19.1 Part 1

First let’s build a function that will take the set of rules and convert it to a named list.

process_rules <- function(rules) {
  x <- str_split(rules, ": ")
  x <- set_names(map(x, 2), map(x, 1))

  map(x, function(.x) {
    if (str_detect(.x, "[a-z]")) {
      str_extract(.x, "[a-z]")
    } else {
      str_split(.x, " \\| ")[[1]] %>%
        map(str_split, " ") %>%
        map(1)
    }
  })
}

We can now build a function that will take a list of rules and a list of messages and filter the messages against the rules.

We have a recursive internal function which starts from rule “0” and iteratively works through seeing if we can build the current message from that rule.

check <- function(rules, messages) {
  fn <- function(s, seq) {
    if (length(s) == 0 | length(seq) == 0) {
      return (length(s) == 0 & length(seq) == 0)
    }
    
    r <- rules[[seq[[1]]]]
    
    if (r[[1]][[1]] %in% letters) {
      if (s[[1]] == r[[1]][[1]]) {
        fn(s[-1], seq[-1])
      } else {
        FALSE
      }
    } else {
      any(map_lgl(r, ~fn(s, c(.x, seq[-1]))))
    }
  }
  
  keep(messages, fn, "0")
}

Now we just need to process our input to split into rules and messages, and then call our function.

part_1 <- function(input) {
  rules <- process_rules(input[[1]])
  messages <- str_extract_all(input[[2]], ".")
  
  length(check(rules, messages))
}

We can test our function matches the sample:

part_1(sample) == 2

## [1] TRUE

And we can run with our actual data:

part_1(actual)

## [1] 173

19.2 Part 2

All we need to do for part 2 is modify rule 8 and 11, the check() function remains the same.

part_2 <- function(input) {
  rules <- process_rules(input[[1]])
  messages <- str_extract_all(input[[2]], ".")
  
  rules[["8"]] <- list(c("42"), c("42", "8"))
  rules[["11"]] <- list(c("42", "31"), c("42", "11", "31"))
  
  length(check(rules, messages))
}

We are given a different sample for part 2

part_2_sample <- list(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"
), c(
  "abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa",
  "bbabbbbaabaabba",
  "babbbbaabbbbbabbbbbbaabaaabaaa",
  "aaabbbbbbaaaabaababaabababbabaaabbababababaaa",
  "bbbbbbbaaaabbbbaaabbabaaa",
  "bbbababbbbaaaaaaaabbababaaababaabab",
  "ababaaaaaabaaab",
  "ababaaaaabbbaba",
  "baabbaaaabbaaaababbaababb",
  "abbbbabbbbaaaababbbbbbaaaababb",
  "aaaaabbaabaaaaababaa",
  "aaaabbaaaabbaaa",
  "aaaabbaabbaaaaaaabbbabbbaaabbaabaaa",
  "babaaabbbaaabaababbaabababaaab",
  "aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba"
))

We can test our function works against the provided sample:

part_1(part_2_sample) == 3

## [1] TRUE

part_2(part_2_sample)

## [1] 12

And we can run our function with the actual data:

part_2(actual)

## [1] 367

---

Elapsed Time: 41.497s