CountDown Numbers game evaluate method is too slow

Pavle

Well-known member
Joined
Oct 4, 2016
Messages
47
Programming Experience
1-3
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?

C#:
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[i].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[i] == '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[i] == '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[i].Substring(expressions[i].IndexOf('=') + 1));

                if (res == target)
                {
                    closestExpression = expressions[i];
                    break;
                }
                else if (res > 0 && Math.Abs(res - target) < absDiff)
                {
                    absDiff = Math.Abs(res - target);
                    closestExpression = expressions[i];
                }
            }

            watch.Stop();
            var elapsedMs = watch.ElapsedMilliseconds / 1000;

            Console.WriteLine("Expression: " + closestExpression);
            Console.WriteLine("Time: " + elapsedMs);
            Console.ReadKey();
        }
    }
}
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
2,409
Location
Chesapeake, VA
Programming Experience
10+
Based on this profiling run, it looks like it's not the stack that is slowing you down, but your parsing a string into a number.
Screenshot_3.png


Screenshot_4.png
 

Pavle

Well-known member
Joined
Oct 4, 2016
Messages
47
Programming Experience
1-3
Based on this profiling run, it looks like it's not the stack that is slowing you down, but your parsing a string into a number.
View attachment 836

View attachment 837
I created method to generate all permutations from int values instead of string values and after removing part for converting to int method for calculation is much faster.

Thank you very much. How I can make program to be faster?

