07: Bridge Repair

library(mistlecode)

options(scipen = 999)

mat <-
  'input.txt' |>
  readLines() |>
  stringr::str_split(':| ', simplify = TRUE) |>
  mistlecode::cast_matrix(as.numeric)
mat <- mat[,-2]

Part 1

Okay. At first glance this is some fancy math one that I don’t know enough math to do correctly. After fiddling around a bit and getting it working on the test input, it was time to move to the real one. For ages I kept getting the same wrong output. I thought that maybe it’s because I needed bit64 for 64 bit integers and spent way too long screwing around with that then eventually realized that not only was my input not being read properly (that seems to be a theme this year…), but that the numbers can be double and that solves all my problems. They’re still whole numbers, just not integers. After realizing that, it was a lot of head scratching until I realized that my if statement with return(total) was inside my second for loop when it should be after it. Fixing that led to a victory.

totals <-
  mat |>
  apply(1, \(r) {
    target <- r[1]; r <- r[-1]; r <- r[!is.na(r)];
    grid <- expand.grid(rlang::inject(rep(list(c('*', '+')), length(r) - 1)))
    for (g in seq_len(nrow(grid))) {
      ops <- grid[g,] |> unlist() |> unname(); total <- 0;
      for (i in seq_along(r)[-1]) {
        if (i == 2) {
          total <- if (ops[i-1] == '+') r[i-1] + r[i] else r[i-1] * r[i]
        } else {
          total <- if (ops[i-1] == '+') total + r[i] else total * r[i]
        }
      }
      if (target == total) return(total)
    }
    return(0)
  }) 
part1 <-
  totals |> 
  sum() |>
  print()

[1] 945512582195

Part 2

I spent a while on part 2 as well, but had more of a plan than part 1. I initially had a cool little recursion method that used the same expand.grid and collapsed the string in on itself. It ultimately didn’t end up working and I’m not really sure why. Moving the operations into a function helped make things more readable and then it was just a matter of collapsing the string the right way every time and waiting a while for everything to run. After getting my answer I realized I could reduce grid even further by filtering for rows that contain a concatenate operation since the new numbers must have one.

tictoc::tic()
future::plan(future::multisession, workers = future::availableCores())
progressr::with_progress({
  do_op <- function(x, y, op) {
    x <- 
      if (op == '*') x * y else if (op == '+') x + y else paste0(x, y, collapse = '')
    as.numeric(x)
  }
  
  mat2 <- mat[totals == 0,] 
  p <- progressr::progressor(steps = nrow(mat2))
  mat2 |>
    nrow() |>
    seq_len() |>
    furrr::future_map_dbl(\(rr) {
      p()
      rr <- mat2[rr,]
      target <- rr[1]; rr <- rr[-1]; rr <- rr[!is.na(rr)];
      grid <- 
        expand.grid(rlang::inject(rep(list(c('*', '+', '|')), length(rr) - 1))) |>
        dplyr::filter(dplyr::if_any(tidyselect::everything(), \(x) x == '|'))
      for (g in seq_len(nrow(grid))) {
        ops <- grid[g,] |> unlist() |> as.character()
        r <- rr; i <- 1;
        repeat {
          if (r[1] > target || i > length(ops)) break
          x <- do_op(r[1], r[2], ops[i])
          r <- c(x, utils::tail(r, -2))
          i <- i + 1
        }
        if (isTRUE(r == target)) return(r)
      }
      return(0)
    }) |>
    sum(part1)
}, handlers = progressr::handler_cli())

[1] 2.716911e+14

future::plan(future::sequential())
tictoc::toc()

408.647 sec elapsed