How to walkthrough a tree and calculate value on path?

Community Support
,
1

https://learninghub.kx.com/forums/topic/how-to-walkthrough-a-tree-and-calculate-value-on-path

Hi there,

Input:

tree:(parent:AAABBEE;child:BCDEFGH;data:(1;2;3;4;5;6;7));

How to get output as in this chart?

Thank you.

 

 

2

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
3

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
4

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 outputTree

There’s probably a more concise way to do the above so keen to see any further improvements.

5

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

 

6

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]]]}

 

7

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