Day 19

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)
library(memoise)

Disable scientific formatting when displaying large numbers:

options(scipen = 999)

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

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

Run on puzzle input:

desired |> 
  map_dbl(num_matches) |> 
  sum()