Algorithm for testing all mathematical order-CodePudding

I want to implement, that the User can input a Array of ints (int[]), and a desired target.

Then the program should be able to test all possibilities in add, subtract, multiply and divide, and return true, if any possibilities are given.

Example:

int[] = {1, 4, 6, 3}, target = 8

(Program test everything, from 1 4 6 3 till 1/4/6/3)

Desired result

1 4 6-3

is the correct answer, since 1 4 6-3 == 8

CodePudding user response：

Let's try brute force - we have just few formulae (3**4 == 81 of them) to test. First, let's generate all formlae:

using System.Data;
using System.Linq;

...

private static IEnumerable<string> Formulae(int[] numbers) {
  char[] alphabet = new char[] { ' ', '-', '*', '/' };

  int[] current = new int[numbers.Length - 1];

  do {
    yield return string.Concat(numbers
      .Select((d, i) => $"{(i > 0 ? alphabet[current[i - 1]].ToString() : "")}{d}"));

    for (int i = 0; i < current.Length;   i)
      if ((current[i] = (current[i]   1) % alphabet.Length) != 0)
        break;
  }
  while (!current.All(i => i == 0));
}

then we Compute each formula:

private static string Solve(int[] numbers, int target) {
  using (DataTable table = new DataTable()) {
    foreach (string formula in Formulae(numbers)) {
      try {
        int result = Convert.ToInt32(table.Compute(formula, null));

        if (result == target)
          return $"{formula} = {target}";
      }
      catch (DivideByZeroException) {
        ;
      }
    }
  }

  return "No solution";
}

Demo:

Console.Write(Solve(new int[] { 1, 4, 6, 3 }, 8));

Outcome:

1 4 6-3 = 8

You need just a little modification, if you want to get all solutions:

private static IEnumerable<string> AllSolutions(int[] numbers, int target) {
  using (DataTable table = new DataTable()) {
    foreach (string formula in Formulae(numbers)) {
      int result; 

      try {
        result = Convert.ToInt32(table.Compute(formula, null));
      }
      catch (DivideByZeroException) {
        continue;
      }

      if (result == target)
        yield return $"{formula} = {target}";
    }
  }
}

Demo:

Console.Write(string.Join(Environment.NewLine, 
  AllSolutions(new int[] { 1, 4, 6, 3 }, 8)));

Outcome:

1 4 6-3 = 8
1*4*6/3 = 8

Edit: in the implementation above I used integer division, e.g.

1 / 4 == 0

if you want to use floating point division, i.e.

1.0 / 4.0 = 0.25

you should slightly modify the code:

// note ".0" in the very end of the Select 
private static IEnumerable<string> Formulae(int[] numbers) {
  ...
  yield return string.Concat(numbers
    .Select((d, i) => $"{(i > 0 ? alphabet[current[i - 1]].ToString() : "")}{d}.0"));
  ...
}

private static IEnumerable<string> AllSolutions(int[] numbers, 
                                                int target, 
                                                double tolerance = 1e-8) {
  using (DataTable table = new DataTable()) {
    foreach (string formula in Formulae(numbers)) {
      double result = Convert.ToDouble(table.Compute(formula, null));

      // Compare with tolerance
      if (Math.Abs(result - target) < tolerance)
        yield return $"{formula} = {target}";
    }
  }
}