Movimentum - The solver algorithm, second try cont'd.

For our very simple equations,

0 = y + 2
0 = x + y

a second step should suffice to finde the solution. Here is a test case that wants to prove this:

    [Test]
    public void Test2SimpleConstraintsAndTwoSteps() {
        // Try to solve:
        //   0 = y + 2
        //   0 = x + y

        ...set as in previous test...

        // First step
        IEnumerable<SolverNode> expanded1 =
            SolverNode.SolverStep(new[] { current },
                new Dictionary<Variable, VariableRangeRestriction>(),
                out solutionOrNull);

        // Second step: Find that x = 2, substitute 2 for x everywhere, 
        // and declare the equations to be solved.
        IEnumerable<SolverNode> expanded2 =
            SolverNode.SolverStep(expanded1,
                new Dictionary<Variable, VariableRangeRestriction>(),
                out solutionOrNull);
        Assert.AreEqual(1, expanded2.Count());
        Assert.IsNotNull(solutionOrNull);
    }

However, this test is red: solutionOrNull remains null. If we look into our solver code, it is clear why: Towards the end of our first attempt of a solver algorithm, I stated that we have to

• record that –C is a solution for V;
• create the rewriting V → –C.

But we never wrote code for the first item! Let us now do this.

VariableValueRestrictions

First, we need a tiny class that remembers that a variable has a certain value. As we started with a general class "VariableRangeRestriction" in the posting mentioned, we create an abstract class with the former name, and a derived class that can only hold a single value:

public abstract class VariableRangeRestriction {
    private readonly Variable _variable;

    protected VariableRangeRestriction(Variable variable) {
        _variable = variable;
    }

    public Variable Variable { get { return _variable; } }
}

public class VariableValueRestriction : VariableRangeRestriction {
    private readonly double _value;

    public VariableValueRestriction(Variable variable, double value)
            : base(variable) {
        _value = value;
    }

    public double Value { get { return _value; } }
}

With this, we can now improve the code of FindBestRewrite—we add knowledge about the variable and its definitive value:

    private VariableToConstantRewrite FindBestRewrite(...) {
        ...
        foreach (var c in Constraints.OfType<ScalarConstraint>()) {
            ...
            if (matcher.TryMatch(c)) {
                Variable variable = matcher.Match(v);
                double value = -matcher.Match(e).Value;
                _variableInRangeKnowledges.Add(variable,
                    new VariableValueRestriction(variable, value));
                return new VariableToConstantRewrite(variable, value);
            }
        }
        throw new NotSupportedException("I found no 0=V+E-Constraint");
    }

Removing  0 = C

One test run later, we know that this was not enough. A bit of debugging shows why: The second node created actually does have VariableValueRestrictions for both variables, so it did find the solution. But our method to find a solution node was to check for one without constraints—however, our rewritings left us with two constraints of the form 0 = 0 that were never removed. Therefore, we never arrived at a node without constraints.

Obviously, there are two ways to solve the problem:

• Throw away constraints of the form 0 = 0.
• Replace the solution check with another one.

Probably we should do both. But removing constraints of the form 0 = C is certainly worth the effort, especially if we also handle non-zero values for C: This means that no solution can be found for this SolverNode! Here is a short outline for an algorithm handling 0 = C constraints:

• If we find such a constraint with constant zero, then we need a "rewrite" that just removes this constraint.
• If we find one with a constant other than zero, our constraints want to state (probably after some rewriting) that "zero is not zero." In this case, the SolverNode's expansion must be an empty set!

Here is a piece of code that tries to implement this:

    private VariableToConstantRewrite FindBestRewrite(...) {
        var z = new TypeMatchTemplate<Constant>();
        var zeroEqualsConstant = new EqualsZeroConstraintTemplate(z);

        ...as before...
        foreach (var c in Constraints.OfType<ScalarConstraint>()) {
            var matcher2 = new ScalarConstraintMatcher(zeroEqualsConstant);
            if (matcher2.TryMatch(c)) {
                if (matcher2.Match(z).Value == 0) {
                    return new RemoveThisConstraint(c);
                } else {
                    return new MarkAsDeadEnd(this);
                }
            }

            ...as before...
        }
        throw new NotSupportedException("I found no 0=V+E-Constraint");
    }

We now need two more rewriting classes (the ones that ReSharper shows red), and the return type of FindBestRewrite is now wrong ... Obviously, we need to redesign the code around FindBestRewrite and ExecuteRewrites somewhat. Here is a suggestion which might hold out for some time: Instead of writing more and more rewrite classes, we let FindBestRewrite return a Func that creates new SolverNodes; and instead of the separate method ExecuteRewrites, we just execute the returned Func. Expand then looks like this:

    public IEnumerable<SolverNode> Expand(...) {
        Func<IEnumerable<SolverNode>> rewrite =
            FindBestRewrite(previousValues);
        return rewrite();
    }

