puzzle: Cross the desert

This group is comprised of mathematicians, 
who enjoy puzzles, so...

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

On Wednesday, February 10, 2016 at 11:04:34 AM UTC-8, RichD wrote:
> This group is comprised of mathematicians, 
> who enjoy puzzles, so...

(snip)

> 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

(snip)

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

Like Towers of Hanoi, I suspect that there is a recursive solution.

I don't know what it is, though.

On Wednesday, February 10, 2016 at 11:04:34 AM UTC-8, RichD wrote:

(snip)

> So, for a long walk, you 
> could find an algorithm solution; but how would 
> you show your algorithm is optimal?

Use dynamic programming.  If you do that, and do it right, it should
find the optimal value.  You can then go back and find what the optimal
recursion answer is.

A favorite use for dynamic programming is the algorithm for diff, which came
from one previously used for comparing protein sequences, finding the minimal
number of mutations from one to another.

It is also used for compilers to find the fastest sequence of instructions to 
generate an appropriate result.

On 4/13/2016 4:55 PM, herrmannsfeldt@gmail.com wrote:
> On Wednesday, February 10, 2016 at 11:04:34 AM UTC-8, RichD wrote:
>> This group is comprised of mathematicians,
>> who enjoy puzzles, so...
>
> (snip)
>
>> 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
>
> (snip)
>
>> What is the minimum initial quantity of water required,
>> at the base?
>
> Like Towers of Hanoi, I suspect that there is a recursive solution.
>
> I don't know what it is, though.

The goal is to minimize the distance walked since that costs 1 liter per 
mile (I hate mixing SI and Imperial units).  The minimum traveling will 
require the wagon to be as full as possible as well as not retracing 
steps.  Move all the water needed to station 1, then to station 2 
without returning to start, etc.  The final trip can start from station 
4 with a full wagon.

The trips between stations will be 1 trip one-way costing 1 liter, the 
rest are round trips costing 2 liters.

Start with 25 liters
4 trips to station 1, 18 liters
3 trips to station 2, 13 liters
2 trips to station 3, 10 liters
2 trips to station 4, 7 liters
1 trip to finish.

Total - 25 liters.  This is as low as it can go by always carrying as 
much as possible while not back tracking to the start, minimizing the 
"cost" of moving the water.

-- 

Rick

On Wednesday, April 13, 2016 at 10:02:32 PM UTC-7, rickman wrote:

(snip)

> The goal is to minimize the distance walked since that costs 1 liter per 
> mile (I hate mixing SI and Imperial units).  The minimum traveling will 
> require the wagon to be as full as possible as well as not retracing 
> steps.  Move all the water needed to station 1, then to station 2 
> without returning to start, etc.  The final trip can start from station 
> 4 with a full wagon.

Seems like the description doesn't say when you drink the liter.

If you drink one liter before each mile (yes, strange units), you can carry
seven liters, leave six and drink one for the trip back.

But it doesn't say that, and I think you didn't do that.

If you continuously drink, you start with seven, drink one on the way,
leave five, drink one on the way back. 

So, four trips is 3.5 round trips, using seven liters, which 
can supply 20 to rest stop 1, but you only need 18.

So, 3.5 plus 2.5 round trips gets 13 liters to rest stop 2.

If you instead go directly to rest stop 2, you get three liters there, while
drinking four for each round trip. You can get 12 liters there in 3.5 round
trips, or 15 in 4.5 round trips, for 33, as you note, not keeping the wagon
full.

As with packing problems (what is the smallest volume rectangular crate
you can fit N spheres in?) there are round-off cases.

Note that the wagon isn't full for one of the trips out from the start, as
you could have moved 20, instead of 18.  Given that, you can't prove that
your solution is optimal all the way through. 

I suspect it is for this case, but for longer trips, or other costs
per trip, it might not scale.
 
> The trips between stations will be 1 trip one-way costing 1 liter, the 
> rest are round trips costing 2 liters.

> Start with 25 liters
> 4 trips to station 1, 18 liters
> 3 trips to station 2, 13 liters
> 2 trips to station 3, 10 liters
> 2 trips to station 4, 7 liters
> 1 trip to finish.

> Total - 25 liters.  This is as low as it can go by always carrying as 
> much as possible while not back tracking to the start, minimizing the 
> "cost" of moving the water.

-- glen

On Wednesday, February 10, 2016 at 2:04:34 PM UTC-5, RichD wrote:
> This group is comprised of mathematicians, 
> who enjoy puzzles, so...
> 
> 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

