Advent of R: Dia 17

Cesta de Três (A)

O 17º dia do AoC foi uma ótima quebra em relação aos últimos. O enunciado era simples de entender e a solução foi fácil de criar, tudo que eu precisava depois de uma semana cansativa.

Hoje precisávamos tentar encontrar a chave do nosso submarino em uma fossa marinha. A sonda que tínhamos a bordo podia ser arremessada a partir do ponto (0, 0) com qualquer velocidade inteira tanto no eixo x quanto no y. A entrada do problema era a posição do alvo e a saída do primeiro item deveria ser a altura máxima que podíamos arremessar a sonda de modo que ela ainda atingisse o alvo.

As regras para a aceleração da sonda a cada passo eram as seguintes:

• A posição x da sonda aumenta um valor igual à sua velocidade x.

• A posição y da sonda aumenta um valor igual à sua velocidade y.

• Por causa do atrito, a velocidade x da sonda muda em 1 um direção a 0 (ou seja, ela diminui em 1 se a velocidade for maior que 0 e aumenta em 1 caso contrário).

• Por causa da gravidade, a velocidade y da sonda diminui em 1.

O grande truque do exercício era identificar todas as velocidades possíveis da sonda e depois verificar qual o levava à maior altura. Como o alvo estava sempre abaixo e à direita do (0, 0), podíamos estabelecer os limites inferiores e superiores para as velocidades x e y:

• A velocidade x necessariamente tem que ser maior que 0, já que precisamos que a sonda se mova para frente. Adicionalmente, velocidade x máxima não pode ser maior que a fronteira direita do alvo; se o alvo terminar, por exemplo, em x = 10, nunca vamos acertá-lo jogando o módulo para frente com velocidade maior que 10.

• Os limites da velocidade y são mais difícil de entender. Em primeiro lugar, ela nunca pode ser menor do que a fronteira inferior do alvo (pensando na mesma lógica que usamos antes, se o alvo terminar, por exemplo, em y = -10, nunca vamos acertá-lo jogando a sonda para baixo com velocidade menor que -10). O limite superior vem do fato de que se jogarmos a sonda para cima, não importando a velocidade, ela eventualmente vai voltar a y = 0 com velocidade igual à velocidade inicial menos 1, mas com sinal negativo; sendo assim, a velocidade y máxima é igual ao valor absoluto do limite inferior do alvo.

# Velocidade inicial: (6,3)
# ..................................
# .........(3,0).#..#.(2,-1)........
# .....(4,1).#........#.(1,-2)......
# ..................................
# (5,2).#..............#.(0,-3).....
# ..................................
# ..................................
# S.(6,3)..............#.(0,-4).....
# ..................................
# ..................................
# ..................................
# .....................#.(0,-5).....
# ....................TTTTTTTTTTT...
# ....................TTTTTTTTTTT...
# ....................TTTTTTTTTTT...
# ....................TTTTTTTTTTT...
# ....................T#T(0,-6)TT...
# ..................................
# ..................................

Note no diagrama acima a simetria da trajetória no eixo y. Assim fica mais fácil entender porque, por exemplo, se o limite inferior do alvo for y = -10, então nunca podemos jogar a sonda para cima com velocidade maior que 9; ela voltará para y = 0 com velocidade -10 e acertará exatamente a fronteira de baixo do alvo.

# Ler alvo como uma tabela de coordenadas
target <- "data-raw/17a_trick_shot.txt" |>
  readr::read_lines() |>
  stringr::str_split("[=,]") |>
  purrr::pluck(1) |>
  stringr::str_subset("^[0-9-]") |>
  stringr::str_replace("\\.\\.", ":") |>
  purrr::map(~eval(parse(text = .x))) |>
  purrr::cross() |>
  purrr::transpose() |>
  purrr::set_names("x", "y") |>
  tibble::as_tibble() |>
  tidyr::unnest(c(x, y))

# Todas as possíveis combinações de velocidades x e y válidas
vels <- purrr::cross(list(
  1:max(target$x),
  min(target$y):abs(min(target$y))
))

Para calcular a altura máxima que poderíamos arremessar a sonda, eu simulei a trajetória a partir de cada um dos pares de velocidades válidas e guardei a altura máxima à qual a sonda chegava. No final da iteração, se a sonda de fato atingisse o alvo, então eu comparava a altura máxima dessa combinação com a altura máxima global e mantinha a maior.

# Verificar quais pares de velocidades funcionam e pegar a altura máxima
max_height <- 0
for (vel in vels) {

  # Posição inicial
  x_pos <- 0
  y_pos <- 0

  # Velocidades iniciais
  x_vel <- vel[[1]]
  y_vel <- vel[[2]]

  # Encontrar a altura máxima deste par de velocidades
  max_height_ <- 0
  while (y_pos >= min(target$y) && x_pos <= max(target$x)) {

    # Atualizar posições
    x_pos <- x_pos + x_vel
    y_pos <- y_pos + y_vel

    # Atualizar altura máxima local
    if (y_pos > max_height_) max_height_ <- y_pos

    # Se o par de fato leva ao alvo, atualizar altura máxima global
    if (x_pos %in% target$x && y_pos %in% target$y) {
      if (max_height_ > max_height) max_height <- max_height_
    }

    # Atualizar velocidades
    x_vel <- if (x_vel > 0) x_vel - 1 else 0
    y_vel <- y_vel - 1
  }
}

# Retornar a altura máxima global
max_height
#> [1] 4753

Cesta de Três (B)

Chegando no item 2, eu percebi que tinha dado muita sorte. O enunciado aqui pedia para encontrarmos o número de velocidades iniciais da sonda que a faziam chegar ao alvo. Meu código anterior já encontrava todos os pares válidos, mas utilizava isso para atualizar a altura máxima; só era necessário trocar a variável sendo atualizada dentro do while.

# Verificar pares de velocidades que funcionam e contá-los
n_works <- 0
for (vel in vels) {

  # Posição inicial
  x_pos <- 0
  y_pos <- 0

  # Velocidades iniciais
  x_vel <- vel[[1]]
  y_vel <- vel[[2]]

  # Encontrar a altura máxima deste par de velocidades
  max_height_ <- 0
  while (y_pos >= min(target$y) && x_pos <= max(target$x)) {

    # Atualizar posições
    x_pos <- x_pos + x_vel
    y_pos <- y_pos + y_vel

    # Se o par de fato leva ao alvo, atualizar contador
    if (x_pos %in% target$x && y_pos %in% target$y) {
      n_works <- n_works + 1
      break
    }

    # Atualizar velocidades
    x_vel <- if (x_vel > 0) x_vel - 1 else 0
    y_vel <- y_vel - 1
  }
}

# Retornar número de velocidades que funcionam
n_works