Advent of R: Dia 12

Busca de Caminho (A)

O dia 12, juntamente com os anteriores, começou a me deixar preocupado com os próximos exercícios do Advent of Code. Aparentemente a dificuldade vai aumentando conforme o passar dos dias, mas já estou chegando no limite do meu conhecimento.

Mais uma vez temos um enunciado complicado, então leia a versão original se ficar difícil de entender aqui. Nosso objetivo esta vez era contar o número de caminhos que o nosso submarino podia tomar em um sistema de cavernas.

A entrada era uma lista de arestas nomeadas em um grafo. Os nossos caminhos deveriam sempre começar na caverna chamada “start” e terminar na chamada “end”, sendo que todas as outras eram divididas em dois grupos: grandes e pequenas. Uma caverna grande era demarcada por uma letra maiúscula e podia ser utilizada pelo nosso caminho qualquer número de vezes. Já uma caverna pequena (demarcada por uma letra minúscula), só podia ser utilizada uma vez no caminho.

Veja o exemplo abaixo. A primeira parte seria a entrada do problema, a segunda, o diagrama das cavernas e a terceira, os 10 possíveis caminhos para o nosso submarino.

# start-A
# start-b
# A-c
# A-b
# b-d
# A-end
# b-end

#     start
#     /   \
# c--A-----b--d
#     \   /
#      end

# start,A,b,A,c,A,end
# start,A,b,A,end
# start,A,b,end
# start,A,c,A,b,A,end
# start,A,c,A,b,end
# start,A,c,A,end
# start,A,end
# start,b,A,c,A,end
# start,b,A,end
# start,b,end

Minha solução envolvia uma tabela que representava todas as arestas do grafo do sistema de cavernas. A cada nova recursão, a última caverna poderia ser mantida na tabela ou removida (no caso das cavernas pequenas); toda vez que um caminho chegasse ao “end”, um contador global era incrementado.

# Contar caminhos distintos em um grafo
count <- 0
count_paths <- function(graph, path = "start") {

  # Verificar se o nó atual é "pequeno"
  cave <- tail(path, 1)
  is_small <- stringr::str_to_lower(cave) == cave

  # Condições de parada
  if (cave == "end") {count <<- count + 1; return(1)}
  if (!any(graph$orig == cave)) return(0)

  # Encontrar próximo nó do caminho
  searches <- graph |>
    dplyr::filter(orig == cave) |>
    dplyr::pull(dest) |>
    purrr::map(purrr::prepend, path)

  # Atualizar nós disponíveis
  graph <- if (is_small) dplyr::filter(graph, orig != cave) else graph

  # Iterar nos possíveis caminhos
  for (search in searches) {
    count_paths(graph, search)
  }

  # Retornar contador global
  return(count)
}

# Ler arestas do grafo e retornar conta dos caminhos
"data-raw/12a_passage_pathing.txt" |>
  readr::read_table(col_names = "path") |>
  tidyr::separate(path, c("orig", "dest"), "-") |>
  {\(d) dplyr::bind_rows(d, purrr::set_names(d, rev(names(d))))}() |>
  dplyr::filter(dest != "start", orig != "end") |>
  count_paths()
#> [1] 4792

Busca de Caminho (B)

O segundo item do problema mudava muito pouco o enunciado. Agora, ao invés de cada caverna pequena poder ser visitada apenas 1 vez, tínhamos um pequeno acréscimo de tempo. Isso queria dizer que, em cada caminho até o final do sistema de cavernas, podíamos visitar apenas 1 das cavernas pequenas até 2 vezes.

Minha solução foi criar um argumento chamado boost que indicava se já tínhamos usado o nosso excedente de tempo naquele caminho expecífico. Se não tivéssemos, poderíamos não retirar uma das cavernas pequenas da lista imediatamente. Esta estratégia funcionou, mas gerou caminhos repetidos (usando e não usando o boost), então, ao invés de contar os caminhos, passei a salvar os caminhos e contar o número de caminhos distintos no final.

# Pegar todos os caminhos distintos em um grafo
all_paths <- list()
get_paths <- function(graph, path = "start", boost = FALSE) {

  # Verificar se o nó atual é "pequeno"
  cave <- tail(path, 1)
  is_small <- stringr::str_to_lower(cave) == cave

  # Condições de parada
  if (cave == "end") {all_paths <<- append(all_paths, list(path)); return(1)}
  if (!any(graph$orig == cave)) return(0)

  # Encontrar próximo nó do caminho
  searches <- graph |>
    dplyr::filter(orig == cave) |>
    dplyr::pull(dest) |>
    purrr::map(purrr::prepend, path)

  # Atualizar nós disponíveis
  graph_ <- if (is_small) dplyr::filter(graph, orig != cave) else graph

  # Iterar nos possíveis caminhos
  for (search in searches) {
    get_paths(graph_, search, boost = boost)

    # Uma opção é não remover o nó do grafo e usar o boost
    if (!boost && is_small && cave != "start") {
      get_paths(graph, search, boost = TRUE)
    }
  }

  # Retornar lista global
  return(all_paths)
}

# Ler arestas do grafo e retornar conta dos caminhos distintos
"data-raw/12b_passage_pathing.txt" |>
  readr::read_table(col_names = "path") |>
  tidyr::separate(path, c("orig", "dest"), "-") |>
  {\(d) dplyr::bind_rows(d, purrr::set_names(d, rev(names(d))))}() |>
  dplyr::filter(dest != "start", orig != "end") |>
  get_paths() |>
  purrr::map_chr(stringr::str_c, collapse = "|") |>
  unique() |>
  length()
#> [1] 133360