X
Xah Lee
Programing Challenge: Constructing a Tree Given Its Edges.
Show you are the boss.
http://xahlee.info/perl-python/python_construct_tree_from_edge.html
here's plain text.
────────── ────────── ────────── ────────── ──────────
Problem: given a list of edges of a tree: [child, parent], construct the tree. Here's a sample input: [[0, 2], [3, 0], [1, 4], [2, 4]].
Here's a sample print of a tree data structure:
4
1
2
0
3
this means, the root node's name is 4. It has 2 branches, named 1 and 2. The branche named 2 has 1 children, named 0, and it has one children named 3.The node's names are given as integers, but you can assume them to be strings.
You can choose your own data structure for the output. For example, nested list with 1st element being the node name, or use nested hash of hash, where key is the node name, and value is its children.
Here's sample data structure in python, using hash of hash.
{
"4": {
"1": {},
"2": {
"0": {
"3": {}
}
}
}
}
Other data structure are accepted.
Code it using your favorite language. I'll be able to look at and verify inMathematica, Python, Ruby, Perl, PHP, JavaScript, Emacs Lisp, Java. But other langs, such as Clojure and other lisps, OCaml, Haskell, erlang, Fortress, APL, HOL, Coq, Lua, Factor, Rust, Julia … are very welcome. 〔☛ Proliferation of Computing Languages〕
You should be able to do this within 8 hours from scratch. Took me 5 hours.
Python solution will be posted in a week, on 2014-01-14 (or sooner if many showed solutions). Post your solution in comment (or link to github or pastebin).
Show you are the boss.
http://xahlee.info/perl-python/python_construct_tree_from_edge.html
here's plain text.
────────── ────────── ────────── ────────── ──────────
Problem: given a list of edges of a tree: [child, parent], construct the tree. Here's a sample input: [[0, 2], [3, 0], [1, 4], [2, 4]].
Here's a sample print of a tree data structure:
4
1
2
0
3
this means, the root node's name is 4. It has 2 branches, named 1 and 2. The branche named 2 has 1 children, named 0, and it has one children named 3.The node's names are given as integers, but you can assume them to be strings.
You can choose your own data structure for the output. For example, nested list with 1st element being the node name, or use nested hash of hash, where key is the node name, and value is its children.
Here's sample data structure in python, using hash of hash.
{
"4": {
"1": {},
"2": {
"0": {
"3": {}
}
}
}
}
Other data structure are accepted.
Code it using your favorite language. I'll be able to look at and verify inMathematica, Python, Ruby, Perl, PHP, JavaScript, Emacs Lisp, Java. But other langs, such as Clojure and other lisps, OCaml, Haskell, erlang, Fortress, APL, HOL, Coq, Lua, Factor, Rust, Julia … are very welcome. 〔☛ Proliferation of Computing Languages〕
You should be able to do this within 8 hours from scratch. Took me 5 hours.
Python solution will be posted in a week, on 2014-01-14 (or sooner if many showed solutions). Post your solution in comment (or link to github or pastebin).