12
\$\begingroup\$

Challenge

Your goal is to find the furthest point on a graph (from a provided start node). Your code doesn't need to handle cycles in the graph properly, but it might pose a fun challenge. For this question, you can assume the graph is actually a tree.

Input data

Input can be provided in any suitable format for the language. It can be provided either as an adjacency matrix, a list of edges, or an adjacency list. The input data can be directed or undirected as wanted by the program. The program needs to know the starting node - this can be provided in the input data if the program doesn't calculate it.

Output format

The program must output to stdout, in a human readable format, a list of nodes, starting from the root and leading to the furthest node. If you prefer, this order may be reversed. Your program must be consistent wrt to the ordering.

Edge cases

If there are multiple longest paths, only return one. If there is a cycle, or the graph has disconnected components, your code may crash or return a valid or invalid output.

Libraries

All graph related libraries, including built-in language features, are not permitted.

Test case

Input:

{0: (1, 2, 3), 1: (), 2: (4, 5), 3: (6,), 4: (7,), 5: (), 6: (8,), 7: (9,), 8: (), 9: ()}
0

The zero on the second line is the starting node. This could be inferred from the adjacency list, but I've included it in the test data anyway, to be clear.

Output:

[0, 2, 4, 7, 9]

Image:

Sample path

Scoring

Shortest code wins.

\$\endgroup\$
18
  • 4
    \$\begingroup\$ Welcome to Code Golf! This looks like a reasonably well-specified challenge, but for future reference, we strongly recommend using the Sandbox to get feedback on challenge ideas before posting them to the main site. \$\endgroup\$ – pxeger Jun 4 at 9:24
  • \$\begingroup\$ <s>Will the graph always connected? If not, should the not connected node be considered furthest?</s> oh, ignore this, I missed the keyword "tree" \$\endgroup\$ – tsh Jun 4 at 9:44
  • 2
    \$\begingroup\$ Welcome, and nice first challenge. \$\endgroup\$ – rak1507 Jun 4 at 9:44
  • \$\begingroup\$ Graph will always be connected. I've edited the question to reflect this, under Edge cases. \$\endgroup\$ – Hack5 Jun 4 at 9:44
  • 1
    \$\begingroup\$ Since the input data is always a tree, if your programs takes a directed graph as input, then the node with no parents is the start node. I don't expect you to use this, I just added it in case anyone prefers to calculate it rather than take as input. As shown in the test data, you don't have to calculate it, you can just take it as input. \$\endgroup\$ – Hack5 Jun 4 at 9:53
4
\$\begingroup\$

Coconut, 45 bytes

Takes the graph in the format shown in the example test case

f=(g,s)->[s]+max(map(f$g,g[s])::[[]],key=len)

Try it online!

Uses Coconuts lambda syntax, $ for partial application and :: as an operator for itertools.chain. The same would be 56 bytes in Python:

f=lambda g,s:[s]+max([f(g,x)for x in g[s]]+[[]],key=len)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 23 bytes

⊞υ⟦θ⟧FυF§η§ι⁰⊞υ⁺⟦κ⟧ιI⊟υ

Try it online! Link is to verbose version of code. Takes the root as the first input and an array of lists of adjacencies as the second input and outputs the longest route in reverse order. Explanation:

⊞υ⟦θ⟧

Start a breadth first search with a list of just the root node.

Fυ

Process the lists in the order they are found.

F§η§ι⁰

For each list, loop over the nodes adjacent to the first node in the list...

⊞υ⁺⟦κ⟧ι

... pushing a new list with the adjacent node at the beginning to the search.

I⊟υ

Output the last, and therefore longest, list.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 92 bytes

a=>g=(h,...t)=>v=1/h?a[h].map((n,j)=>g[j]?0:g[j]=n&&t.push(j))[g(...t)[0]]?[h,...v]:v||[h]:0

Try it online!

Input the adjacency matrix of graph and the start node currily.

This one works on graphs with cycles.


JavaScript (Node.js), 68 bytes

