Sorry, I have been editing around the last cache checker for the trail using the other cartesic product checker I implemented ;-)
I have implemented the list of qualifying caches exactly this way, showing all types per line that could be used to qualify because there is no means to backcompute THE qualifying type and cache for that line.
You can see from the mathematical background that there is no way to resolve them after the algorithm found a possible solution:
First of all, a cartesic product uses a lot of space and time if you implement the mathematical theory in a straightforward manner.
I'll use the following shorthand: 1x3 -> 13
so that {1,2} X {3, 4} = {13, 14, 23, 24}
I tried at first attempt, to just do this and check time and space consumption for very small matrices. No way to even get close to finishing before the sandbox limits were reached. On the other hand the approach with fixed nested for loops did not even have the minimum of the needed flexibility.
I made the assumption that {1,2} X {3, 4} X {3, 2} can be iterated by multiplying the first two matrices and then use the result to multiply with the next. This way the number of matrices needn't be fixed to be traversed by an algorithm. After having multiplied the last result with the last remaining matrix you have all possible combinations of (in this case) cache types.
This means that {1,2} X {3, 4} X {3, 2} = {13, 14, 23, 24} X {3, 2} = {133, 132, 143, 142, 233, 232, 243, 242}
For any cartesic product with this would normally result in a very large matrix in the end.
Another thing to do the trick (reducing memory fooprint) is to translate cachetypes to single letters (not necessarily related to the cache type name at all). "Event Cache" will become "A", "Traditional Cache" will become "B" and so on. Maybe some other letters and not necessarily the same every time a tag is created. It depends on the position in the array "Configuration.cachetypes".
The next optimization is to treat the resulting matrix after the multiplication so that only relevant entries are kept. Others will be regarded "the same". Look at the combination {"Earthcache", "Traditional", "Traditional"} and {"Traditional", Earthcache", "Traditional"}
Both matrices are equal according to number of different cache types. With what I have said earlier and for example by translating "Earthcache" to "1" and "Traditional Cache" to "2" plus the assumption that the position of the letter in the "word" does not matter, following will be calculated (I also sort the letters ascending for better readability):
This means that {1,2} X {3, 4} X {3, 2} = {13, 14, 23, 24} X {3, 2} = simplify({133, 132, 143, 142, 233, 232, 243, 242}) = {13, 123, 134, 124, 23, 234, 24}
At last I only multiply until I find an N letter word in the resulting matrix, where N is "minimum different cache types". The mathematical probability is very high therefore that I do not have to multiply until the bitter end and chances are high to rate the challenge qualified before checking all combinations.
Having said that, you can see that I cannot produce a list with minimum GC Codes but can tell if the challenge was fulfilled or not. The list can be used to verify that the algorithm worked correct if any doubts arise. The positive checker itself should be proof enough that the challenge may be logged found.
Oooops, I hope I haven't bored the hell out of you, then ;-)
Greetings
Hampf
