Re: GC87FM1 Countries, Types, 4x4 Matrix

Can someone make a checker for this please? I suspect a new checker needs to be written.

Challenge:
Fill your 4x4 matrix with the following conditions:
You can use at most 3 finds per country
Finds used from the same country has to be different types

For example you can use a traditional, a mystery and a multi from the same country, but you can't use 2 traditionals from the same country.


I've been thinking about how to write the checker to make it go faster, and I think I have a good idea on how to do it:
Start with the countries, where the geocacher has found the least number of caches.
If there is a country, where the geocacher has only found 1 cache, then that cache can be safely included. Or if the geocacher has found less than 4 types in a country, and for one of the types has found only 1 cache, then that cache can also be safely included.
Whenever a cache is included, the checker can stop looking for the D/T combination of that cache.

The above written a little differently, that is more difficult to understand, but I think better when programming it:
If there is a country, where the geocacher has only found 1 missing D/T combination, then that cache can be safely included. Or if the geocacher has found less than 4 types with missing D/T combinations in a country, and for one of the types has found only 1 missing D/T combination, then that cache can also be safely included.

I used this method to manually figure out that I am qualified myself.

I hope this all makes sense. Otherwise ask :)

In your example if your 'least' found country, has 5 finds of all different type for example, then the checker would select the first three and then move onto the next country.... and so on, but, if the last 2 for that first country had some rare D/T that you didnt find anywhere else, they would not be used and the checker would tell you that you failed.

Therefore, this checker would require recursion to address that problem, where it added a single hide with missing D/T then called itself again. Recursion can make this very slow, especially for a cacher with many finds in many countries

I am happy to give this a go

I know. I just meant it as a way to start that I think should make it a lot faster for most persons.
When it can't find anymore caches to safely add, then it has to try all the possibilities.

Sounds good :)



Edited 1 time(s). Last edit at 05/07/2019 10:12PM by Sirusc. (view changes)

I have created the script, and shaved a lot of time off it.....
- area : valid values are 'country', 'region', 'county'. Defaults to no area restriction
- maxFindsPerArea : the maximum numbers of finds that can count from the area level specified
- maxAreas : the maximum numbers of areas that can be used
- maxTypesPerArea : the maximum number of types that can be used in each area
- maxFindsPerTypePerArea : maximum number of finds per type per area
- loops : number of required DT loops, defaults to 1
- minD : the mininum D value, defaults to 1.0
- maxD : the mininum D value, defaults to 5.0
- minT : the mininum T value, defaults to 1.0
- maxT : the mininum T value, defaults to 5.0

but.... it says you dont qualify. Obviously, this could be a bug on my side..... in fact it is likely.... but I dont know.

You pass if I limit the restriction to max 2 finds per type per country, and the script takes 0.5 seconds.... but if I set it max 1 find per type per country... the script takes 15 seconds and says you fail.

Here is the output.... can you check it against your manual list please (and/or provide me with your manual list to help me debug the script).

Sirusc qualifies for this challenge

GC5VV9P D2.0 T2.0, Traditional Cache, Albania

GC5DFKG D3.0 T3.5, Traditional Cache, Andorra

GC5B2GK D3.5 T3.0, Traditional Cache, Andorra

GC2TTWZ D2.5 T2.5, Traditional Cache, Anguilla

GC4BP4P D2.5 T3.0, Traditional Cache, Bermuda

GCMDYY D2.0 T4.0, Traditional Cache, Bonaire, Sint Eustatius and Saba

GC1AABK D2.5 T3.5, Traditional Cache, Bonaire, Sint Eustatius and Saba

GC5PN1W D2.0 T1.5, Traditional Cache, British Virgin Islands

GC7FRQW D3.5 T1.0, Earthcache, Cambodia

GC6NTR1 D1.0 T2.0, Traditional Cache, Cambodia

GC20DQ1 D1.0 T4.0, Earthcache, Croatia

