-
How to walkthrough a tree and calculate value on path?
Hi there,
Input:
tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:(1;2;3;4;5;6;7));
How to get output as in this chart?
Thank you.
-
6 Replies
-
This gets it done while remaining somewhat readable:
child:select (child,'data) by parent from tree; res:(); a:([]start:key[child];end:key[child];val:1); while[count a; res,:select from a where not end in key child; b:ungroup update nxt:child end from (delete from a where not end in key child); a:select start, end:nxt[;0], val*nxt[;1] from b; ];
The answer is given by
q)`start`end xasc res start end val ------------- A C 2 A D 3 A F 5 A G 24 A H 28 B F 5 B G 24 B H 28 E G 6 E H 7
-
Try to traverse through Dictionary
tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:(1;2;3;4;5;6;7)); tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:(1;2;3;4;5;6;7)); traverse_dict:exec child!parent from tree; calc:`A`D`C`B`F`E`G`H!1 3 2 1 5 4 6 7; traverse_func:{[st;end;dict;calc] prd calc except[(dict) end;(dict) st] }[;;traverse_dict;calc]; outputTree:([] parent:`A`A`A`A`A`B`B`B`E`E;child:`C`D`F`G`H`F`G`H`G`H); // output update val:traverse_func'[parent;child] from outputTree -
Another method:
tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:1 2 3 4 5 6 7); dl:-1_ s:{x iasc 2#/:x} // sort lr:{flip dl(x)y} // leaf to root lar:{(sum[n]-2)dlx where n:not null x} // leaf to all roots gw:{((last;first)@:y),prd x dl flip 1 nexty} // get weights walk:{ d:exec child!parent from x; w:exec(child,'parent)!data from x; s gw[w;]each raze lar each lr[d;](except/)x`child`parent } walk tree `A `C 2 `A `D 3 `A `F 5 `A `G 24 `A `H 28 `B `F 5 `B `G 24 `B `H 28 `E `G 6 `E `H 7 -
Really like this solution, haven’t seen a scan indexing before. Just wanted to add to it so the user doesn’t have to define calc and outputTree:
tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:(1;2;3;4;5;6;7)); traverse_dict:exec child!parent from tree; root:`A; // value pairing appending root node with 1 factor calc:(root, exec child from tree)!1,exec data from tree; // calc:`A`D`C`B`F`E`G`H!1 3 2 1 5 4 6 7; traverse_func:{[st;end;dict;calc] prd calc except[(dict) end;(dict) st] }[;;traverse_dict;calc]; outputTree:exec child by parent from tree; outputTree:key[outputTree]!raze each (value outputTree),' outputTree value outputTree; outputTree:(key outputTree)!except[;key outputTree]each distinct each (raze/) each (outputTree)each value outputTree; p:raze (count each value outputTree)#'key[outputTree]; c:raze value outputTree; outputTree:([] parent:p;child:c); // outputTree:([] parent:`A`A`A`A`A`B`B`B`E`E;child:`C`D`F`G`H`F`G`H`G`H); // output update val:traverse_func'[parent;child] from outputTreeThere’s probably a more concise way to do the above so keen to see any further improvements.
-
This is my solution
tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:1 2 3 4 5 6 7); getVal:{?[`tree;((=;`parent;enlist x);(=;`child;enlist y));();`data]} checkParent:{first ?[`tree;enlist (=;`child;enlist x);();`parent]} getPathVal:{[x;y] $[x~checkParent[y];getVal[x;y];getVal[checkParent[y];y]*.z.s[x;checkParent[y]]]} -
It’s faster to keep track of the running products at each step:
tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:1 2 3 4 5 6 7); sort:{x iasc 2#/:x:x@'(-1+count each x),:1 0} step:{.[z;(::;0);*;]y -2#/:z:(z,'x l)where(l:last each z)in key x} walk2:{ d:exec child!parent from x; w:exec(child,'parent)!data from x; sort raze 1_(step[d;w;])1,'(except/)x`child`parent } walk2 tree `A `C 2 `A `D 3 `A `F 5 `A `G 24 `A `H 28 `B `F 5 `B `G 24 `B `H 28 `E `G 6 `E `H 7 q)\ts do[50000;walk tree] 1930 3584j
q)\ts do[50000;walk2 tree] 1259 3440j
Log in to reply.