编码挑战：在值之间插入运算符以生成答案。 [英] Coding challenge: inserting operators between values to generate an answer.
本文介绍了编码挑战：在值之间插入运算符以生成答案。的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
给定一串数字，在您希望的任何数字之间插入任何运算符+ .-。/。*，％或^，以便等式计算给定数字。
例如使用1234567890创建一个等于100的等式。
答案：1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 - 0 = 100
您的解决方案应该足够通用，以便可以提供任何字符串和任何解决方案，并且应该认识到可能无法从给定输入中获得解决方案。
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.
推荐答案
还没有解决方案吗？好的，我会试一试......
这种方法很蛮力而且很慢。它使用PLINQ来加速触摸。
我假设^代表权力而不是比'xor'。我已将它包含在下面，但对其进行了评论，因为它需要真的长时间运行，我无法等待。 ：/
这是代码：
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);
}
}
}
这是演示1234567890的输出，关于短暂的咖啡休息时间：
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.
我想到的一个潜在优化是以某种方式保留先前的部分计算。这可能会节省一堆lambda调用，但由于操作顺序，实现起来会很棘手。分析可能会提供更多优化提示。
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.
这篇关于编码挑战：在值之间插入运算符以生成答案。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
