What is the shortest distance?

Question

24 unit blocks are arranged in a rectangular 4x6 grid with "streets" of unit widths separating them, so that beginning at corner (0,0), the far corner is (7,11). Assuming that one has to walk around blocks but may traverse streets at any angle, what's the shortest distance that may be walked between (0,0) and (7.11)?

This is a familiar scenario when one has to cross a parking lot full of cars.

hayhabr, read the question carefully. The blocks are separated by streets of unit widths, which may be traversed at angles, thereby cutting distances and making this problem harder.

Gary H, good work, let's see if anyone can beat your figure.

Actually, your figure sums up to 13.6476, not 12.09. The diagonal from (0,0) to (7,11) is 13.0384, so it can't be less than this.

Answer 1

There are 2 equal minimum paths. The first is to go North 1 block, then turn and walk 45 degrees East for a distance of
SQRT(7^2 + 7^2) units, which brings you to (7,8), then North 3 units. Total distance is

1 + SQRT((7^2 + 7^2) + 3

= 4 + 7SQRT(2)

~= 13.9 units

The second is to go North 3 units, turn and walk 45 degrees East 7SQRT(2) units, North 1 unit.

[REPOST} Oops! There is one shorter distance - North 1 unit to (0,1), then to (3,4), then to (4,7), then to (7,10), then to
(7,11). Total distance =

1+ SQRT(18) + SQRT(10) + SQRT(18) + 1

~= 12.09

[RE-REPOST]
Yup, you're right, I mis-simplified the square roots mentally before breaking out the calculator. I stand by the 13.647 distance as the shortest.

Answer 2

if we were to draw a line from (0,0) to (7,11), it'd have 11/7 slope. It's logical that the closer to this slope are the sub-components of our path, the shorter distance we will see.

11/7 ~ 1.57

to get slope of 1.5, we'd ahve to be walking 2 squares right for every 3 squares up

our streets, unfortunately, are 1 square wide.

so the best slopes we can get to are 1.0 and 2.0

let's try this path:

(0,0) (1,0) (2,5) (5,8) (6,11) (7,11) = 14.503

this path deviates far away from the straight line though at point (2, 5)

so let's try

(0,0) (1,0) (2,3) (3,4) (4,6) (7,10) (10,11) = 13.981

better

the furthest-away point from the straight line now seems to be (1,0). Maybe its wiser to go to (0,1) instead.

let's try

(0,0) (0,1) (3,4) (4,7) (7,10) (7,11) = 13.647

beautiful. This path is also symmetric, which adds it some credit. Let's go with this answer.

The algorthim for finding the right path is then like this:

- draw a "green line" that is a straight line from A to B.
- start moving in the direction closest as possible to the green line, and keep moving keeping as close to the green line as possible :)
- make sure that you cross the green line in the middle of the board - it's obvious the right path should be symmetric.

Answer 3

As long as you go up or right each time, all paths will be the same length. So just count up to the top then over to the right. 11 + 7 = 18 blocks.