Problem # 18 : Die Hard
Remember the movie "Die Hard with a Vengeance" (*ing Bruce Willis.
Third in a series of Die Hard movies).
Well
at one point in the movie
he was given two containers
one with
a capacity of 5 litres and the other with 3
and an endless supply of water.
To stop a bomb he needed exactly 4 litres of water.
This is what he did :-
-
Filled the 5 L container
-
Using the full 5L can
he filled the 3L can. Now there are 2L in the 5L
can.
-
Emptied the 3L can.
-
Poured the contents of the 5L can into the 3L one. Now
there is no water
in the 5L can and 2L in the 3L can.
-
He filled the 5L again.
-
He poured some of the contents of the 5L can into the 3L can to fill the
latter. Since the 3L can had only 2L in it
it could take 1 more litre
from the 5L can
leaving 4L of water in the 5L can and saving the city.
Now
your objective is to write a function DIEHARD(A
B
C
n) which takes
the following parameters :-
a) A = Capacity of can 1
b) B = Capacity of can 2
c) C = Amount required
d) n = Number of steps to do so
which will return -1 if it is possible to obtain C litres in one of
the two containers in "n" steps and 0 if it is not possible to do so.
Note
in the example of the movie above
Bruce Willis had A=5
B=3
C=4 and took n=6 steps.
The things you can do with your containers are :-
-
Fill A
-
Fill B
-
Empty A
-
Empty B
-
Pour the contents of A into B till B is full or A is empty
-
Pour the contents of B into A till A is full or B is empty
Also
you can assume that n<=5.
Sample Output
DIEHARD(3
2
2
1) should
return -1
DIEHARD(4
3
1
2) should
return -1
DIEHARD(4
4
1
5) should
return 0
DIEHARD(2
9
7
2) should
return -1
DIEHARD(2
9
5
5) should
return -1
NOTE: I couldn't find a particularly efficient algorithm for the above
program myself. (Output for some test data took upto 2 minutes!!) So if
you are able to create an efficient algorithm in Qbasic or C++ or Visual
Basic
please e-mail
it to me.
--Thanx
LinkExchange Member
