Threaded Equation Finder

Threaded Equation Finder

Find arithmetic equations that equates to a given 'target' value, number of terms, and operators.

View the GitHub - Download source .zip

Introduction

   You should all be familiar with how a typical computer works; you give it some variables, describe some quantities of some resources you have, choose an algorithm, let it process, and it returns to you a result or outcome. Now imagine a computer if you could work with a computer that worked the other way around. I believe it was Douglas Adams that described the notion of an all-together different type of computer; That is, you tell the computer what you want the outcome to be, and it goes off figuring out how to get there and what you need to do it. Z3, the Theorem Prover, and the constraint satisfaction problem (CSP) solver (and probably others) in Microsoft's Solver Foundation do almost exactly that.
   There is also the idea of Backcasting, which is a similar, but different idea.

   My program isn't as fancy as all that, but it does find equations that equates to a given 'target' value, albeit at random. You define constraints other than just the target value, such as what operators are allowed in the equation, the quantity of terms there, and the range or set of allowed terms.
For example, how many different ways can 9 nines equal 27, using only addition, subtraction, and multiplication, if evaluated left-to-right (ignore the order of operations)? Turns out there are only 67 ways.

(above) Application Screen Shot

How it works

   The actual approach for finding equations that equate to an arbitrary target or 'goal' value is rather primitive. By way of Brute Force, several threads are launched asynchronously to generate thousands of random equations, evaluate them and keep the results that have not been found yet.

   This is something I wrote approx. 2 years ago. I dug it up and decided to publish it, because I thought it was interesting. As this was an 'experiment', I created different ways of storing and evaluating the expressions, and have made those different 'strategies' conform to a common interface so I could easily swap them out to compare the different strategies. I have refactored the code so that each class that implements IEquation is in its own project and creates its own assembly.

   There are two fully-working strategies for representing equations: one that represented the equation as a list of 2-tuples (Term,Operator), did not perform order of operations, and was rather obtuse. The other strategy was to store the equation as a string and evaluate it using MSScriptControl.ScriptControl to Eval the string as a line of VBScript. This was unsurprisingly slower but allowed for much more robust equation evaluation. Order of operations is respected with the ScriptControl strategy, and opens the way to using using parenthesis.

   The other idea for a strategy which I have not implemented but would like to, would be a left-recursive Linq.Expression builder. Also, maybe I could somehow use Microsoft Solver Foundation for a wiser equation generation strategy than at random.

Limitations

   Today, however, there are better architectures. A concurrent system like this would benefit greatly from the Actor model. If you wanted to write complex queries against the stream of equations being generated or selected or solved, maybe reactive extensions would be a slam dunk.

   Although this project certainly is no Z3, it does provide an example of an interface... perhaps even a good one.

Running on Raspberry Pi 2

   Microsoft's Managed Extensibility Framework (MEF) might be a good thing here, but I also wrote a console client that is designed to be ran with Mono on the Raspberry Pi 2. MEF is a proprietary Microsoft .NET technology that is not supported in Mono. The extra meta data in the assembly shouldn't be a problem, but having a dependency on the MEF assembly will be. Probing of the runtime environment and dynamically loading of assemblies is required here, which I have not had time to do, so at this time, there is no MEF.

   The reason the mono client is a console application is because mono and winforms on the Raspberry Pi 2 fails for some people. The problem has something to do with a hardware floating point vs a software float, and it happens to manifest itself when using a TextBox control. The only thing that I haven't tried, and that should presumably fix it, is to re-build mono from the latest source.

Validate all input parameters in one line/Check several objects for empty or null in a single method call.

Often my methods start with several guarding clauses. That is, conditional if statements that check for null or empty parameters and immediately return if they are. This is also known as defensive programming. Usually I am not concerned with this code; indeed I identify these blocks as validation code and overlook this code entirely. It was not until recently that I noticed this as an area that I was repeating myself and could be put in a reusable function.

Lets look at the code:

/// <summary>
/// Checks the parameters for empty, nulls, or invalid states.
/// </summary>
/// <returns>True if the params are null, empty, contains an array or object that is null or empty, contains a blank, whitespace, null or empty string, or contains DataTable that does not pass a call to IsValidDatatable().</returns>
public static bool ContainsNullOrEmpty(params object[] Items)
{
    if (Items == null || Items.Length < 1)
        return true;
    
    foreach (object item in Items)
    {
        if (item == null)
            return true;
        
        if (item is string)
        {
            if (string.IsNullOrWhiteSpace(item as String))
                return true;
        }
        else if (item is DataTable)
        {
            if (!IsValidDatatable(item as DataTable))
                return true;
        }
        
        if (item.GetType().IsArray)
        {
            bool isEmpty = true;
            foreach (object itm in (Array)item)
            {
                if (ContainsEmptyOrNulls(itm))
                    return true;
                
                isEmpty = false;
            }
            if (isEmpty)
                return true;
        }
    }

    return false;
}

My approach above uses the params keyword. By using params, I can pass in any number of parameters (including zero, although that doesn't help us in this context). By using an object instead of a generic type I can pass multiple different types in one method call. If I used generics, I would have to have one method call for each type that I wanted to validate.

The idea is to cram all of your common validation logic into this method, and call it everywhere to increase the readability of your business logic by not cluttering it up with validation logic. Notice how this function also checks for empty or white-space strings, as well as calling a custom IsValidDatatable(DataTable) function. If you have several functions that return an int of -1 or 0 upon failure, you might want to add another conditional to check if (item is int) and then if the value of the integer reflects an erroneous state.

Another cool feature it that if the item is an an array, or even an array of nested arrays, it will still check every item in those arrays. Notice how I get the item type, then check the Type.IsArray property boolean. If it is true, I cast the object as an System.Array, then call ContainsEmptyOrNulls() recursively in a foreach loop. We can return true right away on the first null condition met, but we must be careful not to return on a false condition and to instead let the false conditions fall through and continue on, in the case that there is a null later or in another array.

Enjoy!