Searching for Waldo (or Wally, to give him his original name) is frustrating to the point of insanity. So when a doctoral student unexpectedly found himself snowed in last weekend, he decided to compute the most efficient way to look for the elusive red-and-white man.
Randy Olson, a grad student at Michigan State University's High-Performance Computing Center, decided that Ben Blatt's method, published in Slate, was not the absolute best way to search for Waldo. Blatt's method was based in compiling all the locations of Waldo in the seven main Waldo books by Martin Handford, and then identifying two horizontal stripes across the pages where he is most often found, before moving to other places. Olson's method uses some of the same data, but in a different way.
With these data points, Olson decided to figure out which path would get you to all the possible points in the fastest period of time. As Olson outlined in his blog:
In computer terms, that means we're making a list of all 68 points that Waldo could be at, then sorting them based on the order that we're going to visit them. So now we just need to try every possible arrangement of the points and find the one with the shortest distance traveled. Easy, right? Wrong.
Those 68 points can be arranged in ~2.48 x 1096 possible ways. To provide some context, that's more possible arrangements than the number of atoms in the universe. That's so many possible arrangements that even if finding Waldo became an international priority and the world banded together to dedicate the 8.25 million computing cores from the world's 10 largest supercomputersto the job, it would still take ~9.53 x 1077 years — about 6.35 x 1067x longer than the universe has existed — to exhaustively evaluate all possible combinations. (Generously assuming that each core could perform 10,000 evaluations per second.) In other words: if we don't have a smarter solution, Waldo is as gone as Carmen Sandiego.
Thankfully, there are plenty of smarter methods for approximating the optimal search path for finding Waldo. Below, I visualized the best solution over time of one such method — a genetic algorithm — that found a nearly-perfect solution. As you can see, genetic algorithms continually tinker with the solution — always trying something slightly different from the current best solution and keeping the better one — until they can't find a better solution any more.
The resulting path, as streamlined by Olson after the algorithm ran for five minutes was:
Olson then explained what conclusions his answer had provided:
1. The bottom of the left page is a good place to start. If Waldo isn't on the bottom half of the left page, then he's probably not on the left page at all.
2. The upper quarter of the right page is the next best place to look. Waldo seems to prefer to hide on the upper quarter of the right page.
3. Next check the bottom right half of the right page. Waldo also has an aversion to the bottom left half of the right page. Don't bother looking there until you've exhausted the other hot spots.
I annotated the best solution with a general path to follow when searching for Waldo. If you don't find Waldo at the end of that trail, then you've got an outlier and should check the middle of the pages or the top left and right.
Not bad for a surprise snow weekend's worth of work, right? If you prefer to spend you time fruitlessly searching every inch of the books' images to find the bastard, you can do that. If you want to put your search in the hands of science, you can use this method. Go to Olson's blog to learn more about his process and to see the algorithm run through many different path possibilities.
[via The Guardian]