RichD, Don't you owe the group your answer to the "daily quiz"? - Dirk

> 
> Seems like the description doesn't say when you drink the liter.
> 
> If you drink one liter before each mile (yes, strange units), you can carry
> seven liters, leave six and drink one for the trip back.
>

yes it is amazing to me how often seeming well defined specs in English, can have ambiguities that turn out to be important.

And things specified in math can be hard to comprehend.

We need a specification language that is both easy and intuative to comprehend and unambiguous.

M
 

On 4/14/2016 3:53 AM, herrmannsfeldt@gmail.com wrote:
> On Wednesday, April 13, 2016 at 10:02:32 PM UTC-7, rickman wrote:
>
> (snip)
>
>> The goal is to minimize the distance walked since that costs 1 liter per
>> mile (I hate mixing SI and Imperial units).  The minimum traveling will
>> require the wagon to be as full as possible as well as not retracing
>> steps.  Move all the water needed to station 1, then to station 2
>> without returning to start, etc.  The final trip can start from station
>> 4 with a full wagon.
>
> Seems like the description doesn't say when you drink the liter.
>
> If you drink one liter before each mile (yes, strange units), you can carry
> seven liters, leave six and drink one for the trip back.
>
> But it doesn't say that, and I think you didn't do that.
>
> If you continuously drink, you start with seven, drink one on the way,
> leave five, drink one on the way back.

Yes, this latter description is the one I used.  Equate miles to water 
consumed.


> So, four trips is 3.5 round trips, using seven liters, which
> can supply 20 to rest stop 1, but you only need 18.
>
> So, 3.5 plus 2.5 round trips gets 13 liters to rest stop 2.
>
> If you instead go directly to rest stop 2, you get three liters there, while
> drinking four for each round trip. You can get 12 liters there in 3.5 round
> trips, or 15 in 4.5 round trips, for 33, as you note, not keeping the wagon
> full.
>
> As with packing problems (what is the smallest volume rectangular crate
> you can fit N spheres in?) there are round-off cases.
>
> Note that the wagon isn't full for one of the trips out from the start, as
> you could have moved 20, instead of 18.  Given that, you can't prove that
> your solution is optimal all the way through.

The goal is to use the least amount of water.  How is transporting less 
water not optimal?  As you say, round off of water per trip is required. 
  That doesn't make it non-optimal.

Actually, the optimality of the solution comes from minimizing the 
distance traveled, not directly from having a full wagon.  As I was 
thinking it through I realized longer trips would move less water 
because the wagon would be depleted more by the longer trip requiring 
more trips.  That is why that comment was in there.  In reality it is 
only the number of miles traveled that matter.


> I suspect it is for this case, but for longer trips, or other costs
> per trip, it might not scale.

What is that based on?


>> The trips between stations will be 1 trip one-way costing 1 liter, the
>> rest are round trips costing 2 liters.
>
>> Start with 25 liters
>> 4 trips to station 1, 18 liters
>> 3 trips to station 2, 13 liters
>> 2 trips to station 3, 10 liters
>> 2 trips to station 4, 7 liters
>> 1 trip to finish.
>
>> Total - 25 liters.  This is as low as it can go by always carrying as
>> much as possible while not back tracking to the start, minimizing the
>> "cost" of moving the water.
>
> -- glen
>


-- 

Rick

On 4/14/2016 11:20 AM, makolber@yahoo.com wrote:
>
>>
>> Seems like the description doesn't say when you drink the liter.
>>
>> If you drink one liter before each mile (yes, strange units), you can carry
>> seven liters, leave six and drink one for the trip back.
>>
>
> yes it is amazing to me how often seeming well defined specs in English, can have ambiguities that turn out to be important.
>
> And things specified in math can be hard to comprehend.
>
> We need a specification language that is both easy and intuative to comprehend and unambiguous.

"You drink one liter of water during the hike
between each station, forward or backward"

Is that not clear?

-- 

Rick

On Thu, 14 Apr 2016 08:20:50 -0700 (PDT), makolber@yahoo.com wrote:

>
>> 
>> Seems like the description doesn't say when you drink the liter.
>> 
>> If you drink one liter before each mile (yes, strange units), you can carry
>> seven liters, leave six and drink one for the trip back.
>>
>
>yes it is amazing to me how often seeming well defined specs in English, can have ambiguities that turn out to be important.
>
>And things specified in math can be hard to comprehend.
>
>We need a specification language that is both easy and intuative to comprehend and unambiguous.

But if it is used by people, they'll find a way around those features.
;)