GC1TDDE D1.5 T4.0, Traditional Cache, Croatia

GC4JH7H D4.0 T3.0, Multi-cache, Denmark

GC64DXE D4.0 T3.5, Traditional Cache, Denmark

GC24839 D4.0 T4.0, Traditional Cache, Denmark

GC6ZZC1 D3.0 T3.0, Traditional Cache, Estonia

GC4FK2T D3.0 T2.0, Unknown Cache, Faroe Islands

GC5K1HX D4.0 T1.0, Unknown Cache, Finland

GC6CEM5 D1.0 T3.0, Traditional Cache, France

GC71QVQ D1.5 T3.0, Traditional Cache, France

GC1C0B7 D1.0 T2.5, Earthcache, Gibraltar

GC1DXR1 D1.5 T2.5, Traditional Cache, Gibraltar

GCJR1J D2.0 T3.0, Traditional Cache, Gibraltar

GC65BNK D2.5 T1.5, Earthcache, India

GC6826X D3.0 T1.5, Traditional Cache, Laos

GC6EZ7Q D2.0 T3.5, Traditional Cache, Lithuania

GC4F36Y D1.5 T1.5, Traditional Cache, Macedonia

GC41Q9N D2.5 T4.0, Traditional Cache, Malta

GC239QP D3.0 T4.0, Traditional Cache, Malta

GC6KA6F D4.0 T2.0, Unknown Cache, Monaco

GC56XK0 D1.0 T1.0, Traditional Cache, Netherlands

GC5439T D1.5 T1.0, Traditional Cache, Netherlands

GC7J2FT D3.5 T2.0, Traditional Cache, Saint Barthélemy

GC4EMFG D3.5 T3.5, Traditional Cache, Saint Barthélemy

GC7DXX7 D2.0 T1.0, Traditional Cache, Saint Martin

GC56NVB D3.0 T2.5, Earthcache, San Marino

GC6V3CW D4.0 T2.5, Earthcache, San Marino

GC7QM46 D4.0 T1.5, Multi-cache, Singapore

GC1KZE9 D3.5 T2.5, Multi-cache, Slovakia

GC7J3D1 D1.0 T3.5, Traditional Cache, Sweden

GC1X133 D3.5 T4.0, Traditional Cache, Sweden

GC120HB D2.0 T2.5, Traditional Cache, Switzerland

GC2X725 D1.0 T1.5, Earthcache, Timor-Leste

GC6AZ67 D1.5 T3.5, Traditional Cache, Timor-Leste

GC7DCW5 D3.5 T1.5, Earthcache, Tunisia

GC2KH19 D1.5 T2.0, Traditional Cache, US Virgin Islands

GC71Q8V D2.5 T1.0, Earthcache, Vatican City State

GC5BVQ7 D2.5 T2.0, Unknown Cache, Vatican City State

GC2J0F7 D3.0 T1.0, Unknown Cache, Vatican City State

Here's my list of how I qualify written both by D/T and by country.
There are many country types, where it needs to choose the correct one. Manually I postponed these decisions until all but 1 of the possibilities was filled out elsewhere, and then used the only remaining possibility. This brought me to the situation where everything except 1/3.5, 3.5/4, 4/3, 4/3.5 and 4/4 was filled out, and I was missing both Sweden and Denmark (the two countries I have by far the most finds in). The rest was easy to fill out with traditional and mystery from Sweden and traditional, mystery and multi from Denmark.

