using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using System.Data;

namespace ConsoleApp58
{
    class Program
    {
        static List<string> numbersCombinations = new List<string>();
        static List<string> operatorsCombinations = new List<string>();
        static int target = 0;
        static void Main(string[] args)
        {
            var watch = System.Diagnostics.Stopwatch.StartNew();

            List<string> nums = new List<string>() { "1", "3", "3", "7", "1", "8" };
            List<string> nums1 = new List<string>() { "0", "1", "2", "3", "4", "5" };
            List<string> operators = new List<string>() { "+", "-", "*", "/" };
            target = 999;

            for (int i = 2; i < 7; i++)
            {
                getCombinations(numbersCombinations, nums1, "", 0, i);
            }
            for (int i = 1; i < 6; i++)
            {
                getCombinations(operatorsCombinations, operators, "", 0, i);
            }

            generate(nums);

            string resenje = "";
            int minval = Int32.MaxValue;

            //resenja = resenja.Distinct().ToList();

            foreach (var x in resenja)
            {
                int k1 = int.Parse(x.Substring(x.IndexOf("=") + 1));
                if (k1 > 0 && Math.Abs(k1 - target) < minval)
                {
                    minval = Math.Abs(k1 - target);
                    resenje = x;
                }
            }

            watch.Stop();
            var elapsedMs = watch.ElapsedMilliseconds;
            Console.WriteLine(elapsedMs);
            Console.WriteLine(resenje);

            Console.ReadKey();
        }

