2020: Day 7

tidyverse

strings

recursion

Author

Ella Kaye

Published

December 7, 2020

Setup

The original challenge

My data

Part 1

library(tidyverse)

We have colour-coded bags that must contain a specific number of other colour-coded bags.

bags <- 
  read_tsv(here::here("2020", "day", "7", "input"), col_names = FALSE)

head(bags)

# A tibble: 6 × 1
  X1                                                                            
  <chr>                                                                         
1 wavy bronze bags contain 5 striped gold bags, 5 light tomato bags.            
2 drab indigo bags contain 4 pale bronze bags, 2 mirrored lavender bags.        
3 pale olive bags contain 3 faded bronze bags, 5 wavy orange bags, 3 clear blac…
4 faded white bags contain 5 vibrant violet bags, 4 light teal bags.            
5 mirrored magenta bags contain 2 muted cyan bags, 3 vibrant crimson bags.      
6 dull purple bags contain 1 striped fuchsia bag.

Our first task is to parse the natural language and split the rules into one container/contains pair per line:

rules <- bags %>%
  mutate(rule = row_number()) %>%
  separate(X1, c("container", "contains"), sep = " bags contain ") %>%
  separate_rows(contains, sep = ",") %>%
  mutate(contains = str_remove(contains, "\\.")) %>%
  mutate(contains = str_remove(contains, "bags|bag")) %>%
  #mutate(contains = str_replace(contains, "no other", "0 other")) %>%
  extract(contains, c('number', 'contains'), "(\\d+) (.+)") %>%
  filter(!is.na(number)) %>%
  mutate(contains = str_trim(contains)) %>%
  mutate(number = as.integer(number)) 

head(rules)

# A tibble: 6 × 4
  container   number contains           rule
  <chr>        <int> <chr>             <int>
1 wavy bronze      5 striped gold          1
2 wavy bronze      5 light tomato          1
3 drab indigo      4 pale bronze           2
4 drab indigo      2 mirrored lavender     2
5 pale olive       3 faded bronze          3
6 pale olive       5 wavy orange           3

To find all bags that con eventually contain our shiny gold bag, we first find the bags that can contain it directly. We then find the bags that can contain those bags and take the union of the two levels. We repeat, stopping when going up a level adds no further bags to the vector of bag colours already found. We then subtract 1, because we don’t want to count the original shiny gold bag.

# function to find all colours that contain a vector of other colours:
contains_colours <- function(colours) {
  rules %>%
    filter(contains %in% colours) %>%
    distinct(container) %>%
    pull(container)
}

bags <- "shiny gold"
old_length <- length(bags)
new_length <- 0

# keeping adding to the vector of bags, until no change
while(old_length != new_length) {
  old_length = length(bags)
  bags <- base::union(bags, contains_colours(bags)) %>% unique()
  new_length <- length(bags)
  #cat(old_length, ", ", new_length, "\n")
}

length(bags) - 1

[1] 274

Part 2

Now we need to discover the number of bags that a shiny gold bag must contain. I figured that lends itself to recursion, but struggled on the details. Hat tip to David Robinson for this solution. I’ve learnt a lot for myself by unpicking how it works.

count_all_contained <- function(colour) {
  
  relevant_rules <- rules %>%
    filter(container %in% colour)
  
  sum(relevant_rules$number * 
        (1 + map_dbl(relevant_rules$contains, count_all_contained)))
}

count_all_contained("shiny gold")

[1] 158730

Session info

Toggle

─ Session info ───────────────────────────────────────────────────────────────
 setting  value
 version  R version 4.3.1 (2023-06-16)
 os       macOS Sonoma 14.0
 system   aarch64, darwin20
 ui       X11
 language (EN)
 collate  en_US.UTF-8
 ctype    en_US.UTF-8
 tz       Europe/London
 date     2023-11-06
 pandoc   3.1.1 @ /Applications/RStudio.app/Contents/Resources/app/quarto/bin/tools/ (via rmarkdown)
 quarto   1.4.466 @ /usr/local/bin/quarto

─ Packages ───────────────────────────────────────────────────────────────────
 package     * version date (UTC) lib source
 dplyr       * 1.1.2   2023-04-20 [1] CRAN (R 4.3.0)
 forcats     * 1.0.0   2023-01-29 [1] CRAN (R 4.3.0)
 ggplot2     * 3.4.2   2023-04-03 [1] CRAN (R 4.3.0)
 lubridate   * 1.9.2   2023-02-10 [1] CRAN (R 4.3.0)
 purrr       * 1.0.1   2023-01-10 [1] CRAN (R 4.3.0)
 readr       * 2.1.4   2023-02-10 [1] CRAN (R 4.3.0)
 sessioninfo * 1.2.2   2021-12-06 [1] CRAN (R 4.3.0)
 stringr     * 1.5.0   2022-12-02 [1] CRAN (R 4.3.0)
 tibble      * 3.2.1   2023-03-20 [1] CRAN (R 4.3.0)
 tidyr       * 1.3.0   2023-01-24 [1] CRAN (R 4.3.0)
 tidyverse   * 2.0.0   2023-02-22 [1] CRAN (R 4.3.0)

 [1] /Users/ellakaye/Library/R/arm64/4.3/library
 [2] /Library/Frameworks/R.framework/Versions/4.3-arm64/Resources/library

──────────────────────────────────────────────────────────────────────────────