Day 19

Advent of Code: Worked Solutions

Setup

# Libraries
library(tidyverse)

# Read input from file
available <- read_lines("../input/day19.txt", n_max = 1) |> str_split_1(", ")
desired   <- read_lines("../input/day19.txt", skip = 2)

Part 1

# Convert all possible available patterns into a regex string
regex <- str_c("^(", str_c(available, collapse = "|"), ")+$")

# Test each desired pattern for a regex match and count the number of matches
desired |> 
  str_detect(regex) |> 
  sum()

[1] 363

Part 2

Use recursion to check for total possible values, and cache results with memoisation to speed up the process:

# Recursively remove matches from the beginning of the string and sum result
num_matches <- function(str) {
  if (str_length(str) == 0)
    return(1)
  
  available |> 
    keep(~ str_starts(str, .x)) |> 
    map_chr(~ str_remove(str, .x)) |> 
    map_dbl(num_matches) |> 
    sum()
}

# Memoize the recursive function for performance
num_matches <- memoise::memoise(num_matches)

# Run on puzzle input:
desired |> 
  map_dbl(num_matches) |> 
  sum() |> 
  format(scientific = FALSE)

[1] "642535800868438"