By D/T:
1/1 Virtual Saint Martin GCHH2Q
1/1.5 Earth Timor-Leste GC2X725
1/2 Traditional Cambodia GC6NTR1
1/2.5 Earth Gibraltar GC1C0B7
1/3 Earth United Kingdom GCNTAB
1/3.5 Mystery Sweden GC67VPN
1/4 Earth Croatia GC20DQ1
1.5/1 Traditional Netherlands GC5439T
1.5/1.5 Traditional Liechtenstein GC1YTTH
1.5/2 Traditional US Virgin Islands GC2KH19
1.5/2.5 Earth Laos GC4WCTZ
1.5/3 Traditional Morocco GC4R7YP
1.5/3.5 Traditional Timor-Leste GC6AZ67
1.5/4 Earth Croatia GC1TDDE
2/1 Traditional Saint Martin GC7DXX7
2/1.5 Traditional Norway GC5DMA3
2/2 Traditional Albania GC5VV9P
2/2.5 Traditional Switzerland GC120HB
2/3 Traditional Luxembourg GC5PFAC
2/3.5 Traditional Lithuania GC6EZ7Q
2/4 Traditional Bulgaria GC3W4ZP
2.5/1 Earth Vatican City State GC71Q8V
2.5/1.5 Earth India GC65BNK
2.5/2 Tradional Guadeloupe GC70JW1
2.5/2.5 Traditional Anguilla GC2TTWZ
2.5/3 Traditional Estonia GC296Z9
2.5/3.5 Traditional Bonaire, Sint Eustatius and Saba GC1AABK
2.5/4 Traditional Malta GC41Q9N
3/1 Traditional Monaco GC1XQQ2
3/1.5 Traditional Laos GC6826X
3/2 Mystery Faroe Islands GC4FK2T
3/2.5 Traditional Greece GC53XMY
3/3 Traditional France GC71QVT
3/3.5 Mystery Hungary GC2H19N
3/4 Traditional Bermuda GC4DG8Y
3.5/1 Earth Cambodia GC7FRQW
3.5/1.5 Earth Tunisia GC7DCW5
3.5/2 Mystery Vatican City State GC3WB2W
3.5/2.5 Multi Slovakia GC1KZE9
3.5/3 Traditional Andorra GC5B2GK
3.5/3.5 Traditional Saint Barthelemy GC4EMFG
3.5/4 Traditional Sweden GC1X133
4/1 Mystery Finland GC5K1HX
4/1.5 Multi Singapore GC7QM46
4/2 Mystery Monaco GC6KA6F
4/2.5 Earth San Marino GC6V3CW
4/3 Multi Denmark GC4JH7H
4/3.5 Traditional Denmark GC64DXE
4/4 Mystery Denmark GC38D6N


By Country:
Albania
2/2 Traditional GC5VV9P

Andorra
3.5/3 Traditional GC5B2GK

Anguilla
2.5/2.5 Traditional GC2TTWZ

Bermuda
3/4 Traditional GC4DG8Y

Bonaire, Sint Eustatius and Saba
2.5/3.5 Traditional GC1AABK

Bulgaria
2/4 Traditional GC3W4ZP

Cambodia
1/2 Traditional GC6NTR1
3.5/1 Earth GC7FRQW

Croatia
1/4 Earth GC20DQ1
1.5/4 Traditional GC1TDDE

Denmark
4/3 Multi GC4JH7H
4/3.5 Traditional GC64DXE
4/4 Mystery GC38D6N

Estonia
2.5/3 Traditional GC296Z9

Faroe Islands
3/2 Mystery GC4FK2T

Finland
4/1 Mystery GC5K1HX

France
3/3 Traditional GC71QVT

Gibraltar
1/2.5 Earth GC1C0B7

Greece
3/2.5 Traditional GC53XMY

Guadeloupe
2.5/2 Traditional GC70JW1

Hungary
3/3.5 Mystery GC2H19N

India
2.5/1.5 Earth GC65BNK

Laos
1.5/2.5 Earth GC4WCTZ
3/1.5 Traditional GC6826X

Liechtenstein
1.5/1.5 Traditional GC1YTTH

Lithuania
2/3.5 Traditional GC6EZ7Q

Luxembourg
2/3 Traditional GC5PFAC

Malta
2.5/4 Traditional GC41Q9N

Monaco
3/1 Traditional GC1XQQ2
4/2 Mystery GC6KA6F

Morocco
1.5/3 Traditional GC4R7YP

