2021 Day 12

Author

Nathan Moore

— Day 12: Passage Pathing —

We have to find a way through this cave system.

How many paths through this cave system are there that visit small caves at most once?

library(tidyverse)
library(igraph)


Attaching package: 'igraph'

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

    %--%, union

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

    as_data_frame, groups, union

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

    compose, simplify

The following object is masked from 'package:tidyr':

    crossing

The following object is masked from 'package:tibble':

    as_data_frame

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

    decompose, spectrum

The following object is masked from 'package:base':

    union

my_file <- here::here("2021", "data-2021-12.txt")
x <- readLines(my_file)

Let’s create a matrix and see what links up.

pairs = strsplit(x, "-")
caves = unique(unlist(pairs))

cave_mat = matrix(FALSE, 
                  nrow=length(caves), 
                  ncol=length(caves), 
                  dimnames=list(caves,caves))

for (c in 1:length(x)) { 
    cave_mat[pairs[[c]][1], pairs[[c]][2]] = TRUE
}

cave_mat

         rf    RL    wz    AV    mh   end    dm    gy    cg    VI start    qk
rf    FALSE  TRUE  TRUE  TRUE  TRUE FALSE FALSE  TRUE FALSE FALSE FALSE FALSE
RL    FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
wz    FALSE  TRUE FALSE FALSE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE FALSE
AV    FALSE FALSE FALSE FALSE  TRUE FALSE FALSE  TRUE FALSE FALSE  TRUE FALSE
mh    FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
end   FALSE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE FALSE FALSE
dm     TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
gy    FALSE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
cg    FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE FALSE
VI    FALSE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE FALSE
start FALSE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE
qk    FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE

But also we could try a proper graph package

g = make_graph(edges=unlist(pairs), directed=FALSE)

plot(g)

# paths = all_simple_paths(g, "start", "end")

# 611 low