Re: GCA4N8H : 67 attributes by county challenge

Hello,

My cache ID is GCA4N8H

I am looking for something similar to GC8ZQMW, but restricting the area to Minnesota.

GC8ZQMW requires finding 68 attributes, but only one attribute can be used per find

However, since there are no more GeoTour caches in Minnesota, I would like one for 67 attributes
What I would like to add is:
- Each find must be within a specific county of Minnesota, for 67 total Minnesota counties

If it is possible, I would like the unused attributes (Lost and Found, Partnership, GeoTour) able to be used but not required

I do not think I qualify yet, but interested in seeing how it works.

Thank you much,

skyleaf



Edited 6 time(s). Last edit at 02/08/2023 07:21PM by skyleaf. (view changes)

I suspect that this request needs a new script because I have not seen this before

Interesting problem... I don't see a way with a current script either.

I've been using my A* search in quite few of my scripts recently, and I think that it or something similar will be required here, as the search space is potentially huge. Without an optimized search, you'd definitely timeout for some users with a brute force search. Ie. if somebody had 66 attributes in 67 counties, but didn't have the 67th attribute anywhere would be the worst case.

I'll give it a whirl and see if I can make something somewhat generic (but please be patient).

Does this not reduce to bipartite matching with at most ~8700ish edges? Then Ford-Fulkerson will find you your answer.

I might be missing something, but I'm not sure how this turns into a bigraph problem? There are N sets (eg. potentially 67 of them if you want to qualify).

As I understand it, the Challenge is:

Find 67 geocaches. Each must be in a different (Minnesota) county, and have a different attribute.

So, one can construct a graph where the nodes are the counties of Minnesota and attributes on Geocaching.com, and then join a county to an attribute if a cache has been found, in that county, with that attribute. (Because caches come form different counties, the "only one attribute can be used per find" can be disregarded.)

You then perform matching on this graph.

(I am surprised that no script currently exists for this.)



Edited 1 time(s). Last edit at 02/10/2023 08:46PM by Hügh. (view changes)

<a href="https://project-gc.com/Challenges/GCA4N8H/76268"><img src="https://cdn2.project-gc.com/Images/Checker/76268"; title="Project-GC Challenge checker" alt="PGC Checker"></a>

This works well, but I am looking for the 67 positive attributes. I don't think negative attributes can be used for a challenge

Is it possible to exclude the negative attributes and only search for 67 positive attributes?





Edited 2 time(s). Last edit at 03/26/2023 07:54PM by skyleaf. (view changes)

Change made. It is not clear you qualify. The checker timed out.

This is good. I will try to make some more finds so it can become clear I qualify. This thread can be archived for now