Netherlands
1.5/1 Traditional GC5439T

Norway
2/1.5 Traditional GC5DMA3

Saint Barthelemy
3.5/3.5 Traditional GC4EMFG

Saint Martin
1/1 Virtual GCHH2Q
2/1 Traditional GC7DXX7

San Marino
4/2.5 Earth GC6V3CW

Singapore
4/1.5 Multi GC7QM46

Slovakia
3.5/2.5 Multi GC1KZE9

Sweden
1/3.5 Mystery GC67VPN
3.5/4 Traditional GC1X133

Switzerland
2/2.5 Traditional GC120HB

Timor-Leste
1/1.5 Earth GC2X725
1.5/3.5 Traditional GC6AZ67

Tunisia
3.5/1.5 Earth GC7DCW5

United Kingdom
1/3 Earth GCNTAB

US Virgin Islands
1.5/2 Traditional GC2KH19

Vatican City State
2.5/1 Earth GC71Q8V
3.5/2 Mystery GC3WB2W


It's a little difficult to compare your list with my list, because they're searching for two different things, but I've tried and found 4 main differences:
For Bermuda traditional I used 3/4 and your list used 2.5/3
For Estonia traditional I used 2.5/3 and your list used 3/3
For France traditional I used 3/3, and your list used 2 others
For Malta traditional I used 2.5/4, and your list used 2 others

I hope this can help finding the problem.

I found my bug... stupid really! ... fixed that.

But... now nothing I do will make the script run fast enough to complete within the 60 seconds... even for you with a 'relatively' small total of finds (though you have a ton of countries).

So, its time to abandon the 'area' first, 'type' second, 'DT' third model I had tried.

I think an efficient algo *might* be made that does DT first, selecting the rarest first, not sure.

I dont have any more time to spend on this, at least in the next 3 weeks (I am going to the US to finally finish my Jasmer!)

I'm very surprised by this, because manually I was able to deterministically without guessing reach 5 missing DT-combinations. And the last 5 shouldn't take long time to determine a possibility for.
Can someone else give this a try while GreyHams is away? Otherwise I'll wait. Have fun with your Jasmer GreyHams :)

I don't know how exactly you've tried programming it, but I've tried writing some pseudocode for how I would program what I did manually:

Initialize a result matrix
Initialize a cache list for possible caches that hasn't been added yet
Start loop
____Take the country with the fewest number of finds
____For each cache in that country with a missing DT-combination, add it to the cache list if a similar cache hasn't
____already been added to the list (similar meaning same country, type and DT)
____Call check_country with that country
Loop until there's no more countries
Start guessing and backtracking with the remaining possibilities. Start with the country types with the fewest possibilities and/or the DT-combinations with the fewest possibilities
Before each guess check if there's any country types or DT-combinations with only one possibility that can be safely added

check_country(country)
If the country has less than 4 types in the cache list:
____For the types, where the country has exactly one cache in the cache list:
________Add the cache to the result matrix
________Delete all caches in the cache list with that DT-combination
________For each country with a deleted cache call check_country with that country



Edited 1 time(s). Last edit at 05/09/2019 02:17PM by Sirusc. (view changes)

In order to cleanup the request:
Is this item still live or can it be moved to ARCHIVE Checker requests

It's still live.

I would very much like someone to create the checker.

I tried my luck and I think it works quite ok for now. Here's a temporary checker:

https://project-gc.com/Challenges/GC87FM1/45629

I'll clean up the output later, that shouldn't take too long. I'll see whether I can also display the best progress for users who haven't completed the challenge yet. Got an idea for that, think shouldn't be too hard either.

Now for the approach, if you're interested, I took GreyHams thought (well, I did it like this anyway to then read he had that idea as well):

> I think an efficient algo *might* be made that does DT first, selecting the rarest first, not sure.

