×

To be able to write in the forum you need to authenticate. Meanwhile it's read-only.

Change History

Need a challenge checker made or improved? This is where you should post your request.

Message: Re: GC87FM1 Countries, Types, 4x4 Matrix

Changed By: PattuX
Change Date: October 10, 2019 06:34PM

Re: GC87FM1 Countries, Types, 4x4 Matrix
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.

Original Message

Author: PattuX
Date: October 10, 2019 06:10PM

Re: GC87FM1 Countries, Types, 4x4 Matrix
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.