Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
5.00/5 (2 votes)
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
Comments
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.
Afzaal Ahmad Zeeshan 28-Apr-17 11:03am    
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

1 solution

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.");
            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.
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900