15,998,180 members
See more:
Given a string of numbers insert any of the operators +.-./.*, % or ^ between whichever digits you wish so that the equation evaluates to the given number.

eg Use 1234567890 to create an equation that equals 100.

Answer: 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 - 0 = 100

Your solution should be general enough that any string and any solution can be provided, and should recognise the possibility that no solution from the given input is possible.
Posted
Updated 3-May-17 0:04am
Patrice T 28-Apr-17 9:09am
-Are digits kept in order of input ?
- Can we use unary minus ?
Richard Deeming 28-Apr-17 9:24am
Simple - just put `+` between each number, and then either `=` or `!=` between the equation and the answer. ðŸ˜‹
PIEBALDconsult 28-Apr-17 9:34am
Or put only the = or != and forget the rest.
Correct and then just check how greater the number is, then subtract that number at the end. You're a genius! :D
OriginalGriff 28-Apr-17 10:12am
You mean ... something like this?

Countdown Number Puzzle Solver

## Solution 1

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:

C#
```// 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.");
}

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);
}
});

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();
});
}

public override string ToString() { return _AsString.Value; }

public int? Result { get { return _Result.Value; } }

// 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.

v2