Its purpose is to find the longest path in an equally-weighted tree denoted as such:
3
1 2
2 3
The first number denotes both the number of vertices and the number of edges (3 - 1).
(defn farthest [edg current-node entry-node len]
(let [
farthest-key (atom current-node)
farthest-val (atom len)
]
(do
(dorun
(map
(fn [n]
; check if theres a way to this node and that we're not going back
(if (not= n entry-node)
(let [new (farthest edg n current-node (+ len 1))
new-val (second new)
new-key (first new)]
(if (> new-val @farthest-val)
(do
(reset! farthest-val new-val)
(reset! farthest-key new-key)
)
)
)
)
)
(aget edg current-node)
)
)
[@farthest-key @farthest-val]
)
)
)
(defn main []
(let [edge-count (read)
edges (atom
(to-array
(repeat edge-count [])
)
)]
(dotimes [n (- edge-count 1)]
(let [edge-a (- (read) 1)
edge-b (- (read) 1)]
(aset @edges edge-a
(conj (aget @edges edge-a) edge-b)
)
(aset @edges edge-b
(conj (aget @edges edge-b) edge-a)
)
)
)
(let [
ft (farthest @edges 0 0 0)
ftv (first ft)
sol (farthest @edges ftv ftv 0)
]
(println (second sol))
)
)
)
(main)
I've taken multiple attempts to optimize it, but I'm still struggling to make it run under the allowed time (1 second for a tree of up to 10000 vertices/connections). The most notable improvement was a change of the data structure from a connection matrix to a bunch of neighbourhood lists.
It is a university assignment, but I'm perfectly fine with disclosing that I got help here. I feel that I've already given it everything that I can and it simply requires more intricate knowledge about Clojure and its performance in particular, rather than a purely algorithmic change. (I know for a fact that one my colleagues managed to fit in the allocated time using the same algorithm on the same grading system).