spreadsheets.google.com
Array.prototype.contains = function(obj) {
// copied from http://stackoverflow.com/questions/237104/javascript-array-containsobj
var i = this.length;
while (i--) {
if (this[i] === obj) {
return true;
}
}
return false;
}
function doTree (node, func) {
var seen = [];
var to_see = [node];
while to_see.length {
var next_node = to_see.pop();
func(next_node.value);
seen.push(next_node);
for (var i; i < next_node.children.length; i++) {
var child = next_node.children[i];
if (! seen.contains(child) && ! to_see.contains(child)) {
to_see.push(child);
}
}
}
}
// --
var num_arr = [];
var sum = 0;
doTree(numTree, function (val) { num_arr.push(val); })
// googled for a sum function. didn't know if javascript had map or reduce in stdlib.
for (var i; num_arr.length; i++) {
sum += num_arr[i];
}
// sum is sum.5-10 min.
// --
its kind of a pain to do in a text box. variable width fonts make it harder to read. Would have also been nice to have an actual javascript repl. Was a bit shaky on tree traversal, but I think that's correct. Also not intimately familiar with javascript stdlib.
Chrome has it built in and Firefox has Firebug.
Was a bit shaky on tree traversal, but I think that's correct.
It's much simpler with recursion. Your contains method is "correct" but doesn't work in this case because objects with the same keys and values still aren't necessarily equal.
var doTree = function doTree(node, fn) {
for (var i = 0; i < node.children.length; i++) {
doTree(node.children[i]);
}
fn(node.value);
}
var treeSum = 0;
doTree(numTree, function(nodeValue) {
treeSum += nodeValue;
});
doTree(numTree, addNodeToSum) function mapTree(tree, fun) {
// apply function to tree.value, then recurse (needs javascript.map)
if (typeof tree == 'undefined') {
return null;
}
return {
value: fun(tree.value),
children: tree.children.map(
function(tree) {
return mapTree(tree, fun);
})
};
}
//////////////////
var numTree={value: 42,
children: [
{value: 43, children: []},
{value: 44,
children: [{value: 95, children: []},
{value: 1, children: []}]}
]
};
var count=0;
mapTree(numTree, function(c) {
count+=c;
});
alert(count); // => 225- Well, I dont know JS, but in order to process a node, I have to apply the function to the value and recurse for each value in the array. This also handles leafes properly, because they have no children and thus no recursion occurs. Thus, I'd have to grab some web browser now and find some forach-loop and some functio-definition-syntax in JS now.
- In order to sum values up, I'd need some function which adds the value to an accumulator in place and destructively (such that the new value replaces the old value). Should be easy using closures or, in the worst case, a simple small object.
Overall, this took about 3 minutes. If I would search for javascript syntax now, I'd probably need around 10 - 20 additional minutes to get everything working.
Did it pass? Can you email it back to me ...
do_tree([Value | Children], Fun) ->
[Fun(Value) | [do_tree(Child, Fun) || Child <- Children]];
do_tree([], _Fun) -> [].
sum_tree(NumTree) ->
lists:foldl(fun(Elem, AccIn) -> Elem+AccIn end, 0,
lists:flatten(do_tree(NumTree, fun(Value) -> Value end))).The problem definitely says that a leaf node will have an empty array as it's children property
Besides, it's not an application, I'm sure you could write it in your favorite language of you wanted :)
function doTree(node, fn) {
fn(node.value);
for (var i = 0; i < node.children.length; ++i) {
doTree(node.children[i], fn);
}
}
var sum = 0;
doTree(numTree, function(value) { sum += value; });Can someone explain (or point to an explanation of) the scoping rules for me?
Thanks.