Coding challenge: inserting operators between values to generate an answer.

No solutions yet? Okay, I'll give this a shot...

This method is brute force and rather slow. It uses PLINQ to speed things up a touch.

I've assumed that ^ represents 'power' rather than 'xor'. I've included it below but commented it out, because it takes a really long time to run and I couldn't be bothered waiting. :/

Here's the code:

// requires nuget: "Combinatorics"
// https://github.com/eoincampbell/combinatorics/
// https://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace CodingChallenge_OperatorInsertion
{
    using op = KeyValuePair<string, Func<int, int, int?>>;

    static class Program
    {
        static void Main(string[] args)
        {
            TestString("1234567890");
            Console.WriteLine("Done. Hit enter to quit.");
            Console.ReadLine();
        }

        static void TestString(string test)
        {
            var consoleLock = new object();

            var solutions = NumberOperatorSequence.GetMatchingSequences(
                test, 100);

            var output = new List<NumberOperatorSequence>();
            var sw = new Stopwatch();
            sw.Start();

            solutions.AsParallel().ForAll(s =>
            {
                var text = s.ToString();
                lock (consoleLock)
                {
                    Console.WriteLine(text);
                    output.Add(s);
                }
            });

            sw.Stop();
            Console.WriteLine(string.Format(
                "Found {0} solutions from {1} candidates in {2} seconds.",
                output.Count, 
                Math.Pow(NumberOperatorSequence.Operators
                         .SelectMany(a => a)
                         .Count(),
                    test.Length - 1),
                sw.Elapsed.TotalSeconds));
        }
    }

    public class NumberOperatorSequence
    {
        public NumberOperatorSequence(
            IEnumerable<int> values,
            IEnumerable<op> operators)
        {
            this.values = values.ToArray();
            this.operators = operators.ToArray();
            if (this.values.Length != this.operators.Length + 1)
                throw new ArgumentException(
                    "Operators must have one fewer elements than values.",
                    nameof(operators));

            this._Result = new Lazy<int?>(() =>
            {
                List<int> vl = this.values.ToList();
                List<op> ol = this.operators.ToList();
                foreach (var currentOpSet in Operators)
                    for (int i = 0; i < ol.Count; i++)
                        foreach (var currentOp in currentOpSet)
                            if (ol[i].Key == currentOp.Key)
                            {
                                var newVal = currentOp.Value(vl[i], vl[i + 1]);
                                if (!newVal.HasValue) return null; // div by 0
                                vl[i + 1] = newVal.Value;
                                vl.RemoveAt(i);
                                ol.RemoveAt(i);
                                i--;   // prepare to retry this position
                                break; // restart the position
                            }
                return vl.Single();
            });

            this._AsString = new Lazy<string>(() =>
            {
                var sb = new StringBuilder();
                for (int i = 0; i < this.values.Length - 1; i++)
                {
                    sb.Append(this.values[i]);
                    sb.Append(this.operators[i].Key);
                }
                sb.Append(this.values[this.values.Length - 1]);
                sb.Append("=");
                sb.Append(Result);
                return sb.ToString();
            });
        }

        readonly int[] values;
        readonly op[] operators;

        public override string ToString() { return _AsString.Value; }
        readonly Lazy<string> _AsString;

        public int? Result { get { return _Result.Value; } }
        readonly Lazy<int?> _Result;

        // available operators in order of precedence
        public static op[][] Operators = new op[][]
        {
            new op[]
            {
                new op("",  (l,r) => {
                    try { checked { return l * 10 + r; } }
                    catch { return null; }
                })
            },
            //new op[] {
            //    new op("^",  (l,r) => {
            //        try { checked { return (int)(Math.Round(Math.Pow(l, r))); } }
            //        catch { return null; }
            //    })
            //},
            new op[]
            {
                new op("*",  (l,r) => {
                    try { checked { return l * r; } }
                    catch { return null; }
                }),
                new op("/",  (l,r) => {
                    if (r == 0) return default(int?);
                    try { checked { return l / r; } }
                    catch { return null; }
                }),
                new op("%",  (l,r) => {
                    if (r == 0) return default(int?);
                    try { checked { return l % r; } }
                    catch { return null; }
                })
            },
            new op[]
            {
                new op("+",  (l,r) => {
                    try { checked { return l + r; } }
                    catch { return null; }
                }),
                new op("-",  (l,r) => {
                    try { checked { return l - r; } }
                    catch { return null; }
                }),
            }
        };

        public static IEnumerable<IEnumerable<op>> GetOperatorPermuations(
            int length)
        {
            return new Combinatorics.Collections.Variations<op>(
                Operators.SelectMany(a => a),
                length,
                Combinatorics.Collections.GenerateOption.WithRepetition);
        }

        public static IEnumerable<NumberOperatorSequence> GetMatchingSequences(
            IEnumerable<int> values, int result)
        {
            return from ops in GetOperatorPermuations(values.Count() - 1)
                let seq = new NumberOperatorSequence(values, ops)
                let res = seq.Result
                where res.HasValue
                where res.Value == result
                select seq;
        }
        public static IEnumerable<NumberOperatorSequence> GetMatchingSequences(
            string values, int result)
        {
            return GetMatchingSequences(
                values.Select(c => Convert.ToInt32(c.ToString())),
                result);
        }
    }
}

And here's the output for the demo "1234567890", taking about a short coffee break:

...
...
...
1-2-3+4+5+6%7+89-0=100
1-2-3+4+5+6+7-8+90=100
1-2-3+4-5%6+7+8+90=100
1-2-3-45+67-8+90=100
1-2-3-4*5+6*7-8+90=100
1-2-3-4/5+6%7+8+90=100
1-2-3-4+5*6+78%90=100
1-2-3-4+5*6+78+9*0=100
1-2-3-4+5*6+78-9*0=100
1-2-3-4+5+6+7%8+90=100
Found 5116 solutions from 10077696 candidates in 522.882111 seconds.
Done. Hit enter to quit.

One potential optimisation I have in mind is to retain previous partial calculations somehow. This might save a bunch of lambda calls, but it would be tricky to implement thanks to the order of operations. Profiling might give more optimisation hints.