Click here to Skip to main content
14,120,859 members
Rate this:
 
Please Sign up or sign in to vote.
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
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
   
:)

1 solution

Rate this: bad
 
good
Please Sign up or sign in to vote.

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

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

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web02 | 2.8.190518.1 | Last Updated 3 May 2017
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100