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 in
Mathematica, 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).
--
https://mail.python.org/mailman/listinfo/python-list
