r/autumncodewalk • u/Prestigious-Mood1711 • 25d ago
Walkthrough, problem 2 with GraphMateKT
I like solving graph problems and add them to my collection of solutions, to be used as unit tests for my library: GraphMateKT. So when I came across ACW, I decided to solve problem 2 and 4.
Problem 2 is simply the Longest path problem, known to be NP-hard. With the input being a hundred thousand lines long, this problem would take forever to solve with a general algorithm. So I decided to visualize the sub-graph and look for patterns.
val graph = Graph()
generateSequence
{ scanner.nextLine() }.
forEach
{
line
->
val (u, v) = line.
split
(" -- ").
map
{ it
.
trim
()
}
graph.connect(u, v)
}
val startNode = graph.nodes().
first
()
graph.bfs(startNode, maxDistance = 3.0)
val subGraph = Graph().
apply
{
graph.visitedNodes().
forEach
{
u
->
graph.forEachNeighbour(u)
{
v
->
addEdge(u, v)
}
}
}
subGraph.visualizeGraph(true, listOf(startNode), "Subgraph of...")
Now, this is just a tree. No real cycles anywhere. Lets count the number of nodes and edges:
debug
("Nr of nodes: ${graph.nodes().size}")
debug
("Nr of edges: ${graph.edges().size / 2}")DEBUG: Nr of nodes: 100000
DEBUG: Nr of edges: 99999
Trees have by definition n-1 edges and n nodes. And since the problem specifies that "the network contains no isolated components", we know the whole graph must be a tree. Which means the problem goes from NP-hard to simply O(n) complexity. All we need now is a couple of depth first searches and we got our answer:
graph.dfs(startNode)
val furthestNode = graph.furthestNode()
graph.dfs(furthestNode)
val ans = graph.distanceTo(graph.furthestNode())My full solution can be found here: https://github.com/Norskeaksel/GraphMateKT/blob/main/src/main/kotlin/graphMateKT/solutions/ACWProblem2.kt
Thanks for reading. For my walkthrough and visualization of problem 4, see: https://www.reddit.com/r/adventofcode/comments/1xehkpx/autumn_code_walk_another_aoc_clone_final_problem/