Linq Arithemetic Operator combinations

When attemptiing to solve the below assignment :

Using the Arithmetic operators ( +,-,*,/) rearrange four fives to equal the numbe开发者_JAVA技巧r 1 to 10.

Example : 5/5+5-5 =1 ,5/5+5/5=2

I tried in C# without using Linq (I don't know how to proceed further)

public void GetDetails()
{

   char[] sym = new char[] { '+', '-', '/', '*' };

   int[] AOf5 = new int[] { 5, 5, 5, 5 };


for (int i = 0; i <4; i++)
 {
    for (int j = 0; j <4; j++)
     {
       for (int k = 0; k <4; k++)
          {
             for (int l = 0; l < 4; l++)
              {

                int result1 = AOf5[0] + sym[i] + AOf5[1] + sym[j] +
                AOf5[2] + sym[k] + AOf5[3];

               int result2 = AOf5[0] + sym[i] + AOf5[1] + sym[j] +
               AOf5[2] + sym[l] + AOf5[3];

              int result3 = AOf5[0] + sym[i] + AOf5[1] +
              sym[k] + AOf5[2] + sym[l] + AOf5[3];
              ....
              ....

              }  

         }

      }
  }

}

I am unable to complete it without linq and using linq.Expecting you help.

Applying left-to-right (no precedence), I can get:

1: ((5+5)-5)/5
2:
3: ((5+5)+5)/5
4: ((5*5)-5)/5
5: ((5-5)*5)+5
6: ((5*5)+5)/5
7: ((5+5)/5)+5
8:
9:
10: ((5+5)+5)-5

With (edit: oops - the "no div" stuff was unnecessary):

    var operators = new[] {
          new { Name = "+", Func = (Func<decimal,decimal,decimal>)((x,y)=>x+y) },
          new { Name = "-", Func = (Func<decimal,decimal,decimal>)((x,y)=>x-y) },
          new { Name = "/", Func = (Func<decimal,decimal,decimal>)((x,y)=>x/y) },
          new { Name = "*", Func = (Func<decimal,decimal,decimal>)((x,y)=>x*y) }
      };
    var options = from i in Enumerable.Range(1, 10)
                  select new {i, op=(
                    from op1 in operators
                    let v1 = op1.Func(5,5)
                    from op2 in operators
                    let v2 = op2.Func(v1, 5)
                    from op3 in operators
                    let v3 = op3.Func(v2,5)
                    where v3 == i
                    select "((5" + op1.Name + "5)" + op2.Name + "5)"
                       + op3.Name + "5").FirstOrDefault()};
    foreach (var opt in options)
    {
        Console.WriteLine(opt.i + ": " + opt.op);
    }

I did it in a primitive way which I am not sure if the answer is correct. It is easier done in a spreadsheet though. Basically I modified linqfying's codes to generate codes.

Here is it:

public static void GetDetails()
{
    int ctr = 0;
    char[] sym = new char[] { '+', '-', '/', '*' };
    string num = "5";
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                for (int l = 0; l < 4; l++)
                {
                    ctr++;
                    string str = num + sym[i] + num + sym[j] + num + sym[k] + num;
                    Console.WriteLine("res = " + str + "; ");
                    Console.WriteLine("if(res>=1 && res<=10)");
                    Console.WriteLine("Console.WriteLine(\"" + str + "\");");
                }

            }

        }
    }
    //Console.WriteLine("Total:" + ctr.ToString());
}

It generates 256 sets of operations which I output to a text file, copied and pasted them into a new method:

public static void runit()
{
    float res = 0;
    res = 5+5+5+5;
    if (res >= 1 && res <= 10)
        Console.WriteLine("5+5+5+5");
    res = 5+5+5+5;
    if (res >= 1 && res <= 10)
        Console.WriteLine("5+5+5+5");
    res = 5+5+5+5;
    if (res >= 1 && res <= 10)
        Console.WriteLine("5+5+5+5");
    //......
    //......
    //......
    //......
    res = 5*5*5*5;
    if (res >= 1 && res <= 10)
        Console.WriteLine("5*5*5*5");

}

