times out on user Xnard. She has fewer finds than folks it handles. I appreciate the computational difficulty of fitting 81 slots against the total set of attributes and iterating to find a solution that works. Can the script be sped up? I didn't dig through the code but discarding finds with no attributes should be done although I suspect dealing with those is not where the CP cycles go.
First of all, more finds do not make this problem harder necessarily. As finding one solution is enough, someone with many finds may qualify in millions of different ways and just randomly picking some cache for any cell may be good enough to arrive at a solution. Xnard seems to be in a spot where determining whether there is a solution is really hard since she does not have few enough finds to quickly determine she has no way to find a solution but also not enough finds to find a solution by just picking more or less arbitrary caches for the cells. If there are solutions there are probably very few and thus traversing all possible combinations towards a solution is necessary.
This problem is indeed very hard computationally, so I think in the worst case you'll always finds someone for whome it may take hours, if not years, to determine whether a solution exists. But my gut feeling says that anyone who timeouts probably does not qualify. Do you have any case where someone has a full DT matrix but does not qualify for the challenge? All users I've tried either are missing a DT cell (which makes the task trivial) or qualify. Proving there is no solution seems really hard in general, so I'm curious if this ever happens.
That being said, I think there is a tiny bit one could do for this challenge in particular, but nothing that would change the complexity significantly. Just stuff like if an attribute only occurs for one particular DT rating, then it is safe to assume that attribute for that DT cell. But I think this does not happen too often.
What might help is to abstract this even further and let some solver run this. I've done something similar for another checker and it sped up the process by a good amount (up to 100x) but it still didn't give any result for some users. Also this is not really feasible to port to a checker script. But I can try something similar for this challenge in the next couple of days and see whether I can get a result for Xnard to see how tractable this problem is.
Pretty much what I assumed was going on. She has a completed DT grid but not enough total finds to make hitting upon a solution likely. She told me she did it by hand but it took her several days to get a solution. My thoughts on it had been to sort the low number of finds DT cells and try to get them settled down and then continue with those with more finds leaving things like 1.5/1.5 for the end where there are enough finds to offer a wide set of choices. I don't know that the current algorithm operates along those lines.
I wanted to look at the code in detail a bit, but it is kinda hard to make sense of it since the debug output does not work at the places where I'm not sure what it does. But I think it already does always try the DT combination with the least possible attributes first.
I have written a small script that transforms the problem into another format for a given user, which I then checked locally on my PC for Xnard. It took only less than a second to find a solution. So I suppose this is actually quite tractable but again, I don't think porting this to a challenge checker script would be easy.
Here's the solution I found:
1.01.0 NOT Picnic tables nearby GC7JYDB
1.01.5 NOT Parking available GC4RDVF
1.02.0 NOT Night Cache GC6AQPP
1.02.5 NOT Horses GC6M5BX
1.03.0 Cliff / falling rocks GC1PQV2
1.03.5 Difficult climbing GC5MWKN
1.04.0 NOT Takes less than an hour GCZ9C8
1.04.5 Long Hike (+10km) GC7KH0E
1.05.0 Dogs GC3K2CX
1.51.0 NOT Stealth required GC5AFHF
1.51.5 NOT Available during winter GC6VAQJ
1.52.0 Seasonal Access GC576G7
1.52.5 Boat GC4GQ6F
1.53.0 Horses GCZVPW
1.53.5 NOT Tree Climbing GC5XVJV
1.54.0 NOT Recommended at night GC4VKT0
1.54.5 NOT Public restrooms nearby GC6117E
1.55.0 NOT Campfires GC5XVP6
2.01.0 NOT Seasonal Access GC7X49Z
2.01.5 NOT Fuel Nearby GC6BJBK
2.02.0 NOT Abandoned Structure GC6XBJZ
2.02.5 Park and Grab GC690XH
2.03.0 NOT Tourist Friendly GC5RTRK
2.03.5 Access or parking fee GC659F
2.04.0 Picnic tables nearby GC4PF2M
2.04.5 Recommended for kids GC48868
2.05.0 Needs Maintenance GC3Q29A
2.51.0 Wireless Beacon GC66DH2
2.51.5 NOT Quads GC2Z7C6
2.52.0 GeoTour GC4GW89
2.52.5 Campfires GC2DK5A
2.53.0 NOT Park and Grab GC58607
2.53.5 NOT Significant Hike GC62EFA
2.54.0 NOT Available at all times GC1PVR5
2.54.5 Tree Climbing GC5B2YN
2.55.0 May require swimming GCX97A
3.01.0 NOT Scenic view GC4PZE8
3.01.5 NOT Front Yard (Private Residence) GC6B61G
3.02.0 NOT Dogs GCZW98
3.02.5 Camping available GC293KV
3.03.0 NOT Stroller accessible GC1N97F
3.03.5 Climbing gear GC5PYQ9
3.04.0 NOT Telephone nearby GC6Y42M
3.04.5 Food Nearby GC5X6TG
3.05.0 Dangerous Animals GC7797C
3.51.0 NOT Medium hike (1km-10km) GC1CV3V
3.51.5 NOT Teamwork Required GC6ZPQD
3.52.0 NOT Motorcycles GC5X769
3.52.5 NOT Bicycles GC2MKCH
3.53.0 Recommended at night GC20J8N
3.53.5 NOT Difficult climbing GC70P16
3.54.0 NOT Wheelchair accessible GC5C7EM
3.54.5 Tourist Friendly GC5MAZ5
3.55.0 NOT Recommended for kids GC51NMA
4.01.0 NOT Snowmobiles GC1FXV5
4.01.5 Abandoned mines GC4Y2R7
4.02.0 Off-road vehicles GC5A6TY
4.02.5 Dangerous area GC7E474
4.03.0 NOT Short hike (less than 1km) GC4QKGW
4.03.5 Poisonous plants GC5XFNE
4.04.0 Medium hike (1km-10km) GC68DR7
4.04.5 NOT Truck Driver/RV GC70KWK
4.05.0 Available during winter GC5C0E1
4.51.0 NOT Poisonous plants GC52P55
4.51.5 Cross Country Skis GC4KDZD
4.52.0 May require wading GC22Z6X
4.52.5 Fuel Nearby GC2JAXW
4.53.0 Hunting GC4T30Q
4.53.5 Ticks GC5XFRH
4.54.0 Front Yard (Private Residence) GC2J51D
4.54.5 Takes less than an hour GC5HFH4
4.55.0 NOT Food Nearby GC5WZKT
5.01.0 NOT Field Puzzle GC5F090
5.01.5 Bicycles GC476AB
5.02.0 Motorcycles GC3C5G2
5.02.5 Stealth required GC4VXB6
5.03.0 Scenic view GC3P7G7
5.03.5 Available at all times GC54PBE
5.04.0 Short hike (less than 1km) GC5ZXV6
5.04.5 Teamwork Required GC4RX12
5.05.0 NOT Off-road vehicles GC70M4A
Did you try it on your user or user Xnard for whom it still times out? I have found that users with 10k or more finds typically see a fast solution. They have so many options a solution shows up quickly.
I tried Xnard too - and got a result back in 50 seconds - so it didn't time out.
However there was also the message
"Sorry, the checker goes out of time without try all combination. This can be false negative" - this suggests it did time out but I got this after 50 seconds ?
It does suggest Xnard may not qualify but the last message confuses that result
As I said earlier it's not that surprising. Many finds usually just implies many DT/attribute combinations and basically free choice of attributes for each cell. It is just for users with few finds, but still enough to fill the DT grid, that it becomes rather hard to find a solution. And checking ALL combinations is really, really, really impossible. If there are for example 10 possible choices per cell that'd make 10^81 possiblities, a bit more than the number of atoms in the universe. The checker currently is a bit smarter than that but I suspect for some of these hard users it would still take years to check.
Locally, I used a SAT solver which has the advantage of being able to "learn" from failed attempts and recognize future attempts that would fail in a similar way earlier. The issue is that challenge checkers are not allowed to use any external resources outside of the ones PGC provides. So I'd have to write my own SAT solver in Lua and have it in a checker script. I've wanted to do this already anyway at some point, but it will probably take some time.
Oh, and as rragan mentioned the 50 second limit is esentially a timeout. The scriptwriter automatically stops the search after 50 seconds if it didn't give any results and then leaves 10 seconds to produce output and such. If you didn't interrupt the search in the script but let the server cancel the checker request the user would just get a not so nice error message.
Edited 2 time(s). Last edit at 01/02/2020 01:16AM by PattuX.
I also have a checker timing out for me.
GC6T3JZ - LPC - Triple Marathon Challenge (United States) has timed out for me every time I have tried it. The single and double marathon challenge checkers have worked well for me.
The script groups your caches into "cells" and checks whether the cells are close enough together to potentially have matches. I think that for this challenge the cells are defined too large. I've emailed the script writer to ask if he can add a single line to the script so that the tagger can define the cell size.
By playing around with the script, I found that for your finds with the cell size as set, the script has to check nearly 30,000,000 combinations of finds. This is why it's timing out. By setting the cell size to 25% in each direction, it reduces the number of comparisons to less than 700,000 and doesn't time out. Reducing it further to 10% reduces that to barely over 250,000. I'll message the tagger to adjust when/if I get a response from the script writer.