Return to Project-GC

Welcome to Project-GC Q&A. Ask questions and get answers from other Project-GC users.

If you get a good answer, click the checkbox on the left to select it as the best answer.

Upvote answers or questions that have helped you.

If you don't get clear answers, edit your question to make it clearer.

Is there a checker available for GC479VE?

0 votes
75 views
Around the World in 80 Caches Challenge
asked Oct 26, 2015 in (OBSOLETE) Checker requests by AF BEE (120 points)
A part of the requirement is
...distance from your home coordinates, grandma's house, parent's house, college you attended (starting point is at your discretion)....

Do I understand correctly that you can choose any starting point you like?

I am quite sure that if there exist a point where the sum of the distance to all caches is less or equal to the circumference of the earth there will be an ok solution to the challenge.
An really informal mathematical proof is
there also the exist a point where the sum of the distance is greater then the circumference. Just move more then 2/80 of that distance and the distance will greater then the circumference. You can use the triangle inequality to show that.
The equation that give the sum of the distances from a point is a continuous function along the any line between those points. And with a smaller value and a larger value the intermediate value theorem show that a correct value has to exists.
And is is proven that a point the meets the requirement exists.

In practice that means that if you have 80 finds in a circle with the diameter of 500 km you will have a ok solution to the challenge. If not you might still have one.

That all is only if any point can be used at the start. Else if it has to be a specific point like the one in the example a checker cant be coded. It will not know where the possible points are. It don't even know your home coordinates.
Perhaps it would be easiest to develop a GSAK Macro? http://gsak.net/board/MacroIndex.php
GSAK contains a database of all geocache finds, to include a field for distance from a point (typically home).  An iterative check of groups of 80 caches within the finds set should yield a group of 80 where the sum of the distances total between  25,046.48 to 25,047.48 miles.  Should be pretty straight forward...I just don't know how to do macros :)
The problem it not that straight forward to solve is you can choose your starting point.
There is (k n ) (binomial coefficient with strange syntax) combinations. in this case n=80 and k=your numbers of finds. in your case is it 11323. The number of combinations is (1132  80)=2.19*10^205
It is obvious that it has to be solved another way than to check all combinations it that was your idea

The problem is a modified  knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem if I am not mistake with a specific target value and number of items
More exactly it is a modified https://en.wikipedia.org/wiki/Subset_sum_problem problem
If you read the articles the problems are NP-complete and will result is all problem of that category

An idea how to solve them it to split it into two problems. One fore the caches far away and one for caches near you. Perhaps 77 distant caches and 3 near.
There will be a fever caches far away and try to find a distance close by less the the circumference of the earth. I would guess that a dynamic programming approach is the way to do it.
The generate all combinations of 3 near caches.
Now it is trivial to check if there is a combination of far and near groups that meats the requirement.

It will work really well if you have alot of finds near (earth circumference/80= 500 km) distance. if you have alot of finds at another distance greater then that perhaps use a number of distant caches that give them an sum of the circumference of the earth.
An approach wit a split in really near caches <a fem km. caches a bit further away and far caches is better to result

I would not write a program that calculate that inb GSAK macro language but in another language that have more possibilities and is faster.
But using GSAK to calculate the distance is an idea

A problem is that CO has done defined what the distance between two caches is. is it a straight line between the point and the cache or is it the great circle path along the surface of the earth? I have no idea what GSAK uses

Please log in or register to answer this question.

...