a=>s=>(g=(h,...t)=>v=h&&g(...t,...a[h[0]].map(j=>[j,...h]))||h)([s])

Try it online!

This one works on directed graph without cycles.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 13 12 bytes

;ⱮịṪ¥¥€Ẏ¥ƬẎṪ

Try it online!

A dyadic link taking the start node as the left argument and the list of lists of child nodes as the right argument. The start node is expected to be supplied as [[x]] where x is the number of the node. Uses 1-indexing since that’s the way Jelly is written.

Thanks to @JonathanAllan for saving a byte!

Explanation

        ¥Ƭ    | Starting with the start node index, do the following until there’s a repeated value:
     ¥€       | - For each member of the list:
;Ɱ            |   - Append each of the following:
  ịṪ¥         |     - The last member of the list indexed into the original right argument (actually done as index into then tail)
       Ẏ      | - Flatten lists by one level
          Ẏ   | Finally, join the top level lists together
           Ṫ  | Take the last remaining list (which will be one of the longest paths)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think you can replace ṖṪṪ with ẎṪ. \$\endgroup\$ – Jonathan Allan Jun 5 at 17:43
1
\$\begingroup\$

Kotlin 1.4.20, 92 bytes

fun f(e:Map<Int,Set<Int>>,s:Int):List<Int> =(e[s]?.map{f(e,it)}?.maxBy{it.size}?:setOf())+s

Usage

fun main() = println(f(mapOf(0 to setOf(1, 2, 3), 1 to setOf(), 2 to setOf(4, 5), 3 to setOf(6), 4 to setOf(7), 5 to setOf(), 6 to setOf(8), 7 to setOf(9), 8 to setOf(), 9 to setOf()), 0))

Note

This uses a deprecated API that got removed in 1.5, so it requires Kotlin 1.4 or lower.

\$\endgroup\$
1
  • \$\begingroup\$ You shouldn't be answering your own posts so quickly, give other people a chance first. \$\endgroup\$ – Noodle9 Jun 4 at 12:07
1
\$\begingroup\$

PowerShell, 114 109 104 103 96 bytes

param($s,$e)$e|%{$p=($p+,"$_"*!(($a=$_[0])-$s))-replace"\b$a$",$_}
$p|sort{(-split$_).count}-b 1

Try it online!

Stores paths as an array of strings. Each path contains a list of vertices separated by spaces.


Less golfed:

param($startVertex,$edges)
$edges|%{
    $fromVertex = $_[0]
    $pathes += ,"$_"*($fromVertex -eq $startVertex) # add $null or an edge
    $pathes = $pathes -replace "\b$fromVertex$",$_
}
$pathes|sort{(-split$_).count} -Bottom 1

The dump of $pathes before sorting for the test case:

"0 1"
"0 2 4 7 9"
"0 3 6 8"
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 47 bytes

Pick[#,#,#&@@#~Level~{Depth@#-1}]//._[]:>Set@$&

Try it online!

Input an expression - Mathematica's expressions are trees. For example: TreeForm of 0[1, 2[4[7[9]], 5], 3[6[8]]]

Pick almost does the job, but non-leaf nodes with successors still remain. Then we remove all empty nodes.

Also 47 bytes

Select@Not@*FreeQ[#&@@#~Level~{Depth@#-2}]//@#&

Try it online!

Input leaves as e.g. 9[] instead of 9.

\$\endgroup\$
0
\$\begingroup\$

Red, 95 bytes

f: function[x s][m: []foreach i select x s[p: f x i if(length? p)> length? m[m: p]]rejoin[m s]]

Try it online!

Takes input as an adjacency list plus the starting node in the same form as in challenge specification. Returns the longest path in reverse order.

\$\endgroup\$
0
\$\begingroup\$

R, 89 bytes

R=function(G,p={})`if`(!is.list(G),p,(A=lapply(G,R,c(p,el(G))))[[which.max(lengths(A))]])

Try it online!

Recursive function taking a tree as input (for the input format see the TIO) and returning the subtree of maximum length.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.