Advent of Code 2023 - Day 25Snowverload

R | Problem statement | Source code | Tags: Graph theoryManual inspection

I think this is an easy cheat. Since I already use igraph, I can directly find the min-cut, i.e., the smallest set of edges that disconnects the graph.

parts <- strsplit(data, ": ")
nodes <- sapply(parts, function(x) x[1])
targets <- lapply(parts, function(x) strsplit(x[2], " ")[[1]])
nodes <- unique(c(nodes, unlist(targets)))
graph <- igraph::make_empty_graph(n = length(nodes), directed = FALSE)
for (i in seq_along(targets)) {
  graph <- igraph::add_edges(
    graph,
    unlist(sapply(targets[[i]], function(x) c(i, match(x, nodes))))
  )
}
igraph::V(graph)$label <- nodes
min_cut <- igraph::min_cut(graph, value.only = FALSE)
stopifnot(min_cut$value == 3)
cat(length(min_cut$partition1) * length(min_cut$partition2), "\n")
R

Of course one could just implement the min-cut algorithm by hand, but why bother??

Alternative you can export the graph and look at it directly:

Graph visualization