Day 7: Bridge Repair

library(tidyverse)
library(stringr)
library(tictoc)
library(gmp)

dat <- read_lines("aoc07.txt")

head(dat)

[1] "5784641: 453 6 9 3 8 25 14 356 1"  
[2] "282716070: 373 831 714 455 2"      
[3] "38474572: 1 3 8 4 45 1 248 1 466 2"
[4] "32688: 90 356 3 640 5"             
[5] "2462846: 245 64 23 41 48"          
[6] "10791: 2 4 4 896 39"               

splitcolon <- strsplit(dat, ": ")
out <- splitcolon |> map(\(x) x[1] |> as.bigz())
inp <- splitcolon |> map(\(x) x[2] |>
                                strsplit(, split = " ") |>
                                pluck(1) |>
                                as.bigz()
                        )

The inputs:

head(inp, 2)

[[1]]
Big Integer ('bigz') object of length 9:
[1] 453 6   9   3   8   25  14  356 1  

[[2]]
Big Integer ('bigz') object of length 5:
[1] 373 831 714 455 2  

The target values:

head(out, 2)

[[1]]
Big Integer ('bigz') :
[1] 5784641

[[2]]
Big Integer ('bigz') :
[1] 282716070

Part 1

Get all combos of operators:

combs_ops <- function(num_n) {
  replicate(num_n - 1, c("plus", "mult"), simplify = FALSE) |>
    expand.grid(stringsAsFactors = FALSE,
                KEEP.OUT.ATTRS = FALSE)
}

Do one sum:

calc <- function(nums, ops, target) {
  res <- nums[1]
  
  for (i in 2:length(nums)) {
    the_op <- ops[i - 1] |> as.vector()
    stopifnot(the_op %in% c("plus", "mult"))
    if (the_op == "plus") {
      res <- res + nums[i]
    }
    else {
      res <- res * nums[i]
    }
  }
  
  res == target
}

Check them all for one list of inputs and a target:

check_all <- function(nums, target) {
  all_ops <- combs_ops(length(nums))
  found_it <- FALSE
  
  for (r in 1:nrow(all_ops)) {
    this_ops <- all_ops[r,] |> as.vector()
    found_it <- calc(nums, this_ops, target)
    if (found_it)
      break
  }
  
  found_it
}

Now do it for everything. I wonder will map work okay with {gmp}…

tic()
res <- map2_lgl(inp, out, check_all)
toc()

51.7 sec elapsed

It did. Not taking any chances with the final sum…

to_sum <- out[res]
the_sum <- to_sum[[1]]
for (i in 2:length(to_sum))
  the_sum <- the_sum + to_sum[[i]]
the_sum

Big Integer ('bigz') :
[1] 2437272016585

Part 2

concat <- function(x, y) {
  paste0(as.character(x), as.character(y)) |> as.bigz()
}

combs_ops_v2 <- function(num_n) {
  replicate(num_n - 1, c("plus", "mult", "concat"), simplify = FALSE) |>
    expand.grid(stringsAsFactors = FALSE,
                KEEP.OUT.ATTRS = FALSE)
}

Well, this is going to blow up spectacularly…

calc_v2<- function(nums, ops, target) {
  res <- nums[1]
  
  for (i in 2:length(nums)) {
    the_op <- ops[i - 1] |> as.vector()
    stopifnot(the_op %in% c("plus", "mult", "concat"))
    if (the_op == "plus") {
      res <- res + nums[i]
    }
    else if (the_op == "mult") {
      res <- res * nums[i]
    }
    else {
      res <- concat(res, nums[i])
    }
  }
  
  res == target
}

check_all_v2 <- function(nums, target) {
  all_ops <- combs_ops_v2(length(nums))
  found_it <- FALSE
  
  for (r in 1:nrow(all_ops)) {
    this_ops <- all_ops[r,] |> as.vector()
    found_it <- calc_v2(nums, this_ops, target)
    if (found_it)
      break
  }
  
  found_it
}

tic()
res_v2 <- map2_lgl(inp, out, check_all_v2)
toc()

4400.59 sec elapsed

to_sum <- out[res_v2]
the_sum <- to_sum[[1]]
for (i in 2:length(to_sum))
  the_sum <- the_sum + to_sum[[i]]
the_sum

Big Integer ('bigz') :
[1] 162987117690649