Need a checker for GC5KMHV "GC-Code Challenge"

Question

To find caches with all 31 possible combinations of letters and numbers in the GC-codes, but each letter/number only once. Required letters are A B C D E F G H J K M N P Q R T V W X Y Z, the letters I L O S U are not used. And the numbers 1 2 3 4 5 6 7 8 9 0

And 2 of the caches have to be found the same day

Answer 1

I think that it's not possible to do checker for this challenge. There are billions of billions of combinations and the checker cannot check it all. Otherwise we need a lot of big tables, but the checker has limit of memory. I've tried to write the checker, but after 20000000 tries they cannot find the solution.

Comments

I think the description given in the question and that on the cache page don't actually match. The cache page says (in german):
- Lists in your log the caches with GC Code, Name, Date and Fund Owner, whose GC codes together all 31 possible characters exactly once included! No number or letter (except GC at the start) must be doubled!

- The list of specified caches must contain at least two caches that were found on the same day!

So find a set of n (e.g. 7) caches, where after stripping off the GC the remaining letters/numbers are each only used once.

It should be possible to write a checker for this, first produce a list of valid caches (e.g no duplicate letters in them) and then try to find a set of caches from this which meet the criteria (backtracking when you can't add any other caches).

---

Hi mole125 (complimenti for your 'easy tagging checker')
I've tried exactly the approach that you have described, but the main problem is, that there are too many combination of 7 caches taken from 1000 founds. (they are about 2x10^17). I've tried to index the caches in some way to lower the number of tries, but in 20M tries I've not found the solution. The speed of the script is about 1M tries per second, so 20M are already close to timeout. Hopelessly the script is limited by the memory usage too, so there is no possibility to create huge indexes to lower the number of tries needed.

---

There is another complication. GC codes can be GC and 2-5 charachters se https://support.groundspeak.com/index.php?pg=kb.page&id=221
That will result in combinations with more then 7 caches that are possible

One optimisation that might help is to order the the chars in the gc code and remove duplicates.
If you only consider the case with 7 caches the caches can be grouped in two groups 5 longs codes and 4 long codes in the combination 3*5+4*4
5 char codes all begins with 1-5. that will create two new possible optimisations
The first one is to group 5 char codes in five groups and only take one from each group in a possible solution.
The second one is that the 4*4 group can only contain 2 of the number 1-5

That will reduce the number of combinations alot.  the max start char for 5 code has to be detected at runtime because there will not be long before they can start with 6

Solutions with 3 and 2 char codes will require additional code.
3+2 will be a 5 code
2+2 a 4 code

and 5*5 +3*2  and 5*5+2*3 is possible.
But first try to create it for 5*3+4*4 to check if it is fast enough

---

Another optimisation to do would be have a list of candidates for each letter in the alphabet, then sort this list by number of potential candidates and then work through from the smallest set first. E.g if there is only 1 cache with the letter Z and 2 with P then select the Z cache, then select one from the P list (assuming you haven't already used P) and so on. This approach significantly reduces wasted backtracking as it removes the hard ones first.

---

ad Mole125:
I've tried it making the checker exactly as you have suggested. This was my original idea.
However - on my 800 finds, there are about 500 codes without duplicates. Every letter is present in about 70 codes (the number 4 is in 200 caches = the codes beginning with 4 [:)] ).
So, we must choose 7 caches from sets of in media 80 possibilities. This is about 2x10^13 combinations. Respect of 1.5x10^15 without the optimization. Yes, we have lower the number of possibilities by about 100, but this is not enough. The limit is about 10^8, so we need to lower it by 1000000.
However, for someone with 5k finds like Target. (3500 without doubles), the sets for every character have about 450 with peak of 1200 for '4' and '3', so the number of combinations rises to 4e18. If we cannot lower it by factor of at least 1e10, this is no way.

---

Can you enable the script so I can see it. It might help to get an idea for optimisation when reading the code.
If you have create a tag for the challenge dont enable that tag but create one without gc code if a config is nessecery so pgc dont try to run it in the background

---

I've add some comment and enable the script and null tag.
Enjoy it [:)]
http://project-gc.com/Challenges//15648

I think that your approach can work, but I'm not able to estimate the number of combination. Try it

Answer 2

I've did it!

the checker is here: http://project-gc.com/Challenges/GC5KMHV/15632

It was hard to make, but I've found the algorithm that can do it in real time. However, sometimes the script cannot try all combinations, so goes to timeout and report "false negative - please check it manually".

Comments

With ~20k founds I get some timeout error here.

---

I've modified the checker to improve the detect of timeout, now, either with 20k founds (complimenti to Bergfex for his founds) reports the timeout finishing in real time.
Hopelessly, the task to find the correct chain is very hard for the checker, with many finds the number of combinations is astronomical.