XKCDNPComplete/NCompleteProblem.cs at master · Kquinn/XKCDNPComplete · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using System.Collections.Generic;
using System.Linq;

namespace NP_CompleteOrder
{
    public class NCompleteProblem
    {
        public static List<int[]> Solve(SortedList<decimal, string> menu, decimal spendTotal)
        {

            var baseNArray = BaseNIntegerArray.CreateArray(menu.Keys.ToArray(), spendTotal);
            var x = baseNArray;

            List<int[]> output = new List<int[]>();
            List<int> workingSet = new List<int>();

            long iterationLimit = BaseNIntegerArray.GetLimit(baseNArray);

            while (iterationLimit >= 0)
            {

                workingSet = BaseNIntegerArray.GetPosition(baseNArray,iterationLimit).ToList();

                decimal sum = 0;

                for (int position =0; position< workingSet.Count;position++)
                {
                    decimal temp = ((decimal)workingSet[position]) * menu.Keys[position];
                    sum += temp;
                    if(sum>spendTotal)
                    {
                        position = workingSet.Count;//skip this iteration if the sum is already too high
                    }
                }

                if (sum == spendTotal || ((sum<spendTotal) && ((spendTotal - sum) % menu.Keys[0]) == 0))
                {
                    workingSet[0] += (int)((spendTotal - sum) / menu.Keys[0]);
                    bool exists = false;
                    foreach (var existingArray in output)
                    {
                        exists = Enumerable.SequenceEqual(workingSet, existingArray); //check if this solution is unique
                        if(exists)
                        {
                            break;
                        }
                    }
                    if (!exists)
                    {
                        output.Add(workingSet.ToArray());//add it to the list
                    }
                }

                workingSet.Clear();
                iterationLimit--;
            }

            return output;
        }


        public static List<int[]> OptimizedSolve(SortedList<decimal, string> menu, decimal spendTotal)
        {
            var valueArray = menu.Keys.ToArray();
            var baseNArray = BaseNIntegerArray.CreateArray(valueArray, spendTotal);
            var counterArray = ZeroArray.Create(baseNArray.Length);

            List<int[]> output = new List<int[]>();

            while (!counterArray.Equals(baseNArray))
            {

                decimal arrayProduct = ArrayMath.MultiplyArrays(counterArray,valueArray);
                if(arrayProduct>spendTotal)
                {
                    counterArray = ArrayCounter.SkipToNextValidArray(counterArray, baseNArray, valueArray, spendTotal);
                    //check if we can optimize
                }
                else
                {
                    if ((arrayProduct < spendTotal) && ((spendTotal - arrayProduct) % valueArray[0]) == 0)
                    {
                        counterArray[0] += (int)((spendTotal - arrayProduct) / valueArray[0]);
                        arrayProduct = ArrayMath.MultiplyArrays(counterArray, valueArray);
                    }

                    if (arrayProduct == spendTotal)
                    {
                        bool exists = false;
                        foreach (var existingArray in output)
                        {
                            exists = Enumerable.SequenceEqual(counterArray, existingArray); //check if this solution is unique
                            if (exists)
                            {
                                break;
                            }
                        }
                        if (!exists)
                        {
                            output.Add(counterArray.ToArray());//add it to the list
                        }
                    }
                    counterArray = ArrayCounter.Increment(counterArray, baseNArray);
                }


            }

            return output;
        }
    }
}