Created
December 11, 2025 15:38
-
-
Save tomjemmett/fc2dc7e1bf5698fb343c0e4642f2f27a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| library(igraph) | |
| library(ggraph) | |
| input <- readr::read_lines("inputs/actual/11.txt") | |
| parse_line <- function(line) { | |
| x <- stringr::str_split(line, ": ")[[1]] | |
| node <- x[[1]] | |
| edges <- stringr::str_split(x[[2]], " ")[[1]] |> | |
| stringr::str_trim() | |
| list( | |
| from = replicate(length(edges), node), | |
| to = edges | |
| ) | |
| } | |
| edge_list <- purrr::map(input, parse_line) |> | |
| dplyr::bind_rows() | |
| g <- igraph::graph_from_data_frame(edge_list) | |
| ggraph(g) + | |
| ggraph::geom_edge_link() + | |
| ggraph::geom_node_point() + | |
| ggraph::geom_node_label(aes(label = name)) | |
| p1 <- induced_subgraph( | |
| g, | |
| intersect( | |
| subcomponent(g, "you", mode = "out"), | |
| subcomponent(g, "out", mode = "in") | |
| ) | |
| ) | |
| p1 |> | |
| ggraph() + | |
| ggraph::geom_edge_link() + | |
| ggraph::geom_node_label(aes(label = name)) | |
| length(all_simple_paths(g, "you", "out", mode = "out")) | |
| p2_a <- induced_subgraph( | |
| g, | |
| intersect( | |
| subcomponent(g, "svr", mode = "out"), | |
| subcomponent(g, "fft", mode = "in") | |
| ) | |
| ) | |
| p2_b <- induced_subgraph( | |
| g, | |
| intersect( | |
| subcomponent(g, "fft", mode = "out"), | |
| subcomponent(g, "dac", mode = "in") | |
| ) | |
| ) | |
| p2_c <- induced_subgraph( | |
| g, | |
| intersect( | |
| subcomponent(g, "dac", mode = "out"), | |
| subcomponent(g, "out", mode = "in") | |
| ) | |
| ) | |
| # from this plot, identify some nodes that bisect the graph such that: | |
| # * you reach the node from fft | |
| # * you reach dac from the node | |
| # * you can't reach any of the other selected nodes from this node | |
| # that is, if you collapsed all of the edges between these nodes and fft/dac, you would have a bipartite graph | |
| p2_b |> | |
| ggraph() + | |
| ggraph::geom_edge_link() + | |
| ggraph::geom_node_label(aes(label = name)) | |
| p2_res <- c( | |
| length(all_simple_paths(p2_a, "svr", "fft", mode = "out")), | |
| sum( | |
| length(all_simple_paths(p2_b, "fft", "rqt", mode = "out")) * length(all_simple_paths(p2_b, "rqt", "dac", mode = "out")), | |
| length(all_simple_paths(p2_b, "fft", "vbf", mode = "out")) * length(all_simple_paths(p2_b, "vbf", "dac", mode = "out")), | |
| length(all_simple_paths(p2_b, "fft", "mfw", mode = "out")) * length(all_simple_paths(p2_b, "mfw", "dac", mode = "out")), | |
| length(all_simple_paths(p2_b, "fft", "zal", mode = "out")) * length(all_simple_paths(p2_b, "zal", "dac", mode = "out")), | |
| length(all_simple_paths(p2_b, "fft", "xgi", mode = "out")) * length(all_simple_paths(p2_b, "xgi", "dac", mode = "out")) | |
| ), | |
| length(all_simple_paths(p2_c, "dac", "out", mode = "out")) | |
| ) | |
| prod(bit64::as.integer64(p2_res)) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment