library(stringr)
library(dplyr)
input <- readLines("input16.txt")
input <- unlist(str_split(paste0(input, collapse = "\n"), "\n\n"))

params <- str_match(unlist(str_split(input[1], "\n")), "^([a-z ]+): (\\d+)-(\\d+) or (\\d+)-(\\d+)$")
params <- as.data.frame(params, stringsAsFactors = FALSE)
names(params) <- c("Orig", "Param", "Min1", "Max1", "Min2", "Max2")
params <- mutate(params,
                Min1 = as.numeric(Min1),
                Max1 = as.numeric(Max1),
                Min2 = as.numeric(Min2),
                Max2 = as.numeric(Max2)
                )

bound1 <- params %>% select(Min1:Max1) %>% as.matrix()
bound2 <- params %>% select(Min2:Max2) %>% as.matrix()
bounds <- rbind(bound1, bound2)
boundsb <- cbind(bound1, bound2)


myticket <- as.numeric(unlist(str_split(str_split(input[2], "\n")[[1]][2], ",")))

alltickets <- do.call(rbind, str_split(unlist(str_split(input[3],"\n"))[-1], "," ))
alltickets <- matrix(as.numeric(alltickets), nrow = nrow(alltickets))

posvalid <- apply(alltickets, c(1, 2), function(x) {
                      any(apply(bounds, 1, function(b) {
                                    (x >= b[1]) && (x <= b[2])
    }))
                })


sum(alltickets[!posvalid])

tvalid <- apply(posvalid, 1, min) != 0

vtickets <- alltickets[tvalid,]


possmatrix <- apply(boundsb, 1, function(b) {
          vmatrix <- apply(vtickets, c(1, 2), function(x) {
                               ((x >= b[1]) && (x <= b[2])) || ((x >= b[3]) && (x <= b[4]))
})
          apply(vmatrix, 2, all)
                })

potnums <- apply(possmatrix, 1, sum)
potorder <- order(potnums)
colindex <- numeric(0)

matordered <- possmatrix[potorder,]

apply(matordered, 1, function(r) {
          cb <- which(r)
          cb <- cb[!(cb %in% colindex)]
          colindex <<- c(colindex, cb)
          cb
                })

depcols <- colindex[grepl("^departure ", params$Param[potorder])]

print(prod(myticket[depcols]), digits = 15)

params$Param[potorder]
2529157555213

cbind(params$Param[potorder], colindex)