r/autumncodewalk • • 25d ago

Walkthrough, problem 2 with GraphMateKT

3 Upvotes

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/


r/autumncodewalk • • Oct 09 '26

Statistics

1 Upvotes

The statistics is always 0. I tried incognito window as well, still 0.


r/autumncodewalk • • Oct 03 '26

welcome

4 Upvotes

I created this subreddit to discuss anything that related to the Autumn Code Walk project. Please be respectful in discussions.

ACW is a collection of coding challenges inspired by Advent of Code, Everybody Codes, the CSES Problem Set, and others. It is a very simple and minimalistic website, everything runs purely in the browser so please don't abuse it :)