H2O-au
Еще нет решений? Ладно,я попробую...
Этот метод является грубой силой и довольно медленным. Он использует PLINQ, чтобы ускорить процесс прикосновения.
Я предполагал, что ^ представляет собой "власть", а не "xor". Я включил его ниже, но прокомментировал, потому что это занимает некоторое время. действительно бежать было долго,и я не мог ждать. :/
Вот код:
// 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);
}
}
}
А вот и вывод для демо-версии "1234567890", взяв примерно короткий перерыв на кофе:
...
...
...
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.
Одна потенциальная оптимизация, которую я имею в виду, заключается в том, чтобы каким-то образом сохранить предыдущие частичные вычисления. Это может сэкономить кучу лямбда-вызовов, но реализовать их будет сложно из-за порядка операций. Профилирование может дать больше подсказок по оптимизации.