Friday, February 8, 2008

The backdoor to Where's Yoda?

One thing I love about geocaching is that each person can interact with the game/sport/hobby however he or she chooses. If you pull out a laptop at a pick-up soccer game, you will get looks.

Yesterday, I published a puzzle cache called Where's Yoda?. In order to solve the puzzle, the cacher uses a Javascript calculator that I hacked together from some code I stole from a colleague. That calculator is now here and not on this blog because GC.com does not like it when cache pages re-direct to pages that have links to commercial sites, as I do here (for convenience, not necessarily to promote those products).

I am fascinated with ways that cachers can get around actually solving a puzzle. One way would be to look at the code in the page source for the calculator, so I had to figure out how to encrypt that code. (And if you can decrypt that, then more power to you!)

Another way that cachers get around solving puzzles is by flooding geochecker.com with checks until they hit Success! This Yoda puzzle has 10^6 possible answers, so that's not really a problem here.

A third way is by plotting possible answers on Google Earth. For example, on Millah's musical puzzle cache Final Countdown I didn't have the hundredths of west or the thousandths of north, so I plotted a rectangle in Google Earth and guessed where it should be (incorrectly, it turns out).

In order to discourage this, once the cacher finds the coordinates of Yoda (X,Y), I give the cache coordinates as (7X-2Y+230,Y^2-7X^2-48339), so that distances in Yoda-land don't correspond to distances in cache-land. (I realize that a box of 1'N by 1'W is not a square, but that can be accounted for.)

Well, around the time last night that the cache was published and the first responders were going after it, I realized that these formulas give a bit of a "back door" around the calculator (which gives the distance between a guess and Yoda's location). Here's how it goes:

7X-2Y+230 and Y^2-7X^2-48339 need to be between 0 and 999. If you use a computing package like Mathematica (which I'm using a lot these days for my multi-variable calculus course), then you can determine that there are only 339 (out of 10^6 !!!) possible locations for Yoda and hence the cache. Here's my code:

z = 0; For[x = 0, x < 1000, x++,
For[y = 0, y < 1000, y++,
If[-1 < 7 x - 2 y + 230 &&
7 x - 2 y + 230 < 1000 && -1 < y^2 - 7 x^2 - 48339 &&
y^2 - 7 x^2 - 48339 < 1000, z++;
Print[z, ": Yoda=", {x, y},
"--> cache=", {7 x - 2 y + 230, y^2 - 7 x^2 - 48339}]]]]

And here's some of the output:

1: Yoda={36,240}--> cache={2,189}
2: Yoda={36,241}--> cache={0,670}
...
339: Yoda={367,996}--> cache={807,854}

I'd like to figure out how to write a script that exports these coordinates to a KML or GPX file that Google Earth can then plot. I wonder how many of those 339 possible locations correspond to plausible hiding spots? Of course, this is all much more involved than just working with the calculator as intended.

Like I say, geocaching is whatever it means to you. And today, geocaching looks a lot like my job! Time to go grab some LPCs!

3 comments:

Rick Richardson said...

http://www.rkkda.com/tmp/wheresyoda.gif

Plot of 339 coords....

$ geo-map -s0 `sh wheresyoda.sh`

$ cat wheresyoda.sh
awk '
BEGIN {
z = 0;
for (x = 0; x < 1000; ++x)
{
for (y = 0; y < 1000; ++y)
{
if ( (-1 < (7*x - 2*y + 230)) \
&& ((7*x - 2*y + 230) < 1000) \
&& (-1 < (y*y - 7*x*x - 48339)) \
&& ((y*y - 7*x*x - 48339) < 1000) )
{
z++;
printf "44.58.%03d w93.14.%03d\n",
7*x - 2*y + 230, y*y - 7*x*x - 48339
}
}
}
}'

firstbass said...

Thanks, Rick, that plot is awesome. Many of those locations are plausible, so maybe it's not much of a back door after all!

Did you use GSAK to produce that? I'm on a Mac, and MacCaching is a pretty poor facsimile of GSAK, I hear, certainly in terms of mapping. I'm tempted to dig out an old Pentium IV tower just to run GSAK and manage City Navigator.

Rick Richardson said...

Used my own software:

http://geo.rkkda.com/

Runs linux, mac.

Mac OSX Support

Do this FIRST:

Download and install MacPorts:
http://www.macports.org/

$ PATH=$PATH:/opt/local/bin
$ sudo port selfupdate
$ sudo port install gsed
$ sudo port install coreutils
$ sudo port install lynx
$ sudo port install ImageMagick

Download and install gpsbabel:
http://www.gpsbabel.org/

$ cd gpsbabel
$ ./configure --with-libexpat=/opt/local/lib --with-expathdr=/opt/local/include
$ make
$ sudo make install