Advent of R: Dia 14

Polimerização Estendida (A)

O 14º dia do AoC foi muito demorado de resolver para mim. Apesar de ambas as soluções abaixo serem “simples”, levei horas para encontrar um jeito razoável de resolver o segundo item e, infelizmente, só consegui depois de olhar uma dica na internet que deixou tudo mais simples.

Desta vez nossa missão era estender um molde de polímero através de um conjunto de regras de reação. A primeira linha da entrada era o molde e, a partir daí, tínhamos as regras de inserção:

# NNCB
#
# CH -> B
# HH -> N
# CB -> H
# NH -> C
# HB -> C
# HC -> B
# HN -> C
# NN -> C
# BH -> H
# NC -> B
# NB -> B
# BN -> B
# BB -> N
# BC -> B
# CC -> N
# CN -> C

As regras eram fáceis de entender. Cada uma delas indicava que, quando os dois elementos da esquerda se encontravam, entre eles apareceria o elemento da direita. Uma rodada de reação envolvia estender todos os pares da cadeia polimérica; no caso do exemplo, isso transformaria NNCB em NCNBCHB.

Após 10 iterações, deveríamos contar o número de ocorrências do elemento mais comum da cadeia e subtrair dele o número de ocorrências do elemento menos comum da cadeia. Esta seria a resposta do problema.

Meu código para o primeiro item acabou seguindo o que chamamos de estratégia de força bruta. A cada iteração, eu quebrava o polímero nos seus pares de elementos e fazia um join com a tabela de regras; depois era só colar tudo em uma string só e seguir em frente. No final eu só precisava encontrar as letras mais e menos comuns da string e subtraí-las.

# Ler modelo como string
poly <- readr::read_lines("data-raw/14a_extended_polymerization.txt", n_max = 1)

# Ler regras como tabela
rules <- "data-raw/14a_extended_polymerization.txt" |>
  readr::read_table(skip = 1, col_names = FALSE) |>
  purrr::set_names("pair", "rm", "insertion") |>
  dplyr::select(-rm) |>
  dplyr::mutate(insertion = stringr::str_replace(
    pair, "(.)(.)", paste0("\\1", insertion, "\\2")
  ))

# Executar uma rodada de inserções
do_insertions <- function(poly) {
  poly |>
    stringr::str_split("") |>
    purrr::pluck(1) |>
    purrr::accumulate(~paste0(stringr::str_sub(.x, -1), .y)) |>
    utils::tail(-1) |>
    purrr::map_chr(~rules[rules$pair == .x, ]$insertion) |>
    purrr::reduce(~paste0(.x, stringr::str_sub(.y, -2))) |>
    stringr::str_c(collapse = "")
}

# Rodar do_insertions() 10 vezes e fazer el. mais comum - el. menos comum
10 |>
  seq_len() |>
  purrr::reduce(~do_insertions(.x), .init = poly) |>
  stringr::str_split("") |>
  table() |>
  {\(t) list(t[which.max(t)], t[which.min(t)])}() |>
  purrr::reduce(`-`) |>
  abs() |>
  unname()
#> [1] 2584

Polimerização Estendida (B)

O segundo item parecia suspeitamente simples, mas eu estava redondamente enganado. A única instrução era repetir o problema do primeiro item para 40 iterações ao invés de 10. Pode parecer que eu não precisaria nem mudar meu código, mas note que no primeiro item a minha cadeia polimérica só chegou a ter 19457 letras. No segundo item a cadeia chegaria a… mais de 20 trilhões.

Seria necessário mudar de estratégia e foi aí que eu empaquei. Tentei diversas formas de manter apenas o número de letras na cadeia, sem armazenar a cadeia em si, mas nada funcionava. Eu até notei que a primeira e a última letras da cadeia nunca mudavam, mas isso não me ajudou.

Depois de procurar por dicas no subreddit do AoC, finalmente achei uma boa alma que havia feito uma observação incrível:

Sempre podemos manter apenas a contagem de pares distintos na cadeia. Se tivermos, por exemplo, um par AC aparecendo n = 10 vezes na cadeia e uma regra AC -> B, então na próxima iteração podemos adicionar à nossa contagem AB e BC, cada uma aparecendo n = 10 vezes.

Até aí eu já sabia, era essencialmente o que eu fazia manualmente no item 1. O problema é que, mantendo apenas as contagens dos pares, isso repetiria a letra B duas vezes, totalizando A 10 vezes, C 10 vezes e B 20 vezes. A ideia que veio a seguir, entretanto, foi o que realmente resolveu o problema:

Se pensarmos na cadeia como um todo, todos as letras serão contadas 2 vezes, exceto pela primeira e pela última, pois elas nunca ficam no meio de uma reação. O número de ocorrências de cada letra é, portanto, n / 2, exceto pelas letras que aparecem no início e no fim, paras quais a fórmula é (n + 1) / 2.

Depois disso o item 2 podia ser solucionado facilmente.

# Registrar a primeira e a última letras da cadeia original
orig <- "data-raw/14b_extended_polymerization.txt" |>
  readr::read_lines(n_max = 1) |>
  stringr::str_replace("^(.).*?(.)$", "\\1\\2") |>
  stringr::str_split("") |>
  purrr::pluck(1)

# Ler modelo já no formato de contagem de pares
poly <- "data-raw/14b_extended_polymerization.txt" |>
  readr::read_lines(n_max = 1) |>
  stringr::str_split("") |>
  purrr::pluck(1) |>
  purrr::accumulate(~paste0(stringr::str_sub(.x, -1), .y)) |>
  utils::tail(-1) |>
  tibble::tibble() |>
  purrr::set_names("pair") |>
  dplyr::count(pair)

# Ler regras como tabela
rules <- "data-raw/14b_extended_polymerization.txt" |>
  readr::read_table(skip = 1, col_names = FALSE) |>
  purrr::set_names("pair", "rm", "insertion") |>
  dplyr::select(-rm) |>
  dplyr::mutate(insertion = stringr::str_replace(
    pair, "(.)(.)", paste0("\\1", insertion, "\\2")
  ))

# Executar uma rodada de inserções
do_insertions <- function(poly) {
  poly |>
    dplyr::left_join(rules, "pair") |>
    dplyr::mutate(
      insertion = purrr::map(insertion, stringr::str_extract, c("^..", "..$"))
    ) |>
    tidyr::unnest(insertion) |>
    dplyr::group_by(pair = insertion) |>
    dplyr::summarise(n = sum(n))
}

# Rodar do_insertions() 40 vezes e fazer el. mais comum - el. menos comum
40 |>
  seq_len() |>
  purrr::reduce(~do_insertions(.x), .init = poly) |>
  dplyr::mutate(elem = stringr::str_split(pair, "")) |>
  tidyr::unnest(elem) |>
  dplyr::group_by(elem) |>
  dplyr::summarise(n = sum(n)) |>
  dplyr::mutate(
    n = ifelse(elem %in% orig, n + 1, n),
    n = n / 2
  ) |>
  dplyr::filter(n == max(n) | n == min(n)) |>
  dplyr::pull(n) |>
  purrr::reduce(`-`) |>
  abs() |>
  format(scientific = FALSE)
#> [1] 3816397135460