Discussion:
puzzle: Cross the desert
(too old to reply)
r***@gmail.com
2016-02-10 19:06:53 UTC
Permalink
Raw Message
You are stranded in a desert, at a base station,
looking to get home. There's a rescue truck,
11 miles away. Along the route, there is a
series of rest stations, one at each mile.

To make this long trip, you need water. You
have a wagon, which can carry up to 7 liters.
You drink one liter of water during the hike
between each station, forward or backward

Clearly, you cannot make it in one shot. However,
you may store any quantity of water at the rest
stations. Hence the solution: a series of hikes,
back and forth,dropping and picking up water, until
you ultimately arrive at the rescue point.

What is the minimum initial quantity of water required,
at the base?

This case isn't hard, as 11 miles is a short
distance. But imagine it's 20 to the rescue station,
that would be a lot of work!

Note the problem statement: not merely to find
a procedure to reach safety, but also minimizing
the store of water. So, for a long walk, you
could find an algorithm solution; but how would
you show your algorithm is optimal?

--
Rich
c***@gmail.com
2016-04-17 15:03:04 UTC
Permalink
Raw Message
Post by r***@gmail.com
You are stranded in a desert, at a base station,
looking to get home. There's a rescue truck,
11 miles away. Along the route, there is a
series of rest stations, one at each mile.
To make this long trip, you need water. You
have a wagon, which can carry up to 7 liters.
You drink one liter of water during the hike
between each station, forward or backward
Clearly, you cannot make it in one shot. However,
you may store any quantity of water at the rest
stations. Hence the solution: a series of hikes,
back and forth,dropping and picking up water, until
you ultimately arrive at the rescue point.
What is the minimum initial quantity of water required,
at the base?
This case isn't hard, as 11 miles is a short
distance. But imagine it's 20 to the rescue station,
that would be a lot of work!
Note the problem statement: not merely to find
a procedure to reach safety, but also minimizing
the store of water. So, for a long walk, you
could find an algorithm solution; but how would
you show your algorithm is optimal?
I think the general plan must be, first, to advance a large cache of water forward from one rest station to the next; second and possibly more complicated to arrange the "end game" in which a succession of forward stations have just enough water to support a dash to the rescue point.

The first part seems clear since for example caching at station 2 via a round trip from the starting point 0 requires drinking 4 to cache 3 -- costs 4/3 liter per liter. By comparison caching at station 2 via staging at station 1 saves in two ways: The forward portions from station 1 to 2 will be fully laden hence more efficient, and some return journeys from 1 to 0 are obviated.

The end game can partly (largely?) be figured out by working backwards. The final final dash starts from resting at station -7 (7 from the rescue) with a full load of 7 liters. Prior to that, you may as well have had a full load at station -8 with 1 advance liter at station -7, ... & several steps before advance liters at stations -7, -8, ..., -x, and holding a full load at -x.

In between I suppose it gets messy, as for example the load limit means that sometimes you can carry an extra liter "for free" so there may be tricks as to when and how you distribute a few of the advance liters.
Loading...