07: Handy Haversacks

library(mistlecode)

Loading required package: cipheR

Loading required package: pacman

Loading required package: slider

Loading required package: glue

Loading required package: rlang

Attaching package: 'rlang'

The following object is masked from 'package:data.table':

    :=

The following objects are masked from 'package:purrr':

    %@%, flatten, flatten_chr, flatten_dbl, flatten_int, flatten_lgl,
    flatten_raw, invoke, splice

Loading required package: R6

To install `mistlecode` yourself, run `devtools::install_github('guslipkin/mistlecode')`.

Also loading: cipheR data.table dplyr purrr slider stringr tidyverse glue rlang R6

options(scipen = 999)

df <- 
  read.csv("input.csv") |>
  dplyr::mutate(dplyr::across(
      tidyselect::matches('child[2-4]C'), 
      \(x) ifelse(as.character(x) == " ", NA, x)
  ))

df$child2C[as.character(df$child2C) == " "] <- NA
df$child3C[as.character(df$child3C) == " "] <- NA
df$child4C[as.character(df$child4C) == " "] <- NA

Part 1

longerDF <- data.frame(parent = "", nChild = 0, cChild = "")

for(col in seq(3, 9, by = 2)) {
  for(r in 1:nrow(df)) {
    if(!is.na(df[r,col-1]))
      for(i in 1:df[r,col-1]) {
        longerDF <- rbind(longerDF, data.frame(parent = df[r,1], 
                                               nChild = df[r,col-1], 
                                               cChild = df[r,col]))
    }
  }
}
longerDF <- longerDF[-1,]

shinygoldDF <- 
  longerDF[longerDF$cChild == "shiny gold" | longerDF$parent == "shiny gold",]

level <- c("shiny gold")
oldRows <- 0

while(oldRows != nrow(shinygoldDF)) {
  oldRows <- nrow(shinygoldDF)
  level <- unlist(shinygoldDF$parent)
  shinygoldDF <-
    df[as.character(df$parent) %in% level |
         as.character(df$child1C) %in% level |
         as.character(df$child2C) %in% level |
         as.character(df$child3C) %in% level |
         as.character(df$child4C) %in% level, ]
}
nrow(shinygoldDF) - 1

[1] 164

Part 2

Caution

This solution is still under construction.

shorterDF <-
  longerDF |>
  dplyr::summarise(nChild = dplyr::n(), .by = c('parent', 'cChild'))

traverse <- function(shorterDF, start, i = 0) {
  if (length(start) == 1) return(i)
  tmp <- dplyr::filter(shorterDF, parent == start[1])
  if (nrow(tmp) == 0) return(traverse(shorterDF, start[-1], i + 1))
  traverse(shorterDF, tmp$cChild, i + 1)
}
traverse(shorterDF, 'shiny gold')

[1] 0

tibble::tibble(
  'parent' = c('shiny gold', 'red', 'orange', 'yellow', 'green', 'blue', 'violet'),
  'nChild' = c(2, 2, 2, 2, 2, 2, 0),
  'cChild' = c('red', 'orange', 'yellow', 'green', 'blue', 'violet', NA)
) |>
  tidyr::uncount(nChild, .remove = FALSE) -> longerDF

shorterDF <-
  longerDF |>
  dplyr::summarise(nChild = dplyr::n(), .by = c('parent', 'cChild'))
bags <- 
  c(longerDF$parent, longerDF$cChild) |>
  unique() |>
  sort() |>
  factor()
bags |>
  purrr::map_dbl(\(x) {
    x <-
      longerDF |>
      dplyr::select(parent, cChild) |>
      dplyr::mutate(dplyr::across(
        tidyselect::everything(),
        \(x) { purrr::map_dbl(x, \(x) { which(levels(bags) == x) }) }
      )) |>
      as.matrix() |>
      t() |>
      as.vector() |>
      igraph::make_graph(n = length(bags)) |>
      igraph::all_simple_paths(from = which(bags == 'shiny gold'), to = which(bags == x)) |>
      unlist()
    x <- x[x != which(bags == 'shiny gold')]
    shorterDF |>
      dplyr::filter(cChild %in% bags[x]) |>
      dplyr::pull(nChild) |>
      prod()
  }, .progress = TRUE) |>
  sum(-1)

[1] 126

2068 6268 6286 <16014