C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp19
{
    class Program
    {
        private static List<List<int>> generate(int[] input)
        {
            List<List<int>> combinations = new List<List<int>>();
            int a = 0, b = 0, c = 0, d = 0, e = 0;

            for (int i = 0; i < input.Length; i++)
            {
                if (i == 0)
                {
                    a = 1;
                }
                else
                {
                    a = 0;
                }

                for (int j = a; j < input.Length; j++)
                {
                    if (j == 0)
                    {
                        b = 1;
                    }
                    else
                    {
                        b = 0;
                    }

                    string combination = i + "" + j;

                    if (combination.Distinct().Count() == combination.Length)
                    {
                        combinations.Add(new List<int>() { input[i], input[j] });
                    }

                    for (int k = b; k < input.Length; k++)
                    {
                        if (k == 0)
                        {
                            c = 1;
                        }
                        else
                        {
                            c = 0;
                        }

                        combination = i + "" + j + "" + k;

                        if (combination.Distinct().Count() == combination.Length)
                        {
                            combinations.Add(new List<int>() { input[i], input[j], input[k] });
                        }

                        for (int l = c; l < input.Length; l++)
                        {
                            if (l == 0)
                            {
                                d = 1;
                            }
                            else
                            {
                                d = 0;
                            }

                            combination = i + "" + j + "" + k + "" + l;

                            if (combination.Distinct().Count() == combination.Length)
                            {
                                combinations.Add(new List<int>() { input[i], input[j], input[k], input[l] });
                            }

                            for (int m = d; m < input.Length; m++)
                            {
                                if (m == 0)
                                {
                                    e = 1;
                                }
                                else
                                {
                                    e = 0;
                                }

                                combination = i + "" + j + "" + k + "" + l + "" + m;

                                if (combination.Distinct().Count() == combination.Length)
                                {
                                    combinations.Add(new List<int>() { input[i], input[j], input[k], input[l], input[m] });
                                }

                                for (int n = e; n < input.Length; n++)
                                {
                                    combination = i + "" + j + "" + k + "" + l + "" + m + "" + n;

                                    if (combination.Distinct().Count() == combination.Length)
                                    {
                                        combinations.Add(new List<int>() { input[i], input[j], input[k], input[l], input[m], input[n] });
                                    }
                                }
                            }
                        }
                    }
                }
            }

            combinations = combinations.OrderBy(x => x.Count).ToList();

            return combinations;
        }

        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[i].ToString().Equals("1"))
                {
                    if (--numValues <= 0)
                    {
                        return false;
                    }
                }
                else
                {
                    ++numValues;
                }
            }

            return numValues == 1;
        }

        private static int evaluate(string selectors, List<int> 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[i] == '0')
                {
                    stack.Push(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.Pop() / top;
                        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<int> nums, string operators,
            int numPos, int operatorPos)
        {
            Stack<string> stack = new Stack<string>();

            for (int i = 0; i < selectors.Length; i++)
            {
                if (selectors[i] == '0')
                {
                    stack.Push(nums[numPos++].ToString());
                    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)
        {
            int[] input = new int[]{ 0, 1, 2, 3, 4, 5 };

            List<List<int>> numbersCombinations = generate(input);

            List<int> nums = new List<int>() { 6, 6, 6, 6, 15, 50 };
            int target = 405;

            List<string> operatorsList = new List<string>() { "+", "-", "*", "/" };
            List<string> selectorsList = new List<string>() { "0", "1" };
            List<string> expressions = new List<string>();

            var watch = System.Diagnostics.Stopwatch.StartNew();

            for (int i = 5; i <= 5; i++)
            {
                List<string> selectorsCombinations = generateCombinations("", selectorsList, 0, i + 1 + i, i + 1);
                List<string> operatorsCombinations = generateCombinations("", operatorsList, 0, i);
                List<List<int>> numbersCombinations2 = numbersCombinations.Where(s => s.Count == i + 1).ToList();

                for (int j = 0; j < selectorsCombinations.Count; j++)
                {
                    string selectorsCombination = selectorsCombinations[j];

                    for (int k = 0; k < numbersCombinations2.Count; k++)
                    {
                        List<int> numbersCombination = numbersCombinations2[k];
                        List<int> numbersCombinations3 = new List<int>();

                        for (int l = 0; l < numbersCombination.Count; l++)
                        {
                            numbersCombinations3.Add(nums[numbersCombination[l]]);
                        }

                        for (int l = 0; l < operatorsCombinations.Count; l++)
                        {
                            string operatorsCombination = operatorsCombinations[l];

                            int res = evaluate(selectorsCombination, numbersCombinations3, operatorsCombination, 0, 0);

                            if (res == target || (res >= target - 10 && res <= target + 10))
                            {
                                string exp = generateExp(selectorsCombination, numbersCombinations3, 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[i].Substring(expressions[i].IndexOf('=') + 1));

                if (res == target)
                {
                    closestExpression = expressions[i];
                    break;
                }
                else if (res > 0 && Math.Abs(res - target) < absDiff)
                {
                    absDiff = Math.Abs(res - target);
                    closestExpression = expressions[i];
                }
            }

            watch.Stop();
            var elapsedMs = watch.ElapsedMilliseconds / 1000;

            Console.WriteLine("Expression: " + closestExpression);
            Console.WriteLine("Time: " + elapsedMs);
            Console.ReadKey();
        }
    }
}
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
2,409
Location
Chesapeake, VA
Programming Experience
10+
Just eyeballing stuff, it seems that you keep on doing this:
C#:
combination.Distinct().Count() == combination.Length
on a string to determine if there all the characters in the string is unique. Furthermore, it looks like you are using a string as a data structure. Why not just use HashSet<char> if the string truly contains a "combination". Recall that in a combination, the order of the items does not matter. If the order does matter, then its a "permutation", not a "combination".
 

Pavle

Well-known member
Joined
Oct 4, 2016
Messages
47
Programming Experience
1-3
Just eyeballing stuff, it seems that you keep on doing this:
C#:
combination.Distinct().Count() == combination.Length
on a string to determine if there all the characters in the string is unique. Furthermore, it looks like you are using a string as a data structure. Why not just use HashSet<char> if the string truly contains a "combination". Recall that in a combination, the order of the items does not matter. If the order does matter, then its a "permutation", not a "combination".

I removed that part for checking string and I am now checking indices instead. For generating operator permutations I am still using generateCombinations method because permutations must be strings.
I also removed combination.Count(s => s == '0') and I use for loop to get count of zeros.
What else I should change to make program faster?

C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp19
{
    class Program
    {
        private static List<List<int>> generate(int[] input)
        {
            List<List<int>> combinations = new List<List<int>>();
            int a = 0, b = 0, c = 0, d = 0, e = 0;

            for (int i = 0; i < input.Length; i++)
            {
                if (i == 0)
                {
                    a = 1;
                }
                else
                {
                    a = 0;
                }

                for (int j = a; j < input.Length; j++)
                {
                    if (j == 0)
                    {
                        b = 1;
                    }
                    else
                    {
                        b = 0;
                    }

                    if (i != j)
                    {
                        combinations.Add(new List<int>() { input[i], input[j] });
                    }

                    for (int k = b; k < input.Length; k++)
                    {
                        if (k == 0)
                        {
                            c = 1;
                        }
                        else
                        {
                            c = 0;
                        }

                        if (i != j && i != k && j != k)
                        {
                            combinations.Add(new List<int>() { input[i], input[j], input[k] });
                        }

                        for (int l = c; l < input.Length; l++)
                        {
                            if (l == 0)
                            {
                                d = 1;
                            }
                            else
                            {
                                d = 0;
                            }

                            if (i != j && i != k && i != l && j != k && j != l && k != l)
                            {
                                combinations.Add(new List<int>() { input[i], input[j], input[k], input[l] });
                            }

                            for (int m = d; m < input.Length; m++)
                            {
                                if (m == 0)
                                {
                                    e = 1;
                                }
                                else
                                {
                                    e = 0;
                                }

                                if (i != j && i != k && i != l && i != m && j != k && j != l && j != m && k != l && k != m && l != m)
                                {
                                    combinations.Add(new List<int>() { input[i], input[j], input[k], input[l], input[m] });
                                }

                                for (int n = e; n < input.Length; n++)
                                {
                                    if (i != j && i != k && i != l && i != m && i != n && j != k && j != l && j != m
                                        && j != n && k != l && k != m && k != n && l != m && l != n && m != n)
                                    {
                                        combinations.Add(new List<int>() { input[i], input[j], input[k], input[l], input[m], input[n] });
                                    }
                                }
                            }
                        }
                    }
                }
            }

            combinations = combinations.OrderBy(x => x.Count).ToList();

            return combinations;
        }

        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 (input[0].Equals("0") || input[0].Equals("1"))
                {
                    int count = 0;

                    for (int i = 0; i < combination.Length; i++)
                    {
                        if (combination[i] == '0')
                        {
                            count++;
                        }
                    }

                    if (count == inputCount && isSelectorValid(combination))
                    {
                        combinations.Add(combination);
                    }
                }
                else
                {
                    combinations.Add(combination);
                }
            }

            return combinations;
        }

        private static bool isSelectorValid(string selectorsCombination)
        {
            int numValues = 0;

            for (int i = 0; i < selectorsCombination.Length; i++)
            {
                if (selectorsCombination[i].ToString().Equals("1"))
                {
                    if (--numValues <= 0)
                    {
                        return false;
                    }
                }
                else
                {
                    ++numValues;
                }
            }

            return numValues == 1;
        }

        private static int evaluate(string selectors, List<int> 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[i] == '0')
                {
                    stack.Push(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<int> nums, string operators,
            int numPos, int operatorPos)
        {
            Stack<string> stack = new Stack<string>();

            for (int i = 0; i < selectors.Length; i++)
            {
                if (selectors[i] == '0')
                {
                    stack.Push(nums[numPos++].ToString());
                    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)
        {
            int[] input = new int[]{ 0, 1, 2, 3, 4, 5 };

            List<List<int>> numbersCombinations = generate(input);

            List<int> nums = new List<int>() { 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> operatorsCombinations = generateCombinations("", operatorsList, 0, i);
                List<List<int>> numbersCombinations2 = numbersCombinations.Where(s => s.Count == i + 1).ToList();

                for (int j = 0; j < selectorsCombinations.Count; j++)
                {
                    string selectorsCombination = selectorsCombinations[j];

                    for (int k = 0; k < numbersCombinations2.Count; k++)
                    {
                        List<int> numbersCombination = numbersCombinations2[k];
                        List<int> numbersCombinations3 = new List<int>();

                        for (int l = 0; l < numbersCombination.Count; l++)
                        {
                            numbersCombinations3.Add(nums[numbersCombination[l]]);
                        }

                        for (int l = 0; l < operatorsCombinations.Count; l++)
                        {
                            string operatorsCombination = operatorsCombinations[l];

                            int res = evaluate(selectorsCombination, numbersCombinations3, operatorsCombination, 0, 0);

                            if (res == target || (res >= target - 10 && res <= target + 10))
                            {
                                string exp = generateExp(selectorsCombination, numbersCombinations3, 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[i].Substring(expressions[i].IndexOf('=') + 1));

                if (res == target)
                {
                    closestExpression = expressions[i];
                    break;
                }
                else if (res > 0 && Math.Abs(res - target) < absDiff)
                {
                    absDiff = Math.Abs(res - target);
                    closestExpression = expressions[i];
                }
            }

            watch.Stop();
            var elapsedMs = watch.ElapsedMilliseconds / 1000;

            Console.WriteLine("Expression: " + closestExpression);
            Console.WriteLine("Time: " + elapsedMs);
            Console.ReadKey();
        }
    }
}
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
2,409
Location
Chesapeake, VA
Programming Experience
10+
The best way to tell is to run a profiler against your code and find the hotspots. Also watch for where there are a lot of garbage collection events.

Personally, I think that the generation of the permutations and combinations can be sped up and that you should choose better data structures. That is just a gut feel based on how complex the code looks and all the string concatenations. Again a profiler will give you more insight. Look in MSDN. There are .NET Framework recommendations on improving performance.

As I recall, one of those recommendations is to use the StringBuilder if you are doing a lot of string concatenations. This is because it optimizes the number of allocations required to create the final string as opposed to concatenations where a new string is allocated for every pair of strings you create.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
2,409
Location
Chesapeake, VA
Programming Experience
10+
permutations must be strings
Really? So mathematicians have been doing it all wrong all these centuries? What is a string, but a list of characters? Why can't it be a list of operations?
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
2,409
Location
Chesapeake, VA
Programming Experience
10+
My reading of the Countdown game on Wikipedia is that negative numbers and fractions are not allowed. I see in your code where you try to prevent fractions, but I must be missing where you are preventing negative results.

From my reading, for the game show, the contestant's objective is to come up with at least one solution. For this programming task, is it the same or should all possible solutions be listed? For solutions that mirrors of each other (e.g. 5 + 6 == 6 + 5), should both be listed, or only only of them?
 

Pavle

Well-known member
Joined
Oct 4, 2016
Messages
47
Programming Experience
1-3
My reading of the Countdown game on Wikipedia is that negative numbers and fractions are not allowed. I see in your code where you try to prevent fractions, but I must be missing where you are preventing negative results.

From my reading, for the game show, the contestant's objective is to come up with at least one solution. For this programming task, is it the same or should all possible solutions be listed? For solutions that mirrors of each other (e.g. 5 + 6 == 6 + 5), should both be listed, or only only of them?

When solution is like this 5 + 6 == 6 + 5 only one should be listed
 
Top Bottom