Advent of R: Dia 15

Quítons (A)

No 15º dia do AoC eu demorei muito mais do que deveria. Apesar de ter entendido bem o enunciado e ter identificado rapidamente o caminho para a solução, eu empaquei na implementação do algoritmo. No final achei melhor pegar uma versão pronta do algoritmo para não perder mais horas com isso.

Novamente o enunciado envolvia um submarino, uma caverna, etc. Passar por cada ponto da caverna vinha com um certo risco que variava entre 1 e 9 e nosso objetivo era levar o submarino do ponto esquerdo superior até o ponto esquerdo inferior passando pelo caminho com menor risco total. A saída do programa deveria ser a soma do risco de todos os pontos do caminho (sem incluir o ponto de entrada, pois já começávamos nele).

A esse ponto, qualquer um que tenha aprendido sobre grafos já deve estar com o sentido aranha ativado. Esse é um problema clássico da Computação que pode ser facilmente solucionado pelo algoritmo de Dijkstra. Algumas alterações são necessárias, mas todas podem ser feitas antes de executar o algoritmo.

O passo-a-passo do código é mais ou menos o seguinte:

1. Marcar todos os pontos como não visitados. Criar um conjunto com todos os pontos não visitador chamado conjunto não visitado.

2. Atribuir a todos os pontos um risco temporário: ele deve ser 0 para o nó inicial e infinito para o resto. O risco temporário de um ponto v é o risco total do caminho de menor risco já descoberto entre v e o ponto inicial. Como no começo não conhecemos nenhum outro ponto além do inicial, todos os riscos temporários começam como infinito. Fixar o ponto inicial como o atual.

3. Para o ponto atual, considerar todos os seus vizinhos não vizitados e calcular os seus riscos temporários através do ponto atual. Comparar o novo risco temporário ao risco atual e atribuir o menor dos dois. Por exemplo, se o risco do ponto atual A é 6 e o seu vizinho B tem risco 2, então o risco de chegar em B por A é 6 + 2 = 8. Se o risco temporário de B até agora era maior que 8, então ele deve virar 8. Caso contrário, nada muda.

4. Quando já tivermos considerado todos os vizinhos não visitados do ponto atual, marcar o ponto atual como visitado e removê-lo do conjunto não visitado. Um ponto visitado nunca será checado de novo.

5. Se o ponto final houver sido marcado como visitado, então parar. O algoritmo terminou e o risco total do melhor caminho até o distino é igual ao risco temporário que foi atribuido ao destino.

6. Caso contrário, selecionar o ponto não visitado que tem o menor risco temporário e torná-lo o ponto atual. Voltar ao passo 3.

Normalmente o algoritmo de Dijkstra é aplicado em grafos nos quais os custos de cada passo do caminho são atribuídos à arestas do grafo e não aos nós, como é o nosso caso. Para resolver esse problema, temos que fazer uma certa ginástica para que os custos sejam transferidos para as arestas. Cada par de nós vizinhos ganham duas arestas direcionadas, cada uma com o risco do nó para o qual ela aponta:

# Ponto atual com seus 4 vizinhos
#   7
# 9 3 1
#   6
#
# Arestas indo para o ponto atual (todas têm risco 3)
#       o
#       3
#       ↓
# o 3 → x ← 3 o
#       ↑
#       3
#       o
#
# Arestas saindo do ponto atual (todas têm o risco do vizinho)
#       o
#       ↑
#       7
# o ← 9 x 1 → o
#       6
#       ↓
#       o

Eu queria ter de fato implementado o algoritmo de Dijkstra no R por conta própria, mas eu cometi vários erros pelo caminho (eram 7:30, não me julgue) e, para não passar a manhã toda nisso, resolvi usar o pacote cppRouting para aplicar o algoritmo.

# Ler os riscos da caverna como uma matriz
cave <- "data-raw/15a_chiton.txt" |>
  readr::read_lines() |>
  stringr::str_split("") |>
  purrr::flatten_chr() |>
  as.integer() |>
  matrix(100, 100, byrow = TRUE)

# Criar uma tabela com os custos entre vizinhos
graph <- tibble::tibble()
for (i in 1:prod(dim(cave))) {

  vals <- c()
  if (i %% 100 != 0)  vals <- append(vals, i + 1L)
  if (i %% 100 != 1)  vals <- append(vals, i - 1L)
  if (i > 100)        vals <- append(vals, i - 100L)
  if (i < 9901)       vals <- append(vals, i + 100L)

  node <- tibble::tibble(from_vertex = i, to_vertex = vals, cost = cave[vals])
  graph <- dplyr::bind_rows(graph, node)
}

# Criar grafo e executar o algoritmo de Dijkstra
path <- graph |>
  cppRouting::makegraph(directed = TRUE) |>
  cppRouting::get_path_pair(from = 1L, to = 10000L) |>
  purrr::pluck(1) |>
  as.integer()

# Calcular o risco total do caminho (subtraíndo o custo da entrada)
graph |>
  dplyr::filter(to_vertex %in% path) |>
  dplyr::group_by(to_vertex) |>
  dplyr::summarise(cost = cost[1]) |>
  dplyr::summarise(risk = sum(cost)) |>
  dplyr::pull(risk) |>
  magrittr::subtract(cave[1])
#> [1] 811

Quítons (B)

O segundo item seguia a mesma lógica de outros problemas desse ano: igual ao primeiro item, mas maior. Como eu estava usando um algoritmo bastante eficiente, não tive problema nenhum nessa parte.

Aqui descobríamos que, na verdade, a caverna era 5 vezes maior em cada dimensão (ou seja, 25 vezes mais pontos). A caverna completa era, entretanto, composta por cópias da sessão original com riscos mais elevados; para obter a versão final da caverna era necessário juntar 25 cópias da original somando um certo fator a cada cópia.

# +0 +1 +2 +3 +4
# +1 +2 +3 +4 +5
# +2 +3 +4 +5 +6
# +3 +4 +5 +6 +7
# +4 +5 +6 +7 +8

Seguindo o guia acima, vemos que o canto superior esquerdo da caverna maior era igual à sessão original e, sucessivamente, chegávamos ao canto direito inferior, que era igual à sessão original, mas o risco de cada ponto era acrescido de 8. O único detalhe é que, quando o risco de um ponto passava de 9, ele voltava para 1 (igual aos polvos-dumbo que vimos anteriormente). O resto da solução era igual.

# Criar clones da caverna, somar fator de risco e juntar
cave <- cbind(
  rbind(cave + 0L, cave + 1L, cave + 2L, cave + 3L, cave + 4L),
  rbind(cave + 1L, cave + 2L, cave + 3L, cave + 4L, cave + 5L),
  rbind(cave + 2L, cave + 3L, cave + 4L, cave + 5L, cave + 6L),
  rbind(cave + 3L, cave + 4L, cave + 5L, cave + 6L, cave + 7L),
  rbind(cave + 4L, cave + 5L, cave + 6L, cave + 7L, cave + 8L)
)

# Reduzir pontos que passaram de 9
cave[cave > 9] <- cave[cave > 9] - 9