        private static void generate(List<string> nums)
        {
            int x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0;
            StringBuilder expression = new StringBuilder();
            int s = 0, s1 = 0, s2 = 0, s3 = 0, s4 = 0;

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

                for (int j = 0; j < numbersCombinations.Count; j++)
                {
                    expression.Clear();
                    x1 = Convert.ToInt32(numbersCombinations[j].Substring(0, 1));
                    x2 = Convert.ToInt32(numbersCombinations[j].Substring(1, 1));

                    if (operator1.Length == 1)
                    {
                        if (j == 30)
                        {
                            break;
                        }

                        expression.Append(nums[x1]).Append(operator1[0]).Append(nums[x2]);

                        s = calculateExpression(operator1[0].ToString(), int.Parse(nums[x1]), int.Parse(nums[x2]));

                        if(checkExpression(expression.ToString(), s))
                        {
                            return;
                        }
                    }
                    else if (operator1.Length == 2)
                    {
                        if (j == 0)
                        {
                            j = 30;
                        }
                        else if (j == 150)
                        {
                            break;
                        }

                        x3 = Convert.ToInt32(numbersCombinations[j].Substring(2, 1));

                        expression.Append("((").Append(nums[x1]).Append(operator1[0]).Append(nums[x2]).Append(")").Append(operator1[1]).Append(nums[x3]).Append(")");

                        s = calculateExpression(operator1[1].ToString(), calculateExpression(operator1[0].ToString(), int.Parse(nums[x1]), int.Parse(nums[x2])), int.Parse(nums[x3]));

                        if (checkExpression(expression.ToString(), s))
                        {
                            return;
                        }
                    }
                    else if (operator1.Length == 3)
                    {
                        if (j == 0)
                        {
                            j = 150;
                        }
                        else if (j == 510)
                        {
                            break;
                        }

                        x3 = Convert.ToInt32(numbersCombinations[j].Substring(2, 1));

                        x4 = Convert.ToInt32(numbersCombinations[j].Substring(3, 1));

                        expression.Append("(((").Append(nums[x1]).Append(operator1[0]).Append(nums[x2])
                            .Append(")").Append(operator1[1]).Append(nums[x3]).Append(")").Append(operator1[2])
                            .Append(nums[x4]).Append(")");

                        s1 = calculateExpression(operator1[0].ToString(), int.Parse(nums[x1]), int.Parse(nums[x2]));
                        s2 = calculateExpression(operator1[1].ToString(), s1, int.Parse(nums[x3]));
                        s = calculateExpression(operator1[2].ToString(), s2, int.Parse(nums[x4]));

                        if (checkExpression(expression.ToString(), s))
                        {
                            return;
                        }
                    }
                    else if (operator1.Length == 4)
                    {
                        if (j == 0)
                        {
                            j = 510;
                        }
                        else if (j == 1230)
                        {
                            break;
                        }

                        x3 = Convert.ToInt32(numbersCombinations[j].Substring(2, 1));

                        x4 = Convert.ToInt32(numbersCombinations[j].Substring(3, 1));

                        x5 = Convert.ToInt32(numbersCombinations[j].Substring(4, 1));

                        expression.Append("((((").Append(nums[x1]).Append(operator1[0]).Append(nums[x2])
                            .Append(")").Append(operator1[1]).Append(nums[x3]).Append(")").Append(operator1[2])
                            .Append(nums[x4]).Append(")").Append(operator1[3]).Append(nums[x5]).Append(")");

                        s1 = calculateExpression(operator1[0].ToString(), int.Parse(nums[x1]), int.Parse(nums[x2]));
                        s2 = calculateExpression(operator1[1].ToString(), s1, int.Parse(nums[x3]));
                        s3 = calculateExpression(operator1[2].ToString(), s2, int.Parse(nums[x4]));
                        s = calculateExpression(operator1[3].ToString(), s3, int.Parse(nums[x5]));

                        if (checkExpression(expression.ToString(), s))
                        {
                            return;
                        }
                    }
                    else if (operator1.Length == 5)
                    {
                        if (j == 0)
                        {
                            j = 1230;
                        }

                        x3 = Convert.ToInt32(numbersCombinations[j].Substring(2, 1));

                        x4 = Convert.ToInt32(numbersCombinations[j].Substring(3, 1));

                        x5 = Convert.ToInt32(numbersCombinations[j].Substring(4, 1));

                        x6 = Convert.ToInt32(numbersCombinations[j].Substring(5, 1));

                        expression.Append("(((((").Append(nums[x1]).Append(operator1[0]).Append(nums[x2])
                            .Append(")").Append(operator1[1]).Append(nums[x3]).Append(")").Append(operator1[2])
                            .Append(nums[x4]).Append(")").Append(operator1[3]).Append(nums[x5]).Append(")").Append(operator1[4]).Append(nums[x6]).Append(")");

                        s1 = calculateExpression(operator1[0].ToString(), int.Parse(nums[x1]), int.Parse(nums[x2]));
                        s2 = calculateExpression(operator1[1].ToString(), s1, int.Parse(nums[x3]));
                        s3 = calculateExpression(operator1[2].ToString(), s2, int.Parse(nums[x4]));
                        s4 = calculateExpression(operator1[3].ToString(), s3, int.Parse(nums[x5]));
                        s = calculateExpression(operator1[4].ToString(), s4, int.Parse(nums[x6]));

                        if (checkExpression(expression.ToString(), s))
                        {
                            return;
                        }
                    }
                }
            }
        }
        static List<string> resenja = new List<string>();
        private static bool checkExpression(string expression, int value)
        {
            if (value > 0)
            {
                if (value == target)
                {
                    resenja.Add(expression + "=" + value.ToString());

                    return true;
                }
                else if (value >= target - 100 && value <= target + 100)
                {
                    if (!resenja.Any(s => (expression + "=" + value.ToString()).Contains(s)))
                    {
                        resenja.Add(expression + "=" + value.ToString());
                    }

                    return false;
                }
            }

            return false;
        }
        private static int calculateExpression(string operator1, int num1, int num2)
        {
            switch (operator1)
            {
                case "+":
                    return num1 + num2;
                case "-":
                    return num1 - num2;
                case "*":
                    return num1 * num2;
                case "/":
                    return num1 / num2;
            }

            return 0;
        }

        public static void getCombinations(List<string> combinations, List<string> input, String comb, int pos, int length)
        {
            if (pos < length)
            {
                foreach (string ch in input)
                {
                    getCombinations(combinations, input, comb + ch, pos + 1, length);
                }
            }
            else
            {
                if (!comb.Contains("+") && !comb.Contains("-") && !comb.Contains("*") && !comb.Contains("/"))
                {
                    if (CheckForDupicate(comb))
                    {
                        combinations.Add(comb);
                    }
                }
                else
                {
                    combinations.Add(comb);
                }
            }
        }
        public static bool CheckForDupicate(string input)
        {
            return input.Distinct().Count() == input.Length;
        }
    }
}