Advent of R: Dia 09

Bacia de Fumaça (A)

O dia 9 do AoC foi desafiador, apesar de não tanto quanto o anterior. Como sempre o problema envolvia uma historinha que não contribui muito para o entendimento do enunciado, então vamos direto ao ponto: recebemos uma matriz 100x100 que representa um mapa de alturas e precisávamos encontrar todos os pontos que eram cercados (em cima, embaixo, na esquerda e na direita) por pontos mais altos. Ademais sabíamos que as alturas iam de 0 a 9 e que as fronteiras fora do mapa podiam ser todas consideradas mais altas que o resto do mapa. A resposta do problema seria o risco total de todos os pontos baixos, onde o risco de um ponto é igual à sua altura + 1.

O problema não é tão complicado, pois bastaria iterar em todos os pontos da matriz e comparar cada um com seus vizinhos. O maior dezafio era lidar com as fronteiras do mapa. Para isso, resolvi cercar toda a matriz por noves e iterar no quadrado 2:101x2:101.

# Ler o mapa de alturas e estofar as fronteiras com 9
height <- "data-raw/09a_smoke_basin.txt" |>
  readr::read_lines() |>
  stringr::str_split("") |>
  purrr::flatten_chr() |>
  as.integer() |>
  matrix(nrow = 100, ncol = 100, byrow = TRUE) |>
  rbind(rep(9, 100)) |>
  {\(m) rbind(rep(9, 100), m)}() |>
  cbind(rep(9, 102)) |>
  {\(m) cbind(rep(9, 102), m)}()

# Iterar por todos os pontos
risk <- 0
for (i in 2:101) {
  for (j in 2:101) {

    # Verificar se é um ponto baixo e somar o risco ao total
    if (
      height[i, j] < height[i - 1, j] &&
      height[i, j] < height[i + 1, j] &&
      height[i, j] < height[i, j - 1] &&
      height[i, j] < height[i, j + 1]
    ) {
      risk <- risk + height[i, j] + 1
    }
  }
}

# Imprimir
risk
#> [1] 494

Bacia de Fumaça (B)

O segundo item já era mais complicado. Considerando que os pontos com altura 9 não pertencem a nenhuma bacia, precisávamos encontrar as 3 maiores bacias no nosso mapa. Uma bacia é definida por toda uma região cercada por noves e seu tamanho é igual ao número de pontos contíguos contidos nessa área.

O diagrama abaixo não estava no enunciado, mas ele me ajudou muito a entender o que era uma bacia. Para criá-lo, eu peguei um retângulo na ponta do meu mapa e substituí todos os números menores que 9 por um ., representando assim as bacias. Cada região cercada por noves é uma bacia diferente.

# ....999.........9.9....99......9....9..........9
# ...9.9.9.......9...9..9.......9.9...99.99.9.....
# ..9.....9.9.....9...99...........999.999.9.9....
# ..9......9.9...9....999.........9..9..9.....999.
# 99..........999......9999......9..9..9.....9...9
# ...........9..9........99...9.9.......9.........
# 9..............9...9..9..9.99.9......9..........
# ...........99.9...9.99....9..99.....9...........
# ............99....9..9.......9.......9..........
# 9........99999...9....9.9....9.......999........

Minha solução começou igual à do item anterior, mas desta vez criei também uma tabela com todos os pontos do mapa. Meu objetivo era fazer uma busca em largura e remover desta tabela os pontos já explorados.

# Criar uma tabela de pontos a explorar
points <- purrr::cross2(2:101, 2:101) |>
  purrr::map(purrr::flatten_int) |>
  purrr::transpose() |>
  purrr::set_names("i", "j") |>
  tibble::as_tibble() |>
  tidyr::unnest(c(i, j))

A seguir eu criei uma função que explorava uma bacia a partir de um ponto “semente”. O primeiro passo era verificar se o ponto já tinha sido explorado e retornar 0 se sim (indicando que aquele ponto não contribuiria mais para o tamanho da bacia). Se o ponto não tivesse sido explorado, então o código o removia da tabela de pontos e verificava se ele tinha altura 9, mais uma vez retornando 0 se sim. O final da função aplicava uma recursão nos 4 vizinhos do ponto, somando os tamanhos das 4 sub-bacias encontradas mais 1 (indicando que o ponto “semente” contribuia em 1 para o tamanho total da bacia).

# Explorar uma bacia
explore <- function(a, b) {

  # Pular se o ponto já tiver sido explorado
  if (nrow(dplyr::filter(points, i == a, j == b)) == 0) return(0)

  # Marcar o ponto como explorado
  points <<- dplyr::filter(points, i != a | j != b)

  # Se a altura for 9, então ele não faz parte da bacia
  if (height[a, b] == 9) return(0)

  # Adicionar os pontos vizinhos à bacia
  return(
    explore(a - 1, b) +
    explore(a + 1, b) +
    explore(a, b - 1) +
    explore(a, b + 1) + 1
  )
}

A resposta para o item era o produto dos tamanhos das 3 maiores bacias do mapa, então o programa terminava iterando na matriz, calculando o tamanho de todas as bacias e seguindo para obter o resultado final.

# Iterar por todos os pontos
basins <- matrix(rep(0, 10404), 102, 102)
for (i in 2:101) {
  for (j in 2:101) {
    basins[i, j] <- explore(i, j)
  }
}

# Multiplicar as 3 maiores bacias
basins |>
  sort(decreasing = TRUE) |>
  magrittr::extract(1:3) |>
  prod()
#> [1] 1048128