Yeah, click both images.
This extraordinarily easy, simple little problem has been sitting on VleeptronZ, in full public view of every Carbon or Silicon Entity who can get its hands (if it has hands) on a computer, since 15 March 2007 -- roughly 11 months. It is growing Old, it badly needs a haircut and a shower, it is starting to smell bad and fester and mold.
The Easter Bunny feels unloved, unwanted, lonely. The Easter Bunny, who feels terribly guilty about assassinating the Russian Imperial family and stealing their fabulous Faberge Easter Eggs, desperately needs YOUR help to give 13 of them back to 13 lucky little girls and boys this Easter
but answer came there none.
Despite the spectacular Prize of 1 Giant Pizza with the Toppings of the winner's choice, nobody has submitted an Answer.
Not even RamanuJohn, the Amazing Occidental Mathematical Mystic from Maine, who solved the original 7-Node Travelling Santa Problem, thus allowing Santa Claus to deliver iPods and Amy Winehouse "Rehab" .mp3s to 7 little boys and girls on Christmas Eve in the shortest possible distance and time.
Does this crowd believe in Santa Claus, but think the Easter Bunny is some kind of silly myth undeserving of a little computational assistance? There are odd theological implications in this possible reason why this problem is being universally dissed and ignored.
Initially we loudly dangled this problem in front of The Dutch Power Cows, who arrogantly boast (in Dutch) that they are the most powerful organization of amateur computerists on Planet Earth, regularly annihilating some of the most difficult mathematical and scientific problems known to Klaas from Rotterdam.
Well, obviously, the DPC are not really very good at this kind of thing, and are probably just a front for a porn and hydroponic cannabis gang. Or perhaps their inability to read a blog in English has blinded them to the interesting mathematical and computational aspects of the Easter Bunny's troubles.
So, okay, I will use Very Small Words to explain what is going on here, to offer special assistance to the Thick.
Santa Claus and the Easter Bunny face an astonishingly famous mathematical problem more commonly called The Travelling Salesman Problem, or the TSP.
(In the UK a travelling salesman is called a Commercial Traveller, and Durrenmatt called one of these gentleman "Traps," a nickname from the luggage in which he schleps around his sales samples. What happened to him when his car broke down in the Alps one night will curl your hair, but he probably deserved it. If you can't read, you can rent the excellent video starring George Segal.)
Yes, of course women travel around selling crap too, but mathematicians and computerists still call it The Travelling Salesman Problem.
And it's actually a Practical Problem. Real Human Beings who reside in Ordinary SpaceTime just like baseball players and Britney Spears actually need the Answers to TSP to save Money (do I have your attention now?) and Time, which is Money. Real Capitalist Corporations use their Big Computers to try to get Answers to TSP so they can Make More Money.
A Travelling Salescreature who is sitting at Headquarters must visit customers in n cities, each city just once, and after the last city, fly back to Headquarters. Each flight between cities is a straight line.
Suppose n = 3 or 4 or 5. This does not present much of a headache; there aren't very many different possible paths to analyze and sum the flight length segments to find the shortest possible path.
But when n = 6, 7 (Go RamanuJohn!) or more, things require Aspirin, or (for Canadians) Aspirin with Codeine, and Big, Fast Computers and Supercomputers.
As n gets bigger, the number of different possible paths increases so dramatically that the Salescreature, and the company's entire IT Department, just give up and essentially have to pick an educated guess -- which almost certainly is NOT the shortest possible path. It's sort of short-ish, and can be shown to save on airfare more than most other paths, but No Pizza.
(You can get a Ph.D. and a big private-sector paycheck by specializing in the mathematical field of this kind of Educated Guessing.)
Eventually n gets so big that computing The Shortest Possible Path is beyond the power of the world's biggest Supercomputers -- at least in a reasonable amount of time. Finding the Shortest Path after all the Sales Associates are dead will not help the corporation get richer.
Okay, there are other Practical (and non-Practical, but Fun) Applications for TSP besides selling shoelaces and glow-in-the-dark condoms.
Trust Vleeptron: This is a Very Important and consequently a Very Famous Mathematical Problem.
And in only 33 days, the Easter Bunny needs the Answer. Time (which is Money) is running out. The Easter Bunny is not getting any younger or smelling any sweeter, and the Giant Pizza isn't, either.
I know everybody thinks Math is Disgusting and Vulgar and (as Talking Barbie used to say) Hard. I know you like Vleeptron better when we show images of pretty young naked Suisse women, or discuss the Technology of Male Face Shaving, which (by counting Comments received) is The Most Important Thing In The World.
(The War in Iraq and USA Election 2008 and Protecting Our Schoolchildren from Charles Darwin get Comments, but not nearly as many as Shaving.)
I am trying to solve the Easter Bunny's Problem myself, with my amazing new Vleeptron Supercomputer, the envy of Real Estate Agencies and Dental Practices throughout the Connecticut River Valley.
Unfortunately the only software tools available to me at the moment are my beloved ancient unsupported QuickBasic and my new Python, which is wonderful because it is Free, but it is also Slow as Bre'r Rabbit Molasses, and if I use Python or QB, I will probably get the Answer sometime around 2020 AD.
So once again I am taking a Second Look at the outre Forth (extinct-ish) and LisP (currently un-trendy, maybe extincting). Other programming lingo advice always gratefully received. Am I finally going to have to overcome my aesthetic revulsion for C++ to solve this sucker? I'd really rather not, but ... well, whatever it takes.
What follows is a slightly modified and updated version of the original 13-Node Travelling Easter Bunny Problem AND the x,y coordinates of the houses of the 13 little boys and girls who are still waiting for their Faberge Easter Eggs. The coordinates are in text that can be copied and pasted into your computer (or your college's mainframe) without risking re-typing errors.
Oh. Okay. So I squished the Earth and made it Flat. Go ahead, make fun of me, insult me, complain. Here is a ready-made Comment:
asshole the erth is rownd
Well, here's the deal. Some Real Mathematician PROVED that TSP is the same problem whether the Earth is an Oblate Spheroid or Flat. So there.
TSP, on a sphere or on a plane, belongs to a class of problems called NP-Hard. (GeekSpeak: nondeterministic polynomial-time hard.) If you can find a significant time-slashing shortcut to TSP, this shortcut will equally slash the time it takes to compute all NP-Hard problems, and maybe you can get invited to be on Late Night with David Letterman.
If you got a C+ or better in Mandatory Geometry Class, you should be Very Grateful that I squished the Earth and made it Flat. Because you just possibly might remember that you can use the Pythagorean right-triangle relationship to find the straight-line distances between any two cities.
If you would prefer finding the Easter Bunny's Shortest Possible Path on the Surface of a Sphere, using segments of Great Circle arcs and Spherical Trigonometry, Leave A Comment, you Sick Fuck, I'll see what I can do.
How hard can this be? Huh? Really. How hard can this be?
I am the Easter Bunny, and I need your help!
Easter Sunday 2008 is 23 March, so I don't have much time.
In 1918, after assassinating Tsar Nicholas and Tsarina Alexandra of Russia and their children, the Easter Bunny stole all their fabulous Fabergé Easter eggs made of diamonds, emeralds, sapphires, pearls and gold.
I feel very bad about this, and now I want to give back 13 of the beautiful Fabergé eggs.
I have chosen 13 little girls and boys, who live in 13 different houses, and I want to deliver the beautiful Fabergé eggs to them on Easter.
I need to know The Shortest Possible Path from Easter Bunny Centre, to each house, and then back home again to Easter Bunny Centre.
Finding the Shortest Possible Path connecting 13 different places is a Very Hard Problem, and I'm just a Dumb Bunny who is not smart enough to find the Shortest Possible Path in time for Easter!
As you all know,
* the Earth is Flat
* the shortest distance between 2 points is a straight line
* all distances are measured in kilometers
* Easter Bunny Centre is at the origin (0, 0)
Here are the (x, y) coordinates of the houses of the 13 children:
child ............ x .......... y
Anna ....... -267.79 .... -083.96
Benjamin ... -826.03 .... +846.76
Carmen ..... +863.47 .... -416.76
David ...... -510.72 .... +450.21
Eloise ..... +905.16 .... -597.97
Freddy ..... +701.36 .... -691.47
Gemma ...... -653.85 .... -469.27
Hrothgar ... +460.26 .... +096.81
Imogen ..... -713.34 .... -706.31
Jacques .... +917.97 .... -016.04
Kiki ....... +344.47 .... +462.57
Leonhard ... +884.65 .... +164.46
Mimi ....... +061.24 .... -962.69
Here are EXAMPLES of a Path Answer. Small "e" stands for Easter Bunny Centre. The Easter Bunny only needs 2 decimal digits of precision.
Path .......... Length of Path
eABCDEFGHIJKLMe 87654321.09 km
eCMBJGFLAHEKDIe 45678901.23 km
[An illustration of the second example is shown above.]
Please help me! What is the Shortest Possible Path??? Don't make me hop all over the place and waste weeks of time. I need to deliver all 13 Fabergé eggs on Easter Sunday!
I have posted my problem on my blog for ALMOST 1 YEAR!!! But NOBODY ON THE INTERNET has tried to solve it!!!
Is there No One on Earth or C-Space who has the skills, brains and computing power to help me?
Time is running short! Help!
The Easter Bunny
Easter Bunny Centre
P.S. I promise to buy 1 Giant Pizza, with your favorite toppings, at your favorite Pizzeria, for ANYONE who can solve my problem in time for Easter! (Shipping & Transportation not included. You got to come here or I'll buy if I come there.)
Labels: 13-Node Travelling Easter Bunny Problem Travelling Salesman Problem NP-Hard RamanuJohn Dutch Power Cows porn cannabis Britney Spears Roger Clemens Friedrich Durrenmatt Traps