Advent of R: Dia 16

Decodificador de Pacotes (A)

O 16º problema do AoC foi bastante diverido. O enunciado era extremamente longo e cheio de detalhes, mas consegui fazer uma implementação direta e eficiente que só não funcionou de primeira por causa de um detalhe obscuro da função strtoi().

Hoje nosso objetivos era decodificar pacotes binários. Eles chegavam ao nosso submarino em hexadecimal e, depois de convertidos para binário eles tinham as seguintes características:

• Os 3 primeiros bits representavam a versão do pacote;

• Os 3 bits seguintes representavam o tipo do pacote, que podia cair em dois casos:

  • Se o tipo (na forma decimal) fosse igual a 4, então o pacote representaria um valor. Isso queria dizer que o resto do pacote poderia ser quebrado em pedaços de 5 bits com a seguinte configuração:

    • Se o pedaço começasse com 1, então os 4 bits a seguir eram parte do valor e deveríamos continuar lendo o pacote;

    • Se o pedaço começassem em 0, então os 4 bits a seguir eram o final do valor e poderíamos parar de ler o pacote.

  • Se o tipo do pacote fosse diferente de 4, então o pacote representaria um operador. Isso queria dizer que o bit de número 7 indicava o modo do pacote:

    • Se o indicador fosse 1, então os próximos 15 bits seriam iguais à soma dos comprimentos de todos os sub-pacotes contidos naquele pacote operador;

    • Se o indicador fosse 0, então os próximos 11 bits seriam iguais ao número de sub-pacotes contidos naquele pacote operador.

Simples? Longe disso. Vejamos alguns exemplos:

# Pacote literal (valor)
# D2FE28
# 110100101111111000101000
# VVVTTTAaaaaBbbbbCcccc
#
# - VVV são a versão do pacote, 6.
# - TTT são o tipo, 4. Então este pacote carrega um valor.
# - A é 1 (continuar lendo), então aaaa são o primeiro pedaço do valor.
# - B é 1 (continuar lendo), então bbbb são o segundo pedaço do valor.
# - C é 0 (parar de ler), então cccc são o último pedaço do valor.
# - O resto são bits extras.
# - Portanto, o valor carregado por este pacote é 011111100101 = 2021.
#
# Pacote operador com indicador 0
# 38006F45291200
# 00111000000000000110111101000101001010010001001000000000
# VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB
#
# - VVV são a versão do pacote, 1.
# - TTT são o tipo, 6. Então este pacote carrega um operador.
# - I é o indicador, 0. Então este pacote tem 15 bits com os comprimentos
#   dos sub-pacotes.
# - LLLLLLLLLLLLLLL contêm a soma dos comprimentos dos sub-pacotes, 27.
# - AAAAAAAAAAA são um sub-pacote carregando um valor, 10.
# - BBBBBBBBBBBBBBBB são um sub-pacote carregando um valor, 20.
#
# Pacote operador com indicador 1
# EE00D40C823060
# 11101110000000001101010000001100100000100011000001100000
# VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC
# - VVV são a versão do pacote, 7.
# - TTT são o tipo, 3. Então este pacote carrega um operador.
# - I é o indicador, 1. Então este pacote tem 11 bits com os número de
#   sub-pacotes.
# - LLLLLLLLLLL contêm o número de sub-pacotes, 3.
# - AAAAAAAAAAA são um sub-pacote carregando um valor, 1.
# - BBBBBBBBBBB são um sub-pacote carregando um valor, 2.
# - CCCCCCCCCCC são um sub-pacote carregando um valor, 3.

O ponto positivo desse enunciado enorme é que conseguimos implementar os recursos necessários quase em sequência.

# Converter string hexadecimal para string binária
hex_to_bits <- function(hex) {
  hex |>
    stringr::str_split("") |>
    purrr::pluck(1) |>
    purrr::map(~paste(rev(as.integer(intToBits(strtoi(.x, 16)))))) |>
    purrr::map(magrittr::extract, 29:32) |>
    purrr::flatten_chr() |>
    stringr::str_c(collapse = "")
}

# Pegar a versão de um pacote
get_version <- function(pkt) {
  strtoi(stringr::str_sub(pkt, 1, 3), 2)
}

# Pegar o tipo de um pacote
get_type <- function(pkt) {
  strtoi(stringr::str_sub(pkt, 4, 6), 2)
}

O objetivo final deste item era parsear a hierarquia de pacotes da nossa entrada e somar as versões de todos. Minha solução envolveu, desta forma, cirar uma “classe” que podia conter a versão e o comprimento de um pacote. O comprimento era importante para descartar o número certo de bits do pacote quando tivéssemos terminado de processar um sub-pacote.

Se um pacote fosse do tipo operador, então sua “classe” também conteria todos os seus sub-pacotes como elementos sem nome. O código abaixo implementa o processamento dos dois tipos de pacotes; note como foram implementadas as “classes”:

# Pegar o valor de um pacote literal
get_literal <- function(pkt) {
  interval <- c(7, 11)

  # Iterar até o último pedaço ser encontrado
  literal <- ""
  flag <- FALSE
  while (!flag) {

    # Pegar o grupo especificado pelo intervalo
    group <- stringr::str_sub(pkt, interval[1], interval[2])
    literal <- stringr::str_c(literal, stringr::str_sub(group, 2))

    # Parar se este é o último pedaço, caso contrário somar 5 ao intervalo
    if (!as.integer(stringr::str_sub(group, 1, 1))) {
      flag <- TRUE
    } else {
      interval <- interval + 5
    }
  }

  # Retornar a "classe" que descreve o pacote
  return(list(
    version = get_version(pkt),
    len = interval[2],
    value = strtoi(literal, 2)
  ))
}

