Hour Glass - Euclid Algorithm
Source: Quora - Asked in a Google Interview
Problem:
Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes–without the process taking longer than nine minutes.
Bonus made-up Question: Can you come up with a generalized solution of the hour glass problem?
This is a more involved version of the "Die Hard III Problem: A classic water bottle riddle. How to produce exactly 4 gallons with a 3 and a 5 gallon pan" whose solution can be found here
Update: (26/12/2012):
Assume that equal amount of sand slipped down measures equal intervals of time, i.e. amount of sand slipped to measure the first minute is same as the last minute.
Solution posted by Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Mohit Johari (Civil IITB 2011 Alumnus) , Nikhil Simha R (Amazon India SDE, CSE IITB 2012 Alumnus) and Sravan Kumar (EE IITB Final Year Student) in comments!
Problem:
Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes–without the process taking longer than nine minutes.
Bonus made-up Question: Can you come up with a generalized solution of the hour glass problem?
This is a more involved version of the "Die Hard III Problem: A classic water bottle riddle. How to produce exactly 4 gallons with a 3 and a 5 gallon pan" whose solution can be found here
Update: (26/12/2012):
Assume that equal amount of sand slipped down measures equal intervals of time, i.e. amount of sand slipped to measure the first minute is same as the last minute.
Solution posted by Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Mohit Johari (Civil IITB 2011 Alumnus) , Nikhil Simha R (Amazon India SDE, CSE IITB 2012 Alumnus) and Sravan Kumar (EE IITB Final Year Student) in comments!
Ok
ReplyDelete1) Start at both hourglasses to sand on one side
2) Start them at the same time
3) After 4 minutes are over, immediately flip the 4 minutes hourglass to keep the sand flowing,
4) After the 7th minute is over immediately switch the 7 minute hourglass to keep the sand flowing
5) After the 8th minute is over [4 minute hourglass is emptied the second time], flip the 7 minute hour glass {because it has 1 minute worth sand on one side and 6 minute on the other}
6) After the 7 minute hour glass is empty on the top, smile.
4 min : A , 7 min : B
ReplyDeletewe start with both hourglass..
after 4 mins from start A empties.. B has 3 min to go.. flip A.
after 7 min from start B empties .. A has 1 min to go.. flip B
after 8 min from start A empties .. B has 6 min to go.. so it has emptied by 1 min..flip B
after 9 min from start B also empties..
t | 7min-glass | 4min-glass
ReplyDelete0 | 7|0 | 4|0
4 | 3|4 | 0|4 => 4|0
7 | 0|7=>7|0 | 1|3
8 | 6|1=>1|6 | 0|4
9 | 0|7 | 0|4
and done!
one can model this as a graph search where nodes are states where one or more of the hour glasses finished counting and possible children would be flipping any of the hour glasses.
If one is worried about memory one can use A*.
But if one is worried about the shortest path, BFS is the obvious solution.
This solution is just for the 4,7 case.
ReplyDeleteLet h4 , h7 be the four and seven minute hourglasses resp.
Initially h4, h7 have sand completely emptied into the bottom half.
At t=0 flip both h4 and h7
Flip h4 when it completely empties (This will be at t=4)
Flip h7 when it completely empties (This will be at t=7. By this time h4 will have 1 minute worth of sand in the top half)
Flip h7 when h4 empties completely (This will be at t=8. By this time h7 will have 1 minute worth of sand in the top half, i.e., after flipping)
At t=9 h7 completely empties into the bottom half
This comment has been removed by the author.
ReplyDeleteThe earlier post had a few lines missing. This is the complete one
ReplyDeleteWe have hourglasses that can measure the times t1, t2, t3, ..., tn. The following steps are to calculate all the measurable times
We define a series of times that can be measured xi, and then, for each time, we calculate a new set of incremental times that can be measured yi,j as follows:
The initial set of incremental times, y0,j is exactly tj. These sets will be ordered so that yi,j <= yi,k for j= 2*yi,1){ yi+1,j= yi,j-yi,1}
for(all j | yi,j < 2* yi,1 <= yi,j+1){ yi+1,j= yi,1}
We are taking the list of incremental times and subtracting the shortest measurable time from everything except for itself, then sorting the list.
For every time xi and every 0 < j <= n, it is possible to measure all times xi+yi,j.
For example, with 4 and 7 minute hourglasses, we get the following:
i: xi: yi,j
0: 0 min: 4, 7
1: 4 min: 3, 4
2: 7 min: 1, 3
3: 8 min: 1, 2
4: 9 min: 1, 1
5: 10 min: 1
So on..
This can be thought of as finding gcd of two numbers using subtration. For example, to find gcd of n1=24 and n2=16, diff = 8, now, n1=16 and n2=8, diff = 0. Hence, gcd is 8. In case of 4 and 7 gcd is 1. Note that if gcd is 1 then it can be used to measure any number greater than n1(n1>n2). In this case, we can measure any time from 8 to infinity. Just, keep flipping and counting 1 till you get the desired number.
ReplyDeleteOtherwise, if gcd is not 1, then one only those numbers which are of kind gcd*(a*n1+b*n2) can be counted, where a and b are appropriate integters
@Asheesh
ReplyDeleteHow do you measure 14 minutes in 14 minutes with a 11 and a 13 minutes hour glass.
Your logic of measuring 'Z' with X, Y as long as (X,Y)| Z is correct...
but what is the criteria for measure Z in Z minutes
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete@Gold and Iron (Nikhil Pandey), @Mohit Johari, @Nikhil Simha R, @Sravan - Thanks for the correct solution
ReplyDelete@Sravan. Thanks for the attempt for generalised solution. Looks like its solution is not very "beautiful". Thanks anyways.
@Asheesh. Your solution is not correct as mentioned by @Pandey
@Vivek.. Your point is valid. Clearly posting the assumption in the problem.
If the two hour-glasses are of form (p1,p2) = (p,kp+1) or (p,kp-1) it is easy to measure any value >p2
ReplyDeletecase (p.kp+1)
after kp time:
top half of p1: 0, p2:1
flip p1
after kp+1 time:
top half of p1: p-1, p2:0
flip p1,p2
after kp+2 time
top half of p1: 0, p2: p2-1
and so on
similar solution for (p1,p2) = (p,kp-1)
Super cool! Thanks
DeleteHow will you measure 25 from (11,23)?
DeleteI think only those times are measurable which is of the form t = m*p1 + n*p2 (m,n belongs to Z) and t > max{ -m*p1 , -n*p2} [In case m or n is negative]. So if gcd is of p1 and p2 is 1 , there exists a t' such that all t > t' are measurable. (This requires a proof and we need to find that smallest number. In general case also by some argument, we should be able to show that there exists a t' s.t. all numbers t'+a*d >=t' are measurable where d is gcd of p1 and p2.)
Delete9 is measurable since 9 = 4*4 - 7 and 9 > 7. 14 is not measurable from 11 and 13 since 14 = 11*6 - 13*4 and 14<52.