And run it again which I get 76 non-unqiue operations which fits between 1 and 10. And 19 unique ones here (left to right operations only):

5*5/5/5
5*5/5+5
5/5*5/5
5/5*5+5
5/5/5+5
5/5+5/5
5/5+5-5
5/5-5+5
5+5*5/5
5+5/5*5
5+5/5/5
5+5/5-5
5+5+5-5
5+5-5/5
5+5-5+5
5-5/5/5
5-5/5+5
5-5+5/5
5-5+5+5

I'm sure someone can come out with something more creative :P

To add:

I realised after matching with Marc's answer, the initial loops didn't cover all permutations, my answers ain't gonna be right. But since I already spent quite some time, I'll let it stay. :P

The only missing cases in Marc's solution are the ones with operation precedence like in: 5/5+5/5. I added them in an union and here is the correct query.
Marc, if you update your answer with the code below (if you think it's correct) i'll delete this answer:

var operators = new[] {
              new { Name = "+", Func = (Func<decimal,decimal,decimal>)((x,y)=>x+y) },
              new { Name = "-", Func = (Func<decimal,decimal,decimal>)((x,y)=>x-y) },
              new { Name = "/", Func = (Func<decimal,decimal,decimal>)((x,y)=>x/y) },
              new { Name = "*", Func = (Func<decimal,decimal,decimal>)((x,y)=>x*y) }
          };

var options = from i in Enumerable.Range(1, 10)
              select new
              {
                  i,
                  op = (
                      from op1 in operators
                      let v1 = op1.Func(5, 5)
                      from op2 in operators
                      let v2 = op2.Func(v1, 5)
                      from op3 in operators
                      let v3 = op3.Func(v2, 5)
                      where v3 == i
                      select "((5" + op1.Name + "5)" + op2.Name + "5)"
                         + op3.Name + "5")
                      .Union(
             //calculate 2 operations (the left and the right one),  
             //then operate them together.
                        from op1 in operators
                        let v1 = op1.Func(5, 5)
                        from op2 in operators
                        let v2 = op2.Func(5, 5)
                        from op3 in operators
                        let v3 = (op3.Name == "/" && v2 == 0) ? null : (int?)op3.Func(v1, v2)
                        where v3 == i
                        select "(5" + op1.Name + "5)" + op2.Name + "(5"
                             + op3.Name + "5)"
                      ).FirstOrDefault()
              };

foreach (var opt in options)
        {
            Console.WriteLine(opt.i + ": " + opt.op);
        }

EDIT:
A couple words about let v3 = (op3.Name == "/" && v2 == 0) ? null : (int?)op3.Func(v1, v2): this is an awfully working way to avoid divisions by 0 (which can occur, because you can divide by (5-5)).

I am pretty sure you can filter it in a better way but i left it to enphasize that this problem CAN occur.

Assuming you DON'T want to use LINQ, here is an approach to do an implementation. That said it is horribly unoptimized, and I'd recommend a much shorter LINQ implementation over it. (See: Marc Gravell's post.)

using System;
using System.Collections.Generic;

namespace MathIterator
{
  class Program
  {
    static readonly int[] _inputs = new int[] { 5, 5, 5, 5 };
    static readonly char[] _operations = new char[] { '+', '-', '*', '/' };
    static Dictionary<int, List<string>> _calculations = new Dictionary<int, List<string>>();

    static void Main(string[] args)
    {
      StartPermutation();
      PrintResults();
    }

    static void StartPermutation()
    {
      if (_inputs.Length > 0)
        Permute(1 /*index*/, _inputs[0], _inputs[0].ToString());    
    }

    static void Permute(int index, int result, string computation)
    {
      if (index == _inputs.Length)
      {
        if (!_calculations.ContainsKey(result))
        {
          _calculations[result] = new List<string>();
        }

        _calculations[result].Add(computation);
      }
      else
      {
        foreach (char operation in _operations)
        {
          string nextComputation = String.Format("({0} {1} {2})",computation, operation, _inputs[index]);
          int nextResult = result;

          switch (operation)
          {
            case '+':
              nextResult += _inputs[index];
              break;
            case '-':
              nextResult -= _inputs[index];
              break;
            case '*':
              nextResult *= _inputs[index];
              break;
            case '/':
              nextResult /= _inputs[index];
              break;
          }

          Permute(
            index + 1,
            nextResult,
            nextComputation);
        }
      }
    }

    static void PrintResults()
    {
      for (int i = 1; i <= 10; ++i)
      {
        if (_calculations.ContainsKey(i))
        {
          Console.WriteLine("Found {0} entries for key {1}", _calculations[i].Count, i);

          foreach (string calculation in _calculations[i])
          {
            Console.WriteLine(i + " = " + calculation);
          }
        }
        else
        {
          Console.WriteLine("No entry for key: " + i);
        }
      }
    }
  }
}

Here is another implementation. This one follows order of precedence. Again, I do not recommend solving it like this. Even more-so now given the wide dash hacks (to distinguish them from minus signs), but it does seem to work.

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace MathIterator
{
  class Program
  {
    static readonly int[] _inputs = new[] { 5, 5, 5, 5 };
    //HUGE hack, the '–' is a wide dash NOT a hyphen.
    static readonly char[][] _operationLevels = new[] { new[] { '*', '/' }, new[] { '+', '–' } };
    static List<string> _calculations = new List<string>();
    static Dictionary<int, List<string>> _results = new Dictionary<int, List<string>>();

    static void Main(string[] args)
    {
      StartPermutation();
      StartEvaluateCalculations();
      PrintResults();
    }

    static void StartPermutation()
    {
      if (_inputs.Length > 0)
        Permute(1 /*index*/, _inputs[0].ToString());    
    }

    static void Permute(int index, string computation)
    {
      if (index == _inputs.Length)
      {
        _calculations.Add(computation);
      }
      else
      {
        foreach (char[] operationLevel in _operationLevels)
        {
          foreach (char operation in operationLevel)
          {
            string nextComputation = String.Format("{0} {1} {2}", computation, operation, _inputs[index]);
            Permute(
              index + 1,
              nextComputation);
          }
        }
      }
    }

    static void StartEvaluateCalculations()
    {
      foreach (string calculation in _calculations)
      {
        int? result = EvaluateCalculation(calculation);

        if (result != null)
        {
          int intResult = (int) result;

          if (!_results.ContainsKey(intResult))
          {
            _results[intResult] = new List<string>();
          }

          _results[intResult].Add(calculation);            
        }
      }
    }

    static int? EvaluateCalculation(string calculation)
    {
      foreach (char[] operationLevel in _operationLevels)
      {
        string[] results = calculation.Split(operationLevel, 2);

        if (results.Length == 2)
        {
          int hitIndex = results[0].Length;

          Regex firstDigit = new Regex(@"^ -?\d+");
          Regex lastDigit = new Regex(@"-?\d+ $");

          string firstMatch = lastDigit.Match(results[0]).Value;
          int arg1 = int.Parse(firstMatch);

          string lastMatch = firstDigit.Match(results[1]).Value; 
          int arg2 = int.Parse(lastMatch);

          int result = 0;

          switch (calculation[hitIndex])
          {
            case '+':
              result = arg1 + arg2;
              break;
            //HUGE hack, the '–' is a wide dash NOT a hyphen.
            case '–':
              result = arg1 - arg2;
              break;
            case '*':
              result = arg1 * arg2;
              break;
            case '/':
              if ((arg2 != 0) && ((arg1 % arg2) == 0))
              {
                result = arg1 / arg2;
                break;
              }
              else
              {
                return null;
              }
          }

          string prePiece = calculation.Remove(hitIndex - 1 - arg1.ToString().Length);
          string postPiece = calculation.Substring(hitIndex + 1 + lastMatch.ToLower().Length);

          string nextCalculation = prePiece + result + postPiece;
          return EvaluateCalculation(nextCalculation);
        }
      }

      return int.Parse(calculation);
    }

    static void PrintResults()
    {
      for (int i = 1; i <= 10; ++i)
      {
        if (_results.ContainsKey(i))
        {
          Console.WriteLine("Found {0} entries for key {1}", _results[i].Count, i);

          foreach (string calculation in _results[i])
          {
            Console.WriteLine(i + " = " + calculation);
          }
        }
        else
        {
          Console.WriteLine("No entry for key: " + i);
        }
      }
    }
  }
}

Here's a solution which is completely LINQ based (method-syntax) and late-evaluating, which handles all permutations (not only left-to-righ):

static void Main()
{
    var solution = PermuteLength(4)
        .Where(p => Decimal.Floor(p.Value) == p.Value)
        .Where(p => p.Value <= 10 && p.Value >= 0)
        .OrderBy(p => p.Value);

    foreach (var p in solution)
    {
        Console.WriteLine(p.Formula + " = " + p.Value);
    }
}

public static Operator[] Operators = new[]
    {
        new Operator {Format = "({0} + {1})", Function = (x, y) => x + y},
        new Operator {Format = "({0} - {1})", Function = (x, y) => x - y},
        new Operator {Format = "({1} - {0})", Function = (x, y) => y - x},
        new Operator {Format = "({0} * {1})", Function = (x, y) => x * y},
        new Operator {Format = "({0} / {1})", Function = (x, y) => y == 0 ? 0 : x / y},
        new Operator {Format = "({1} / {0})", Function = (x, y) => x == 0 ? 0 : y / x},
    };

public static IEnumerable<Permutation> BasePermutation = new[] { new Permutation {Formula = "5", Value = 5m} };

private static IEnumerable<Permutation> PermuteLength(int length)
{
    if (length <= 1)
        return BasePermutation;

    var result = Enumerable.Empty<Permutation>();

    for (int i = 1; i <= length / 2; i++)
        result = result.Concat(Permute(PermuteLength(i), PermuteLength(length - i)));

    return result;
}

private static IEnumerable<Permutation> Permute(IEnumerable<Permutation> left, IEnumerable<Permutation> right)
{
    IEnumerable<IEnumerable<IEnumerable<Permutation>>> product = left.Select(l => right.Select(r => ApplyOperators(l, r)));

    var aggregate =
        product.Aggregate(Enumerable.Empty<IEnumerable<Permutation>>(), (result, item) => result.Concat(item)).
            Aggregate(Enumerable.Empty<Permutation>(), (result, item) => result.Concat(item));

    return aggregate;
}

private static IEnumerable<Permutation> ApplyOperators(Permutation left, Permutation right)
{
    return Operators.Select(o => new Permutation
    {
        Formula = string.Format(o.Format, left.Formula, right.Formula),
        Value = o.Function(left.Value, right.Value)
    });
}

public struct Permutation
{
    public string Formula;
    public decimal Value;
}

public struct Operator
{
    public string Format;
    public Func<decimal, decimal, decimal> Function;
}

Known problems: Some solutions are duplicate, Doesn't handle division-by-zero very well, so some wrong answers (I've assumed anything divided by zero = 0)

Edit: A part of result:

((5 / 5) / (5 / 5)) = 1

((5 / 5) + (5 / 5)) = 2

((5 + (5 + 5)) / 5) = 3

(5 - ((5 + 5) / 5)) = 3

(((5 * 5) - 5) / 5) = 4

(5 + (5 * (5 - 5))) = 5

(5 - (5 * (5 - 5))) = 5

(5 + ((5 - 5) / 5)) = 5

(5 - ((5 - 5) / 5)) = 5