14,120,859 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
Chris Maunder 28-Apr-17 11:34am

...and of course there's an article about it! /slaps head. To be fair, the given problem is more general than that article.
OriginalGriff 28-Apr-17 11:38am

Oh yes, much more general. But you should know there is an article here about nearly everything! :laugh:
Chris Maunder 28-Apr-17 11:40am

It's truly awesome
Patrice T 28-Apr-17 13:59pm

In France, we have a TV show "Des_chiffres_et_des_lettres" which have a game very similar to this challenge. This tv show is the oldest show running on French TV.
Des chiffres et des lettres - Wikipedia[^]
Peter_in_2780 28-Apr-17 20:56pm

So that's where our SBS ("multicultural" broadcaster) got "Letters and Numbers" from.
Patrice T 28-Apr-17 21:47pm

:)

## 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:

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

Top Experts
Last 24hrsThis month
 OriginalGriff 185 Richard Deeming 130 Patrice T 130 phil.o 125 MadMyche 100
 OriginalGriff 4,056 Richard MacCutchan 1,705 Patrice T 1,267 Gerry Schmitz 944 phil.o 913