My thought process was that this has the advantage that you can instantly recognize failed attempts when for some DT combination there are no fitting caches. This presumably reduces the number of backtracking steps made. In fact, there are only 25 backtracking steps for your account. If you were looping over countries, and you have the whole matrix completed in your home country, your home country will be decided last but you would never opt out of the recursion early since there will never be a cell for which there is no possible cache left.

That being said, my script is still quite slow for cachers who have found caches in numerous countries but don't quite fulfill the challenge. Take user predator1337 for example. For him the script runs for ~43 seconds and requires 275610 backtracks to then find he does not qualify. I'll see whether I can find a way to speed this up a bit.

edit: Your preprocessing where a country has less than four DT/type combinations would still speed things up of course, I might implement that later and see if it brings any speedup.



Edited 1 time(s). Last edit at 10/10/2019 06:34PM by PattuX. (view changes)

Great :)
Thanks for your work so far :)
(and also thanks to GreyHams for trying)

I'm not sure what "GreyHams thought" is, so I'm not sure which way you're doing it.

My main point is that if you've found less than 4 types with missing D/T combinations in a country, and at least 1 of those types only has 1 missing D/T combination, then you know for sure you can add that cache without needing any backtracking. You can start by adding in this way untill that's not possible anymore, and then start guessing and backtracking after that. When doing it manually I was able to add 44 out of the 49 caches for myself in this way, so I only had to do backtracking with the last 5 caches.
In my mind backtracking is the most time consuming, so you want to minimize that as much as possible. So if you can start by adding a lot of caches without needing any backtracking this is a good thing.
But of course I may be wrong. I don't know what information is available in a fast way, and the way you loop over caches makes this go slow in some way.

I ran the checker for the top 90 danes with most countries, and it didn't finish for mjolner and hathneit. Telling you, because the information may be able to help you make it faster.

I was refering to the DT first search, which is what GreyHams suggested and which I did now.

I have a WIP version where I do some preprocessing. On predator is does reduce the time to 15s and the backtracking steps to 31924.

However I checked for your account and it seems there might be something wrong still. I filled the following DT ratings only by doing deductions as you described:

4.01.5 - Multi-cache - Singapore - GC7QM46
2.01.5 - Unknown Cache - Guadeloupe - GC4MKDA
1.51.5 - Traditional Cache - Liechtenstein - GC1YTTH
1.01.0 - Virtual Cache - United States - GC73A6
2.02.0 - Earthcache - Estonia - GC68169
1.52.0 - Unknown Cache - San Marino - GC6XZJ1
1.01.5 - Unknown Cache - Ireland - GCX7VK
4.01.0 - Unknown Cache - Finland - GC5K1HX
3.02.0 - Wherigo Cache - Bulgaria - GC40GY9
2.01.0 - Traditional Cache - Saint Martin - GC7DXX7
2.51.0 - Earthcache - Russia - GC2XX9B
3.51.0 - Earthcache - Cambodia - GC7FRQW
1.51.0 - Unknown Cache - Italy - GC3ETM0
2.51.5 - Multi-cache - Malaysia - GC6Z48T
1.53.5 - Earthcache - Bonaire, Sint Eustatius and Saba - GC10RX5
2.53.0 - Multi-cache - Cyprus - GC5MGRX
2.52.0 - Wherigo Cache - Faroe Islands - GC4VV8V
2.52.5 - Traditional Cache - Anguilla - GC2TTWZ

How do you get to 44? Is it somewhat similar to this? If so, how do you continue?

Nvm, think I found my mistake.



Edited 1 time(s). Last edit at 10/10/2019 10:27PM by PattuX. (view changes)

Alright, quick update.

So first of all there are two possibilities with the preprocessing here:

1. It's done exhaustively once before the backtracking stuff, like you did for your account. Now this works well for your account in particular since you have many countries with few finds. However for other users, such as the two you listed, it doesn't help that much and it still times out since after ~10 deductions there are only countries with 4 different types and/or only country-type combinations with two or more DT-ratings left, leaving no further deductions.

