Advent of R: Dia 20

Mapa da Fossa (A)

Depois de um domingo assustadoramente difícil, o problema do dia 20 do AoC foi bastante tranquilo de resolver. Tanto o enunciado quanto a solução me pareceram simples (apesar de algumas reclamações na internet sobre uma pegadinha que vou explicar em breve).

Hoje nós recebemos uma imagem na forma de uma matriz composta por pontos luminosos # e pontos escuros .. O outro componente da entrada era uma lista de “conversões”: nós deveríamos converter cada quadrado 3x3 da imagem em um número binário onde # = 1 e . = 0 e encontrar o elemento de índice correspondente da lista de conversões; o ponto do centro do quadrado deveria ser substituido por esse elemento da lista.

# Um quadrado 3x3
# # . . # .
# #[. . .].
# #[# . .]#
# .[. # .].
# . . # # #
#
# Número correspondente
# ...#...#. = 000100010 = 34
#
# 34o elemento da lista de conversões
# 0         10        20        30 [34]   40        50        60        70
# |         |         |         |   |     |         |         |         |
# ..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##

Entretanto, essa operação, denominada realce, tinha um detalhe a mais. A nossa imagem de entrada era, na verdade, infinita! Em todas as direções, a imagem deveria ser completa por infinitos pontos escuros. Nosso objetivo era contar o número de pontos luminosos que restavam na nossa imagem após 2 aplicações do realce.

Como é possível imaginar, os pontos escuros infinitos não podem fazer diferença nessa contagem (senão a resposta seria incalculável). Note que um quadrado composto só por pontos escuros equivale ao índice 0 da lista e, no exemplo acima, isso é convertido para um novo ponto escuro; ou seja, as bordas infinitas continuam sendo escuras após o realce.

A pegadinha, porém, era que a lista de conversões na entrada do problema começava com # e não ., ou seja, os infinitos pontos escuros iam virar infinitos pontos luminosos depois de um realce. Felizmente, na segunda aplicação, todos os quadrados luminosos apontariam para o 511º elemento da lista e esse sim era um .. Em conclusão, desde que aplicássemos um número par de realces, as fronteiras infinitas da imagem seriam escuras e o número de pontos luminosos poderia ser contado.

Sendo assim, o código que resolvia o problema era bem simples, bastava adicionar uma borda escura à imagem para levar em conta a fronteira infinita e seguir em frente.

# Converter uma região 3x3 em um número
img_to_int <- function(image) {

  # Achatar a matriz para uma só coluna
  bits <- ifelse(image == ".", 0, 1)
  binary <- paste0(as.vector(t(bits)), collapse = "")

  # String para inteiro
  strtoi(binary, base = 2)
}

# Aplicar realce
enhance <- function(image, algo) {

  # Iterar nas linhas e colunas, sem passar pela borda
  new_image <- image
  for (i in 2:(nrow(image) - 1)) {
    for (j in 2:(ncol(image) - 1)) {

      # Trocar [i,j] pelo índice correspondente em `algo`
      ind <- img_to_int(image[(-1:1 + i), (-1:1 + j)])
      new_image[i, j] <- algo[ind + 1]
    }
  }

  # Remover borda e retornar
  new_image[2:(nrow(image) - 1), 2:(ncol(image) - 1)]
}

# Adicionar borda
add_padding <- function(image) {

  # Adicionar mais 2 linhas em cima e embaixo
  image <- rbind(
    image[1, ], image[1, ],
    image,
    image[nrow(image), ], image[nrow(image), ]
  )

  # Adicionar 2 colunas na esquerda e na direita
  image <- cbind(
    image[, 1], image[, 1],
    image,
    image[, ncol(image)], image[, ncol(image)]
  )

  return(image)
}

# Ler lista de realce como um vetor de strings
algo <- "data-raw/20a_trench_map.txt" |>
  readr::read_lines(n_max = 1) |>
  stringr::str_split("") |>
  purrr::pluck(1)

# Ler imagem como uma matriz (e adicionar bordas)
image <- "data-raw/20a_trench_map.txt" |>
  readr::read_lines(skip = 2) |>
  purrr::prepend(rep(paste0(rep(".", 100), collapse = ""), 3)) |>
  append(rep(paste0(rep(".", 100), collapse = ""), 3)) |>
  {\(s) stringr::str_c("...", s, "...")}() |>
  stringr::str_split("") |>
  purrr::flatten_chr() |>
  matrix(106, 106, byrow = TRUE)

# Aplicar o realce duas vezes e contar pontos luminosos
image |>
  enhance(algo) |>
  add_padding() |>
  enhance(algo) |>
  magrittr::equals("#") |>
  sum()
#> [1] 5498

Mapa da Fossa (B)

O segundo item pedia apenas para aplicarmos o algoritmo 50 ao invés de 2 vezes e contar o número de pontos luminosos. Como o nosso algoritmo generaliza as bordas, podemos simplesmente aplicá-lo mais vezes.

# Aplicar o realce 50 vezes
image <- enhance(image, algo)
for (i in seq_len(49)) {
  image <- enhance(add_padding(image), algo)
}

# Contar pontos luminosos
image |>
  magrittr::equals("#") |>
  sum()
#> [1] 16014