I created CountDown Numbers game in c# and it works fine but it's too slow inside evaluate method where Stack is used to calculate result. I tried to use LinkedList instead of Stack but it's then even slower and I also tried to use Array instead but it's same like with Stack. Can someone please help me to create method for calculating that will be faster?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp19
{
class Program
{
private static List<string> generateCombinations(string combination, List<string> input, int pos, int length,
int inputCount = 0, List<string> combinations = null)
{
if (combinations == null)
{
combinations = new List<string>();
}
if (pos < length)
{
foreach (string num in input)
{
generateCombinations(combination + num, input, pos + 1, length, inputCount, combinations);
}
}
else
{
if (!combination.Contains("+") && !combination.Contains("-") && !combination.Contains("*") && !combination.Contains("/"))
{
if (!input.Contains("2"))
{
if (combination.Count(s => s == '0') == inputCount && isSelectorValid(combination))
{
combinations.Add(combination);
}
}
else if (checkForDuplicate(combination))
{
combinations.Add(combination);
}
}
else
{
combinations.Add(combination);
}
}
return combinations;
}
private static bool checkForDuplicate(string combination)
{
return combination.Distinct().Count() == combination.Length;
}
private static bool isSelectorValid(string selectorsCombination)
{
int numValues = 0;
for (int i = 0; i < selectorsCombination.Length; i++)
{
if (selectorsCombination.ToString().Equals("1"))
{
if (--numValues <= 0)
{
return false;
}
}
else
{
++numValues;
}
}
return numValues == 1;
}
private static int evaluate(string selectors, List<string> nums, string operators,
int numPos, int operatorPos)
{
Stack<int> stack = new Stack<int>();
int res = 0;
for (int i = 0; i < selectors.Length; i++)
{
if (selectors == '0')
{
stack.Push(Convert.ToInt32(nums[numPos++]));
continue;
}
int top = stack.Peek();
stack.Pop();
switch (operators[operatorPos++])
{
case '+':
stack.Push(stack.Pop() + top);
break;
case '-':
stack.Push(stack.Pop() - top);
break;
case '*':
stack.Push(stack.Pop() * top);
break;
case '/':
if (top == 0)
{
return 0;
}
res = stack.Peek() / top;
if (res * top != stack.Peek())
{
return 0;
}
stack.Pop();
stack.Push(res);
break;
}
}
res = stack.Pop();
return res;
}
private static string generateExp(string selectors, List<string> nums, string operators,
int numPos, int operatorPos)
{
Stack<string> stack = new Stack<string>();
for (int i = 0; i < selectors.Length; i++)
{
if (selectors == '0')
{
stack.Push(nums[numPos++]);
continue;
}
string top = stack.Peek();
stack.Pop();
switch (operators[operatorPos++])
{
case '+':
stack.Push("(" + stack.Pop() + "+" + top + ")");
break;
case '-':
stack.Push("(" + stack.Pop() + "-" + top + ")");
break;
case '*':
stack.Push("(" + stack.Pop() + "*" + top + ")");
break;
case '/':
stack.Push("(" + stack.Pop() + "/" + top + ")");
break;
}
}
string exp = stack.Pop();
return exp;
}
static void Main(string[] args)
{
List<string> nums = new List<string>() { "6", "6", "6", "6", "15", "50" };
int target = 405;
List<string> numsList = new List<string>() { "0", "1", "2", "3", "4", "5" };
List<string> operatorsList = new List<string>() { "+", "-", "*", "/" };
List<string> selectorsList = new List<string>() { "0", "1" };
Stack<int> stack = new Stack<int>();
List<string> expressions = new List<string>();
var watch = System.Diagnostics.Stopwatch.StartNew();
for (int i = 1; i <= 5; i++)
{
List<string> selectorsCombinations = generateCombinations("", selectorsList, 0, i + 1 + i, i + 1);
List<string> numbersCombinations = generateCombinations("", numsList, 0, i + 1);
List<string> operatorsCombinations = generateCombinations("", operatorsList, 0, i);
for (int j = 0; j < selectorsCombinations.Count; j++)
{
string selectorsCombination = selectorsCombinations[j];
for (int k = 0; k < numbersCombinations.Count; k++)
{
string numsbersCombination = numbersCombinations[k];
List<string> numbersCombinations2 = new List<string>();
for (int l = 0; l < numsbersCombination.Length; l++)
{
int index = Convert.ToInt32(numsbersCombination[l].ToString());
numbersCombinations2.Add(nums[index]);
}
for (int l = 0; l < operatorsCombinations.Count; l++)
{
string operatorsCombination = operatorsCombinations[l];
int res = evaluate(selectorsCombination, numbersCombinations2, operatorsCombination, 0, 0);
if (res == target || (res >= target - 10 && res <= target + 10))
{
string exp = generateExp(selectorsCombination, numbersCombinations2, operatorsCombination, 0, 0);
expressions.Add(exp + "=" + res);
}
}
}
}
}
string closestExpression = "";
int absDiff = int.MaxValue;
for (int i = 0; i < expressions.Count; i++)
{
int res = Convert.ToInt32(expressions.Substring(expressions.IndexOf('=') + 1));
if (res == target)
{
closestExpression = expressions;
break;
}
else if (res > 0 && Math.Abs(res - target) < absDiff)
{
absDiff = Math.Abs(res - target);
closestExpression = expressions;
}
}
watch.Stop();
var elapsedMs = watch.ElapsedMilliseconds / 1000;
Console.WriteLine("Expression: " + closestExpression);
Console.WriteLine("Time: " + elapsedMs);
Console.ReadKey();
}
}
}
Continue reading...