2. It's done exaustively once before the guessing and again (exhaustively) every time a cache is added via guessing. This makes it significantly faster for users fulfilling the challenge like the two you listed since there are far less choices on the way towards the solution. However, the issue here is that for a user who does not fulfill the challenge by a small margin (i.e. when simple heuristics can't tell that the user can't fulfill the challenge) the search tree is necessarily traversed completely (i.e. every possible choice is tried) and for every step this preprocessing is done, i.e. tens of thousands of times, which consumes lots of time. Arguably the search tree gets slightly smaller by doing the deductions but with quite some users I tried this knocks them over the timeout barrier.

I'll think about it a bit more and see whether I can get the second option to work for negative results at a speed that is at least as good as the script w/o preprocessing. Sounds like it should be possible...

edit: Oh, and of course, if you want to try it for yourself: https://project-gc.com/Challenges//45632
In the debug output tab there's also a list of how many times each country, and how many times each combination of country/type is included in the final matrix. This should make it easier to check if a result is correct, since you only need to check if all numbers are at most 3 or 1 respectively. I haven't found any wrong output yet.



Edited 3 time(s). Last edit at 10/11/2019 03:03AM by PattuX. (view changes)

Ok, here we go again!

Here's the newest iteration of the checker:

https://project-gc.com/Challenges//45690

I haven't been able to do many significant improvements, so in the end what I did is take the method that works really well for users fulfilling the challenge (method 2) and let that run for a bit (about 5 seconds). If by then no solution was found the script switches back to method 1. The main point there is to make sure that if no solution was found in by method 2, then method 1 tries to confirm there is indeed no solution. Additionally, I try to compute the best possible matrix for users not fulfilling the challenge, however as this is quite hard computationally that attempted solution might be a bit off from the actual best possible matrix, but I suppose most of the time it should have either be the actual best matrix or at least have just or one filled cell less.

So far for all my tests this terminated within the time bounds, but I'm pretty sure there are still a few users not fulfilling the challenge for which the script times out. However I'm quite confident that if a user filfills the challenge, the solution will be found.

So again I'd like to ask you now to test this on several people and report back on the results. In particular:
- Are there timeouts?
- Are there any users fulfilling the challenge for which the script takes longer than 5 seconds?
- (Maybe a bit hard to tell) Are there users not fulfilling the challenge for which the suggested best possible matrix is far off from what seems possible?

and of course also leave any other comments you have.

For the output I'll probably do an actual matrix at some point, should make it look cleaner.

PS: Also I might try an offline solution at some point with some external tools to see if there's any improvement to be made or whether it's just in the nature of the problem that it takes a lot of time to solve.

Hi, really happy you got this working... I had a red hot go at it but ran into time issues.

I failed in 0.066 seconds, which is really good as I have a lot of counties (300+) but only 4600 finds. DT first is clearly more efficient (wish I had tried it first, so credit to your natural thinking)

I've tested top 200 danes with the most countries today (the last having 22 countries).

I only tested for the 2 first points since I didn't know how to test for the 3rd.

There was 26 qualified geocachers. For all of them the solution was found in less than a second (the slowest being 0.8).

There was 4 timeouts:
hathneit (19 * 4x4 matrix, 36 countries)
SP-DK (80 * 4x4 matrix, 25 countries)
DK_Titan (9 * 4x4 matrix, 25 countries)
L8hougs (11 * 4x4 matrix, 22 countries)

I don't know if it helps, but what about:
- Using method 2
- Every time a guess has to be made, do it by rarest D/T. If you've tried guessing all of the possibilities for that D/T-combination and failed every time you know no solution is possible.
- When filling out after a guess, do some memorization, so you can easily fill out in the same way after a different guess of the same D/T.



Edited 2 time(s). Last edit at 10/15/2019 08:44PM by Sirusc. (view changes)

Thanks for the feedback.

Quote

I only tested for the 2 first points since I didn't know how to test for the 3rd.

