2.1.1 Description

r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb

2.1.2 Solution

Looking at the available towels we observe a couple of things:

1. All letters except b are available as single letters:

   str_subset(puzzle_data$towels, "^.$") %>% 
     sort()

   ## [1] "g" "r" "u" "w"

2. All digrams with b are evailable except bg:

   str_subset(puzzle_data$towels, ".b|b.") %>% 
     str_subset("^..$") %>% 
     sort()

   ## [1] "bb" "bg" "br" "bu" "bw" "rb" "ub" "wb"

3. A gb pattern not occuring at the end of the string is never a problem, as it can be split up, e.g. ugbbbu => u g bb bu (single letters are all available and so are all b digrams except bg).

4. Thus, only gb patterns at the end pose a potential problem, unless there is a special (longer) towel with gb in the end:

   puzzle_data$towels %>% 
     str_subset("gb$")

   ##  [1] "uugb"     "bggb"     "uuwrggb"  "ggbgb"    "bbgb"     "rbgb"    
   ##  [7] "wgb"      "urwgrgb"  "rgwgb"    "uuubwrgb" "urgbgb"   "gwwbgb"  
   ## [13] "bugb"     "bgb"      "gwgb"     "ggruwgb"  "ugb"      "grurrgb" 
   ## [19] "ubwrugb"  "uguwgb"   "rrwwugb"  "rgb"

5. However, if there is a special token fitting the end of a pattern, we must not end with gb without a matching token for the same reasons.

This allows to construct an algorithm which iteratively remove patterns which end with gb without a matching towel.

get_solvable_patterns <- function(data) {
  life_savers <- data$towels %>% 
    str_subset("gb$")
  has_token <- paste0("(", paste(life_savers, collapse = "|"), ")$")
  keep(data$patterns, function(pattern) {
    res <- TRUE
    while (res && str_detect(pattern, "gb$")) {
      if (str_detect(pattern, has_token)) {
        # Remove the matched token from the end
        pattern <- str_remove(pattern, has_token)
      } else {
        # No token can save this pattern
        res <- FALSE
      }
    }
    res
  }) 
}

valid_patterns <- get_solvable_patterns(puzzle_data)
length(valid_patterns)

## [1] 290

2.2.1 Description

2.2.2 Solution

We solve this part by means of dynamic programming.

1. Inititalize a vector (ways_to_arrange) with the same length as the pattern. Each entry x_i in this vector counts the number of arrangements for a substring of length i. The final reuslt will eventually be found at position x_n.
2. Iterate over all character positions i in the pattern and form all substrings up to the position i. For instance rrbg => [r], [rr, r], [rrb, rb, b], [rrbg, rbg, bg, g].
3. At each iteration check if the sub string represents an existing towel.
4. If this is the case, there are 2 possibilities:
   1. It is the complete substring from the beginning. That is the first part of the pattern. In this case set x_i to 1. This represents the fact that we can match this pattern in one way simply by using the fitting towel.
   2. If we look at a substring not starting at the beginning, we simply add the x_i − 1 to x_i. The idea is that with this new towel we add new possibilities to the arrangement which correspond to the number of arrangements which we had before adding this very towel.

For instance consider the example towels r, wr, b, g, bwu, rb, gb, br and the pattern rrbgbr. The algorithm would work like this:

1. We initialize x to [0,0,0,0,0,0]
2. i = 1:
   • The first (and only) substring is r. There is a towel for r: x = [1,0,0,0,0,0]
3. i = 2:
   • First substring is rr. There is no matching towel.
   • Second substring is r. There is a matching towel. We add the number of ways to arrange a pattern of length 1 to x₂: x = [1,1,0,0,0,0,0]
4. i = 3:
   • First substring is rrb. There is no matching towel.
   • Second substring is rb. There is a matching towel, use the number of arrangement for a string of length 1: x = [1,1,1,0,0,0,0].
   • Third substring is b. Again there is a matching towel, add the number of arrangements for a string of length 2: x = [1,1,2,0,0,0,0].
5. i = 4 (N.B. I skip irrelevant iterations, especially looking further back than max_i|t_i| positions, where t_i is towel i does not make sense, as there cannot be a matching towel of this length):
   • rbg does not match.
   • bg does not match.
   • g matches: x = [1,1,2,2,0,0].
6. i = 5:
   • bgb does not match.
   • gb matches: x = [1,1,2,2,2,0].
   • b matches: x = [1,1,2,2,4,0].
7. i = 6:
   • gbr does not match.
   • br matches: x = [1,1,2,2,4,2].
   • r matches: x = [1,1,2,2,4,6].
8. Final result is 6.

count_arrangements <- function(data) {
  max_len <- data$towels %>% 
    nchar() %>% 
    max()
  count <- function(pattern, towels) {
    idx <- seq(1L, nchar(pattern))
    ways_to_arrange <- rep(as.integer64(0L), nchar(pattern))
    for (end_pos in seq(1L, nchar(pattern))) {
      for (start_pos in seq(max(1L, end_pos - max_len + 1L), end_pos)) {
        sub_string <- substr(pattern, start_pos, end_pos)
        if (sub_string %in% towels) {
          if (start_pos == 1L) {
            ways_to_arrange[end_pos] <- 1L
          } else {
            ways_to_arrange[end_pos] <- ways_to_arrange[end_pos] + 
              ways_to_arrange[start_pos - 1L]
          }
        }
      }
    }
    tail(ways_to_arrange, 1L)
  }
  map(data$patterns, count, data$towels) %>% 
    do.call(c, .) %>% 
    sum()
}
count_arrangements(puzzle_data)

## integer64
## [1] 712058625427487