Day 5: Print Queue

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

Read in the problem:

dat <- read_lines("aoc05.txt")

Split into the rules and pages:

split_i <- which(dat == "")
rules_raw <- dat[1:(split_i - 1)]
pages_raw <- dat[(split_i + 1):length(dat)]

Take a look:

head(rules_raw)

[1] "48|17" "38|73" "38|78" "72|63" "72|95" "72|54"

head(pages_raw)

[1] "51,78,33,39,97,44,45,69,83,84,13,42,56,57,61,68,99,81,82,21,72,63,64"
[2] "78,34,43,71,33,77,93,22,17,74,73,75,97"                              
[3] "99,98,27,57,84,61,39,51,24,81,33"                                    
[4] "96,98,51,27,97,13,42"                                                
[5] "99,81,82,72,63,89,12,14,38,75,29,43,28,34,73,96,17"                  
[6] "96,71,54,93,98,24,22,78,27,33,97,69,83,84,13,42,56"                  

Make a nice dataframe of rules:

rules <- rules_raw |>
  str_split_fixed("\\|", 2) |>
  as.data.frame() |>
  rename(first = V1, second = V2)
head(rules)

Make a nice list of pages:

pages <- strsplit(pages_raw, ",")
head(pages)

[[1]]
 [1] "51" "78" "33" "39" "97" "44" "45" "69" "83" "84" "13" "42" "56"
[14] "57" "61" "68" "99" "81" "82" "21" "72" "63" "64"

[[2]]
 [1] "78" "34" "43" "71" "33" "77" "93" "22" "17" "74" "73" "75" "97"

[[3]]
 [1] "99" "98" "27" "57" "84" "61" "39" "51" "24" "81" "33"

[[4]]
[1] "96" "98" "51" "27" "97" "13" "42"

[[5]]
 [1] "99" "81" "82" "72" "63" "89" "12" "14" "38" "75" "29" "43" "28"
[14] "34" "73" "96" "17"

[[6]]
 [1] "96" "71" "54" "93" "98" "24" "22" "78" "27" "33" "97" "69" "83"
[14] "84" "13" "42" "56"

Part 1

Test one rule on one vector of pages:

test_rule <- function(first, second, pages) {
  first_i  <- which(pages == first)
  second_i <- which(pages == second)
  
  !is.unsorted(c(first_i, second_i))
}

Test all the rules on one vector of pages:

test_all_rules <- function(page_vec) {
  map2_lgl(rules$first, rules$second,
           \(f, s) test_rule(f, s, page_vec)) |>
    all()
}

Test all the rules on all the pages:

test_all_pages <- function(pages_list) {
  map_lgl(pages_list, test_all_rules)
}

tic()
res <- test_all_pages(pages)
toc()

1.28 sec elapsed

Look up the print runs that satisfy the rules:

sorted_pages <- pages[res]

Sum the middle pages:

mid_val <- function(vec) {
  middle <- (1 + length(vec)) / 2
  vec[middle] |> as.numeric()
}

map_int(sorted_pages, mid_val) |> sum()

[1] 7024

Part 2

Get the unordered pages:

broken <- pages[!res]
head(broken)

[[1]]
 [1] "78" "34" "43" "71" "33" "77" "93" "22" "17" "74" "73" "75" "97"

[[2]]
 [1] "99" "98" "27" "57" "84" "61" "39" "51" "24" "81" "33"

[[3]]
[1] "13" "56" "33" "78" "96" "44" "94"

[[4]]
 [1] "28" "98" "39" "51" "83" "78" "97" "24" "54" "93" "69" "94" "73"
[14] "71" "27" "34" "74"

[[5]]
 [1] "82" "72" "61" "69" "38" "64" "63" "45" "42" "83" "48" "85" "99"
[14] "13" "89"

[[6]]
 [1] "57" "72" "81" "21" "27" "97" "13" "84" "78" "68" "85" "63" "83"
[14] "61" "45"

The following section is brought to you by thinking, “Surely there’s a graph algorithm for this”, and also some wishful thinking about the completeness of the rules (prompted by the existence of a unique middle page).

library(igraph)

sort_pages <- function(vec) {
  rules |>
    filter(first %in% vec & second %in% vec) |>
    as.matrix() |>
    graph_from_edgelist() |>
    topo_sort() |>
    names()
}

tic()
broken |>
  map(sort_pages) |>
  map_int(mid_val) |>
  sum()

[1] 4151

toc()

0.14 sec elapsed