Sunday January 30, 2011
This problem touches upon many aspects of computer science, mathematics and problem solving. At its heart though it is a problem about algorithms. The successful algorithm will not only be correct, but will finish running in the allotted time.
There is this dude, Sissy Fuss the Greek, with this lifetime gig that's a royal pain in the you-know-what. Anyway, he found a way to change jobs, but the dude needs your help to figure out how long it is likely to take. We don't know many details on the new job yet, but we've heard it does involve drinking a coffee liqueur and milk, random walking, big rocks and probability (don't try this at home, kids).

The dude's world is a 3x3 grid laid out on the side of a hill where he starts out in the center. There are these three big boulders, one in each of the 3 bottom square of this grid. He has to move each one up to the top row of the grid where there are three pedestals, one in each of the top squares. The dude is made to drink a quart of Kailua and milk each morning to disorient him, ensuring he moves randomly to an adjacent square, with no diagonal moves allowed since he's not wearing a miter. He can only move into one square each day. If he ends up in a square with a boulder and he is not carrying one, then he picks it up. If he ends up in a square with an empty pedestal and he is carrying a boulder, this is the only time and place he sets it down. Luckily, the pedestal has a permanent quick-set cement, which both prevents the boulder rolling back down the hill and prevents the dude from ever picking it up again.

How many days (to ten decimal places) is it likely to take the dude to complete this task, averaged over 10,000 simulation runs?
Show solution
Challenge Resources:
©1994-2014   |   Shodor   |   Privacy Policy   |   NSDL   |   XSEDE   |   Blue Waters   |   ACM SIGHPC   |   facebook  |   facebook   |   twitter   |   rss   |   youtube Not Logged In. Login