Regrowing trees

6

1

Background

Here you have another work-inspired challenge, but from my wife's work in this case. Imagine you have a service that returns the list of nodes in a tree structure (much like the files and folders in a file system), but in no particular order. For every node you get a tuple with its name and the name of its parent.

So if you get [["C","B"],["D","C"],["A",""],["B","A"]] (format: [NodeName,ParentName]), you could rebuild the tree structure and get a leaf with the path /A/B/C/D (A has no parent, then it is at the top level, then B is a child of A, C is a child of B and D is a child of C).

You could also get [["C","B"],["D","C"],["A",""],["B","A"],["E","B"]], so the rebuilt tree would contain two leaves: one with the path /A/B/C/D (the same as in the previous example) and a new one with the path /A/B/E as the node E has B as its parent. Note that the nodes in the list are not duplicated (the leaves D and E have parts of their paths coincident but the common parts do not appear twice in the original list of nodes).

Challenge

Given a list of nodes as described above, rebuild the tree and output the paths for all the leaves in the tree structure, in no particular order as long as you return them all.

Rules

  • The input will be a list of tuples with two elements each: the name of the current node and the name of its parent. If you don't like strings you can use arrays of chars. You can choose the order of the elements in the tuple (the node name first or the parent name first).
  • The output format can be: a list of paths as strings like ["/A/B/C/D","/A/B/E"] for the second example; a list of path nodes for each leaf, as in [["A","B","C","D"],["A","B","E"]] for the same example; or even a dictionary (something like ["A":["B":["E":[],"C":["D":[]]]]]). Or you can just print the list of paths to STDOUT.
  • There won't be nodes without a parent given explicitly.
  • The node names will be strings of alphanumeric ASCII characters [a-zA-Z0-9] of any length. So you can use any other printable ASCII character as separator if you decide to print or return the paths as strings.
  • There won't be duplicated tuples in the list.
  • There won't be cyclic paths in the list of nodes.
  • The node names are unique and case sensitive. Nodes aa and AA are not the same node.
  • If you get an empty list of nodes, return an empty list/dictionary of leaves (or just print nothing).

Test cases

In:  [["C","B"],["D","C"],["A",""],["B","A"],["E","B"]]
Out: /A/B/C/D
     /A/B/E
Alt: [["A","B","C","D"],["A","B","E"]]
Alt: ["A":["B":["E":[],"C":["D":[]]]]]

In:  [["D3","D8"],["D5","d1"],["s2","S1"],["S1",""],["d1",""],["D8","D5"],["F4","s2"],["F7","S1"],["e3","D5"]]
Out: /d1/D5/D8/D3
     /d1/D5/e3
     /S1/s2/F4
     /S1/F7
Alt: [["d1","D5","D8","D3"],["d1","D5","e3"],["S1","s2","F4"],["S1","F7"]]
Alt: ["d1":["D5":["e3":[],"D8":["D3":[]]]],"S1":["F7":[],"s2":["F4":[]]]]

In:  [["Top",""]]
Out: /Top
Alt: [["Top"]]
Alt: ["Top":[]]

In:  []
Out: 
Alt: []
Alt: []

This is , so may the shortest code for each language win!


This comes from the sandbox (for those who can see deleted posts).

Charlie

Posted 2018-01-19T11:45:02.337

Reputation: 11 448

"The output format depends on you, as long as the paths for each leaf can be reconstructed" - doesn't that apply to the input and therefore allow a no-op? – Jonathan Allan – 2018-01-19T12:46:53.067

@JonathanAllan The input will be a list of tuples with two elements each: the name of the current node and the name of its parent. no, I don't think so (btw I actually feel like this challenge is a no-op in general, but I'm not sure) – Erik the Outgolfer – 2018-01-19T12:48:02.167

@EriktheOutgolfer the task is to "output the paths for all the leaves in the tree structure", which I think is the same as "reconstructing the paths for each leaf". – Jonathan Allan – 2018-01-19T12:49:30.300

@JonathanAllan in fact, I think you're right, I didn't think of that. I'll try to change that sentence. UPDATE: I have limited the output formats, fortunately the current existing answer uses the dictionary option. – Charlie – 2018-01-19T12:50:20.573

Can I take an n x 2 where each row is a pair? – Giuseppe – 2018-01-19T15:03:30.993

@Giuseppe yes, you can. – Charlie – 2018-01-19T15:04:18.263

Can I take the input as a dictionary from child to parent? – None – 2018-01-19T16:18:46.707

@Mnemonic mmm no, no dictionaries on input, sorry. – Charlie – 2018-01-19T16:32:43.260

Is invalid input handling considered? e.g. [["C","B"],["C","A"],["A",""],["B","A"]] (making C a child of both B and A) or [["C","B"],["A","C"],["B","A"]] (making a cyclic). – Draco18s no longer trusts SE – 2018-01-19T23:42:26.250

@Draco18s no, you don't have to worry about those cases. – Charlie – 2018-01-20T07:37:47.727

Answers

4

Haskell, 53 bytes

(""#)
e[]=[[]]
e a=a
p#l=[s:c|(q,s)<-l,p==q,c<-e$s#l]

Try it online!

Takes input as a pair (parent,child) because I find that order easier to read. Output is the "list of lists of strings" style.

The # operator takes a parent name on the left and the list of nodes on the right. First it iterates through the nodes that have that parent. Then it recurs, looking for that node's children and prepending the node to the list. If it has no children e will put in an empty list to terminate the sublist (otherwise nothing would ever get added to the output).

This code assumes that node names are unique which I thought must be the case because if there were two nodes like /foo/bar/baz and /bar/baz it would be impossible to tell where to put "baz".

user1472751

Posted 2018-01-19T11:45:02.337

Reputation: 1 511

1You're right, node names are unique, I'll add that to the question. Nice answer! – Charlie – 2018-01-19T15:03:28.707

2

JavaScript (ES6), 59 bytes

a=>a.map(([c,p])=>g(p)[c]=g(c),g=s=>g[s]||(g[s]={}))&&g['']

Returns undefined if there are no top-level nodes. (+4 bytes to return an empty dictionary.)

Neil

Posted 2018-01-19T11:45:02.337

Reputation: 95 035

2

Pyth, 21 bytes

J.dQVf!}T_JJNWN=N@JNN

If we could take a dictionary, we could drop the first 4 bytes and replace the Js with Qs.
Try it online

Explanation

J.dQVf!}T_JJNWN=N@JNN
J.dQ                    Convert the input to a dictionary and call it J.
     f!}T_JJ            Find the leaves (the keys of J that aren't values).
    V       N           For each leaf, print the label...
             WN=N@JNN   ... and climb the tree, printing along the way.

user48543

Posted 2018-01-19T11:45:02.337

Reputation:

1

Ruby 87 75 bytes

->d{k=d.flatten;k.map{|i|k.count(v=i)<2&&loop{v=(d.assoc(p v)||break)[1]}}}

inspired by this answer

Try it online!

Asone Tuhid

Posted 2018-01-19T11:45:02.337

Reputation: 1 944