If you've seen the base problem before and want an additional challenge, keep reading.

Basic Problem: There are a spider and a fly in a 10 x 10 x 44 foot box. (For the sake of discussion, the ceiling and floor are 44 x 10, the "side" walls are 44 x 10 and the "end" walls are 10 x 10.) The spider is on one end wall, 2 feet down from the ceiling, centered between the two sides. The fly is on the opposite end wall, 2 feet up from the floor, centered between the two sides. The spider wants to find the shortest route from her current position to the fly. The spider is constrained to crawling on the six walls of the room. (Let's say it's a room on the Space Station, so using gravity to get from the ceiling to floor is no good.) Also, assume that the fly is already immobilized and won't go anywhere before the spider get's there.

So what route should the spider take, and how long is that path?

(Solve that problem before you read the next part.)

The Harder Part: Once you get the "trick" to the basic problem you see that different routes are advantageous for different positions of the fly. Given the original spider position and any possible fly position on the other end wall (x = distance from one side wall, y = disance from floor), find the shortest path from the spider to the fly. Sometime the shortest route touches three walls (including the two ends), sometimes four, and sometimes five. If you were color the fly positions on the end wall where the shortest path touches only three walls red, the positions where the shortest path touches four walls blue and the positions where the shortest path touches five walls green, what would the end wall look like?

Even if you don't know the answer, is the question clear?

I'll post the answer some time after I figure it out.

Ryan [ March 31, 2005: Message edited by: Ryan McGuire ]

It looks to me like the red part of the wall is a convex pentagon that includes all of the top half of the fly's wall and encroaches on the bottom half. If my calculations are correct, the rest of the wall is all green.

Followon question: at what room length does blue start appearing?

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988

1

posted

0

Originally posted by Warren Dew: It looks to me like the red part of the wall is a convex pentagon that includes all of the top half of the fly's wall and encroaches on the bottom half. If my calculations are correct, the rest of the wall is all green.

Followon question: at what room length does blue start appearing?

Hmmm... I get a different picture. I have the far end wall as basically blue with a full width green triangle coming up from the bottom and a full width red triangle coming down from the top (i.e. A red stalactite and a green stalgmite). The red point comes down to somewhere between (5,3) and (5,4). The green point is between (5,2) and (5,3).

As a test, let's say you have a fly at (5,3) on the far wall. I have a four-wall (blue) path that's only sqrt(2745) = 52.39someodd feet long. Can you do better?

(Since this is a programming diversion, I programmed it. However there may be a bug in my program.)

Warren Dew
blacksmith
Ranch Hand

Joined: Mar 04, 2004
Posts: 1332

1

posted

0

You are correct. I missed the fact that once the positions are no longer symmetric, there are two different ways to go over four walls. My geometric solution only covered the way that got longer, and not the way that got shorter.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988

1

posted

0

Originally posted by Ryan McGuire:

Hmmm... I get a different picture. ... The red point comes down to somewhere between (5,3) and (5,4). The green point is between (5,2) and (5,3).

Ok, now that I've given out a qulaitative description of the answer to The Harder Part, you should try to find the exact position on the x=5 of the red and green points.