Here, then is the new FindBestRewrite method that checks each constraint against two patterns—first, against 0 = C, then against 0 = V + C:

    private Func<IEnumerable<SolverNode>> FindBestRewrite(...) {
        var z = new TypeMatchTemplate<Constant>();
        var zeroEqualsConstant = new EqualsZeroConstraintTemplate(z);

        var v = new TypeMatchTemplate<Variable>();
        var e = new TypeMatchTemplate<Constant>();
        var zeroEqualsVPlusE = new EqualsZeroConstraintTemplate(v + e);

        foreach (var c in Constraints.OfType<ScalarConstraint>()) {
            {
            var matcher2 = new ScalarConstraintMatcher(zeroEqualsConstant);
            if (matcher2.TryMatch(c)) {
                if (matcher2.Match(z).Value == 0) {
                    // Just drop 0 = 0
                    return () => new[] {
                        new SolverNode(Constraints.Except(new[] {c}), this)
                    };
                } else {
                    // Unsolvable!
                    return () => new SolverNode[0];
                }
            }
            }

            {
            var matcher = new ScalarConstraintMatcher(zeroEqualsVPlusE);
            if (matcher.TryMatch(c)) {
                Variable variable = matcher.Match(v);
                double value = -matcher.Match(e).Value;
                _variableInRangeKnowledges.Add(variable,
                    new VariableValueRestriction(variable, value));
                return () => {
                    ...code from former ExecuteRewrites method...
                };
            }
            }
        }
        throw new NotSupportedException("I found no 0=V+E-Constraint");
    }

This is not yet a satisfying design—we expect that we will write many more such "if match then do" rules. That would create a FindBestRewrite method that gets longer and longer. However, for the moment, we keep this simple design, and run our test again. And it is still red.

A correct and complete test case

One second of thinking reveals why: We need four steps to solve our equations:

• Substitute –2 for y everywhere.
• Remove the resulting 0 = 0 constraint.
• Substitute 2 for x everywhere.
• Remove the second resulting 0 = 0 constraint.

So we have to rewrite our test—it gets somewhat long winded, but so it goes:

    [Test]
    public void Test2SimpleConstraintsAndTwoSteps() {
        // Try to solve:
        //   0 = y + 2
        //   0 = x + y
        EqualsZeroConstraint e1 =
            new EqualsZeroConstraint(
                new NamedVariable("y") + new Constant(2));
        EqualsZeroConstraint e2 =
            new EqualsZeroConstraint(
                new NamedVariable("x") + new NamedVariable("y"));
        var current = new SolverNode(new[] { e1, e2 }, null);
        SolverNode solutionOrNull;

        var NoRestrictions =  
            new Dictionary<Variable, VariableRangeRestriction>();

        // First step
        IEnumerable<SolverNode> expanded1 =
            SolverNode.SolverStep(new[] { current },
                NoRestrictions,
                out solutionOrNull);
        Assert.IsNull(solutionOrNull);

        // Second step: Remove 0 = 0
        IEnumerable<SolverNode> expanded2 =
            SolverNode.SolverStep(expanded1,
                NoRestrictions,
                out solutionOrNull);
        Assert.IsNull(solutionOrNull);

        // Third step: Find that x = 2, substitute 2 for x everywhere.
        IEnumerable<SolverNode> expanded3 =
            SolverNode.SolverStep(expanded2,
                NoRestrictions,
                out solutionOrNull);
        Assert.IsNull(solutionOrNull);

        // Fourth step: Remove 0 = 0.
        IEnumerable<SolverNode> expanded4 =
            SolverNode.SolverStep(expanded3,
                NoRestrictions,
                out solutionOrNull);
        Assert.AreEqual(1, expanded4.Count());

        // Check that we found the right solution.
        Assert.IsNotNull(solutionOrNull);
        AssertVariable(solutionOrNull.VariableKnowledge, -2, "y");
        AssertVariable(solutionOrNull.VariableKnowledge, 2, "x");
    }

    private static void AssertVariable(
            IDictionary<Variable, VariableRangeRestriction> solution,
            double expected, string variablename) {
        VariableValueRestriction varKnowledge =
            solution[new NamedVariable(variablename)]
            as VariableValueRestriction;
        Assert.IsNotNull(varKnowledge);
        Assert.AreEqual(expected, varKnowledge.Value, 1e-10);
    }

And finally, we have a green test → blog about it!