C# recursively calculate value

Question

I have following table

I need to work out the values in columns X, Y and Z.

Rule 1: code only has children as X, Y, or Z.

Let's start from a simple one, row 12, code 'E2' has a child called 'Z' and value is 3.30, so cell [F12] (column Z) should have 3.30. We can denote as f(12)= 3.30Z, Similarly, cell [E11] should be 2.10, or f(11)=2.10Y. For row 6, cell[D6] should be 1.14, denote as f(6)=1.14X.

note, code X,Y,Z do not have children themselves. However, other children can have grand children, recursively.

Rule 2: If a code has a child, then the value will be its own value times whatever the child code value.

e.g. row 10, it has a child 'E2', so the value will be its value 3.10 times whatever the children (E2) value, i.e. f(10)=3.10*f(12)=3.10*3.30Z=10.23Z, cell[F10] should be 10.23

Rule 3, if a code has multiple children, then the value will be sum for all the children group by type, following Rule 2

e.g. row 5 C1 has a child D, and D has three children (X, E1, E2), the 3 children values needs to add together. f(5)=1.70*(f(8)+f(9)+f(10)). Of course, some children has X values, some has Y values, some has Z values, so when adding them up, they need to be grouped by value type, and then fill in the corresponding columns Cell[D5], Cell[E5], cell[F5]

Hope that makes sense.

This is a simplified version of the original more complicated question which has thousands of rows, and some other calculations. But not a huge table, so performance or speed is not priority consideration.

It is more of an algorithm issue, but I prefer to implement in C#

Answer 1

What you've described is a tree structure, which you can build easily enough, and then traverse recursively. You already know the parent/child relationships; you just have to create a model to represent them in code.

Start with an Element class that looks like this:

class Element
{
    string Code;
    Element Parent;  // null if no parent
    double Value;
    double CalculatedValue;
    List<string> Children;
}

And create a dictionary of these, keyed by code:

Dictionary<string, Element> Elements;

Go through the list, adding creating an Element for each unique element, and adding it to the dictionary:

(Note: code examples are in pseudo-C#. I don't want to get bogged down in syntax here.)

for each row
{
    Element e;

    // if the element doesn't exist in the dictionary, create and add it
    if (!Elements.TryGetValue(code, out e))
    {
        e = new Element(code, value);
        Elements.Add(code, e);
    }
    if (child != null)
    {
        e.Children.Add(child);
    }
}

You now have a dictionary of elements, with the child relationships. You need to create the parent relationships. Easiest way is with a scan of the dictionary:

for each e in Elements
    for each child in e.Children
        if (child != "X" or "Y" or "Z")
            Elements[child].Parent = e;

Now what you have is a forest: one or more unrooted trees. You can scan it recursively to compute your value:

double totalValue = 0;
for each e in Elements
    if (e.Parent == null)
    {
        totalValue += calculateElementValue(e);
    }
}
// at this point, totalValue should contain the total value

If I understood your rules correctly, this method should compute an individual element's value. I assumed that an element has only one of X, Y, or Z. This is a simple depth-first traversal of an element tree.

double CalculateElementValue(Element e)
{
    double eValue = 0;
    double childrenValue = 0;
    for each child in e.Children
    {
        switch (child)
        {
            case "X": eValue = e.Value * xValue; break;
            case "Y": eValue = e.Value * yValue; break;
            case "Z": eValue = e.Value * zValue; break;
            else
            {
                childrenValue += CalculateElementValue(Elements[child]);
            }
        }
    }
    return eValue * childrenValue;
}

You could include the parent assignment in the initial loop that builds the elements, but it complicates things a little bit. But unless the table has lots of rows, you probably won't notice a difference in speed.

Answer 2

Here are some example data structures you can use to represent your data, and recursively calculate values.

Note that this example uses indirect recursion. I.e. Node.Evaluate() does not call itself directly, but instead calls WeightedChild.Evaluate() which in turn calls back to Node.Evaluate().

public class Node
{
    public Node(params WeightedChild[] weightedChildren)
    {
        this.WeightedChildren = weightedChildren ?? Enumerable.Empty<WeightedChild>();
    }

    IEnumerable<WeightedChild> WeightedChildren { get; }

    public double Evaluate()
    {
        return this.WeightedChildren.Any()
            ? this.WeightedChildren.Select(child => child.Evaluate()).Sum()
            : 1;
    }
}

public class WeightedChild
{
    public WeightedChild(double weight, Node child)
    {
        this.Weight = weight;
        this.Child = child;
    }

    public double Weight { get; }
    Node Child { get; }

    public double Evaluate()
    {
        return this.Child.Evaluate() * this.Weight;
    }
}

You can then use these classes to build your data set:

var X = new Node();
var Y = new Node();
var Z = new Node();
var E2 = new Node(new WeightedChild(3.3, Z));
var E1 = new Node(new WeightedChild(2.1, Y));
var D = new Node(
    new WeightedChild(0.7, X),
    new WeightedChild(1.8, E1),
    new WeightedChild(3.1, E2));
var C2 = new Node(new WeightedChild(0.9, X));
var C1 = new Node(
    new WeightedChild(1.14, X),
    new WeightedChild(1.7, D));
var B = new Node(
    new WeightedChild(1.3, C1),
    new WeightedChild(1.5, C2));
var A = new Node(new WeightedChild(1.1, C1));

You can then evaluate each node:

Console.WriteLine($"f(E2) = {E2.Evaluate()}");
Console.WriteLine($"f(D) = {D.Evaluate()}");
Console.WriteLine($"f(C1) = {C1.Evaluate()}");

Note however, that while in your example for rule 2, you are evaulating a single "D" from row 10, the set defined in this answer captures the fact that D has multiple children and therefore will give a different answer. You could address this by redefining the Ds as D1, D2 and D3, and then add them all as children of C1 etc.