News for hackers. Stuff that matters.
Re:Game designer designs a game for 2,000 years from now, hi... by shabble on Saturday May 25, 2013 @05:21PM (#5768893)
He estimates that if one person visits a GPS location each day with a metal detector, the game will be unearthed sometime within the next million days — a little over 2,700 years.

[T]he sheets of GPS coordinates were collected by GDC volunteers at the door in an attempt to collate the data, hopefully leading to the game's earlier discovery.

Gentlemen, start your Travelling Salesman algorithms. From a quick skim of the wikipedia page, 1M nodes is probably too many to solve exactly, but (might?) be within 1% via heuristic methods.

Then again, depending on the area the entire set of coordinates covers, dividing it into zones and computing TSP over each would be much more practical, and allow parallel searches by multiple groups.

I wonder if the creator wouldn't have been better off with a Geohashing[1] type location clue, but I'm struggling to think of a useful time-specific seed that is both resistant to precomputation, and likely to survive 2k+ years hence. The XKCD one uses the value of the Dow Jones average for industrial stocks, but I doubt it could be relied on for more than a few decades, or a century or three in a best case.

[1] http://wiki.xkcd.com/geohashing/Algorithm

Re:Game designer designs a game for 2,000 years from now, hi... by ghshephard on Saturday May 25, 2013 @10:11PM (#5769741)
TSP is relevant to graph traversal. "Something buried in the desert" has no (or at least, very little) restriction on how you move from node to node.