# Processar um pacote operador
get_operator <- function(pkt) {
  indicator <- stringr::str_sub(pkt, 7, 7)

  # Inicializar "classe"
  out <- list(
    version = get_version(pkt)
  )

  # Lidar com os 2 indicadores
  if (as.integer(indicator)) {

    # Pegar o número de sub-pacotes e separar a cauda do pacote
    num <- strtoi(stringr::str_sub(pkt, 8, 18), 2)
    rest <- stringr::str_sub(pkt, 19)
    out$len <- 18

    # Iterar no número de pacotes
    for (i in seq_len(num)) {

      # Processar sub-pacote
      sub <- if (get_type(rest) == 4) get_literal(rest) else get_operator(rest)
      out$len <- out$len + sub$len
      out <- c(out, list(sub))

      # Atualizar a cauda dado o compimento do último sub-pacote
      rest <- stringr::str_sub(rest, sub$len + 1)
    }
  } else {

    # Pegar o limite de comprimento dos sub-pacotes e separar a cauda
    lim <- strtoi(stringr::str_sub(pkt, 8, 22), 2)
    rest <- stringr::str_sub(pkt, 23)
    out$len <- 22

    # Iterar enquanto os sub-pacotes não tiverem passado do limite
    while (lim > 0) {

      # Processar sub-pacote
      sub <- if (get_type(rest) == 4) get_literal(rest) else get_operator(rest)
      out$len <- out$len + sub$len
      out <- c(out, list(sub))

      # Atualizar a cauda dado o compimento do último sub-pacote
      rest <- stringr::str_sub(rest, sub$len + 1)
      lim <- lim - sub$len
    }
  }

  return(out)
}

O último passo do meu código era achatar toda a estrutura de árvore que seria devolvida pelas funções acima e somar todos os comprimentos.

# Somar todas as versões do pacote representado por um hex
sum_versions <- function(hex) {

  # Pegar a árvore de pacotes representada pelo hex
  pkt <- hex_to_bits(hex)
  pkts <- if (get_type(pkt) == 4) get_literal(pkt) else get_operator(pkt)

  # Achatar árvore
  while (purrr::vec_depth(pkts) > 2) {
    pkts <- purrr::flatten(pkts)
  }

  # Somar versões
  pkts |>
    magrittr::extract(names(pkts) == "version") |>
    purrr::reduce(sum)
}

# Ler pacotes de um hex e somar versões
"data-raw/16a_packet_decoder.txt" |>
  readr::read_lines() |>
  sum_versions()
#> [1] 991

Decodificador de Pacotes (B)

O segundo item era mais ou menos o que eu já esperava. Os tipos dos pacotes tinham um significado maior, ou seja, cada sub-tipo de pacote operador indicava uma operação matemática que deveria ser aplicada no valor dos seus sub-pacotes.

• A operação 0 é soma (sum()).

• A operação 1 é produto (prod()).

• A operação 2 é mínimo (min()).

• A operação 3 é máximo (max()).

• A operação 5 é maior que (>).

• A operação 6 é menor que (<).

• A operação 7 é igual (==).

Ou seja, se um pacote tiver a estrutura (operador + (operador * (valor 1) (valor 2)) (valor 3)), então a expressão aritmética resultante seria (1 * 2) + 3). Nosso objetivo final era calcular o valor da expressão que o nosso pacote representava. Felizmente, o meu script anterior funcionava muito bem com essa alteração!

Eu troquei o elemento version da “classe” por type (o tipo do operador) e adicionei o seguinte no final do código:

# Avaliar a árvore de pacotes
get_value <- function(tree) {

  # Funções correspondentes aos tipos
  fun <- switch(as.character(tree$type),
    "0" = sum,
    "1" = prod,
    "2" = min,
    "3" = max,
    "5" = `>`,
    "6" = `<`,
    "7" = `==`,
  )

  # Aplicar função aos sub-pacotes
  apply_fun <- function(tree) {
    tree |>
      purrr::keep(names(tree) == "") |>
      purrr::map(get_value) |>
      purrr::reduce(fun)
  }

  # Aplicar recursivamente
  if (tree$type == 4) tree$value else as.numeric(apply_fun(tree))
}

# Decodificar a expressão de um pacote hex
decode <- function(hex) {
  pkt <- hex_to_bits(hex)
  tree <- if (get_type(pkt) == 4) get_literal(pkt) else get_operator(pkt)

  get_value(tree)
}

# Ler pacotes de um hex e calcular o valor da expressão
"data-raw/16b_packet_decoder.txt" |>
  readr::read_lines() |>
  decode() |>
  format(scientific = FALSE)
#> [1] 1264485568252

P.S.: Mas isso não funcionou de primeira! Eu recebi um belo NA ao final da execução e demorei para entender a causa… No final eu descobri que a função strtoi() retorna NA quando o resultado é grande demais. A solução foi trocá-la por uma função própria:

strton <- function(x) {
  y <- as.numeric(strsplit(x, "")[[1]])
  sum(y * 2^rev((seq_along(y) - 1)))
}