How to walkthrough a tree and calculate value on path?

[James1]

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.

[megan_mcp]

Thanks for posting ! Looking forward to seeing what the community's approach to this is.

[gyorokpeter-kx]

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

[sujoy]

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

[sbruce01]

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.

[creid]

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

[cillianreilly · Accepted solution]

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)dl\x where n:not null x}          // leaf to all roots
gw:{((last;first)@\:y),prd x dl flip 1 next\y}   // 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

[cillianreilly]

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