Yeah, the third is hard to tell. I was just thinking about cases where you'd think a user would be really close to fulfilling the challenge, but the srcipt somehow tells you that in can at best fill 30 cells or so. Maybe when I get it to work better with some external stuff I can find out the actual max number of possible cells for some users and compare that to what the script gives.

Quote

There was 4 timeouts

Nice to have some cases for that. I'll have a look at these in particular. I highly suspect they do not fulfill the challenge since the script that finds the solution in under one second (the first script called "wip") couldn't find a solution for these cachers in a full minute.

Quote

There was 26 qualified geocachers. For all of them the solution was found in less than a second (the slowest being 0.8).

That sounds good. If the other four indeed don't qualify I'm very confident the script can find any solution in under five seconds. However I still wouldn't be comfortable telling the user he definetely doesn't fulfill the challenge without evidence, so not sure what to do if I can't improve on the timeouts.

Quote

I don't know if it helps, but what about:
- Using method 2
- Every time a guess has to be made, do it by rarest D/T. If you've tried guessing all of the possibilities for that D/T-combination and failed every time you know no solution is possible.

This is exactly what the script does for the first five seconds. After that it switches to method 1 (since that's faster for the non-fulfilling users) but still always makes a choice for the least common D/T-rating.

Quote

When filling out after a guess, do some memorization, so you can easily fill out in the same way after a different guess of the same D/T.

This would be the key to making this faster I guess. However it's not that simple since you can't "fill out in the same way" after different guesses. If for example after the first guess for a 1/3 (say, that's a Trad in Germany) you proceed to choose a Traditional in Denmark for 1/4 and that turns out fail, you proceed to the next guess. If your next guess for a 1/3 in a Tradi in Denmark then you can't proceed in the same way as before. However now you could choose a Trad in Germany for any other rating which you couldn't do in the previous attempt. There surely is a way to memorize stuff but it requires lots of work and thinking, not only to come up and implement such memorization but also make sure it's correct and implement it in such a way that the memorization itself does not take more time (and also space) than it saves.

Now the external stuff I want to use (SAT-solving and/or constraint programming) use generic algorithms to do exactly that. After encountering a failed attempt they don't simply backtrack and try the next thing but instead try to find out what was the deeper cause of the error and add new restrictions that recognize later attempts that would run into the same issue way earlier. I'd hope that makes it a lot faster. If it does, I'm still not sure how to bring this into PGC tho...

I have written a script that makes it possible to feed some data into a SAT solver (not that important how it works, just know that it's a program that can solve the task) and let that do the work. It 's quite a bit faster: For users where the script would take around 20 seconds to find that the user does not fulfill the challenge, the SAT solver can figure that out in about 0.5s.

Now the bad part: For three out of the four users that you found timing out it still took very long. All of them don't fulfill the challenge.
For L8hougs the SAT solver was done in 5 seconds.
For hathneit it took 15 miuntes.
For SP-DK... Well, I stopped after 4.5 hours. For DK_Titan I let it run for 30 minutes, no result, but I expect that to take longer than SP-DK anyway.

I also tried a different method, using a constraint solver, but that was even far slower than the original PGC script.

I can try fiddling with the SAT solver setting, that can improve the speed, but I don't expect that that would have too much impact. Other than that I don't really have any idea how to make it run faster now. It's just a really hard problem computationally... I still don't think either of these qualify, but of course we can't be sure.

Is this thread still active ??

I think this is impossible to compute in general within a minute (feels NP-complete).

But maybe there's another way of doing this that works well for practical cases as users have a very similar pattern of finds (most in home country, some in neighboring states, generally more traditionals/mulits/mysteries than the rest etc). I can't think of one, maybe someone else can.

I don't know whether a challenge would be published if there are a handful of users for which the checker doesn't give a result, and if so, how the three users for which we still don't know whether they qualify would be handled.

If somehow the current state of the checker is good enough for publishing I can tidy the output as well.