Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1170 > unrolled thread

the hourglass problem

Back to article view | Back to comp.programming

Contents

  the hourglass problem RichD <r_delaney2001@yahoo.com> - 2011-12-31 18:03 -0800
    Re: the hourglass problem William Elliot <marsh@rdrop.com> - 2011-12-31 19:21 -0800
      Re: the hourglass problem Dave Dodson <dave_and_darla@Juno.com> - 2011-12-31 19:41 -0800
        Re: the hourglass problem William Elliot <marsh@rdrop.com> - 2012-01-01 19:48 -0800
          Re: the hourglass problem Patricia Shanahan <pats@acm.org> - 2012-01-01 20:44 -0800
            Re: the hourglass problem William Elliot <marsh@rdrop.com> - 2012-01-01 23:08 -0800
              Re: the hourglass problem Patricia Shanahan <pats@acm.org> - 2012-01-02 07:55 -0800
                Re: the hourglass problem Dr Nick <3-nospam@temporary-address.org.uk> - 2012-01-02 16:17 +0000
                  Re: the hourglass problem Robert Wessel <robertwessel2@yahoo.com> - 2012-01-03 03:37 -0600
      Re: the hourglass problem Remysun <remysun2000@yahoo.com> - 2012-01-02 17:10 -0800
        Re: the hourglass problem "BartC" <bc@freeuk.com> - 2012-01-03 01:12 +0000
    Re: the hourglass problem root <NoEMail@home.org> - 2012-01-01 05:51 +0000
      Re: the hourglass problem William Elliot <marsh@rdrop.com> - 2012-01-01 20:04 -0800
        Re: the hourglass problem Duncan Booth <duncan.booth@invalid.invalid> - 2012-01-02 11:42 +0000
      Re: the hourglass problem RichD <r_delaney2001@yahoo.com> - 2012-01-03 15:05 -0800
        Re: the hourglass problem Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-03 15:19 -0800
          Re: the hourglass problem PT <ptanenbaum@consultant.com> - 2012-01-04 12:28 -0800
            Re: the hourglass problem Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-04 13:44 -0800
          Re: the hourglass problem Dave Dodson <dave_and_darla@Juno.com> - 2012-01-04 22:55 -0800
            Re: the hourglass problem Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-04 23:55 -0800
              Re: the hourglass problem "Harry Vaderchi" <admin@127.0.0.1> - 2012-01-05 10:06 +0000
                Re: the hourglass problem "BartC" <bc@freeuk.com> - 2012-01-05 13:44 +0000
                  Re: the hourglass problem Patricia Shanahan <pats@acm.org> - 2012-01-05 08:13 -0800
                    Re: the hourglass problem Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-05 11:55 -0800
                      Re: the hourglass problem JohnF <john@please.see.sig.for.email.com> - 2012-01-06 04:40 +0000
              Re: the hourglass problem Dave <dave_and_darla@Juno.com> - 2012-01-05 15:37 -0800
                Re: the hourglass problem Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-05 16:02 -0800
    Re: the hourglass problem Duncan Booth <duncan.booth@invalid.invalid> - 2012-01-02 11:50 +0000
    Re: the hourglass problem Frederick Williams <freddywilliams@btinternet.com> - 2012-01-02 17:18 +0000
      Re: the hourglass problem msb@vex.net (Mark Brader) - 2012-01-02 17:40 -0600
        Re: the hourglass problem RichD <r_delaney2001@yahoo.com> - 2012-01-02 17:37 -0800
          Re: the hourglass problem msb@vex.net (Mark Brader) - 2012-01-02 23:45 -0600
          Re: the hourglass problem "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2012-01-03 10:06 +0100
          Re: the hourglass problem Thomas Mlynarczyk <thomas@mlynarczyk-webdesign.de> - 2012-01-03 12:51 +0100
            Re: the hourglass problem Nicolas Neuss <lastname@scipolis.de> - 2012-01-03 18:07 +0100
              Re: the hourglass problem Thomas Mlynarczyk <thomas@mlynarczyk-webdesign.de> - 2012-01-03 21:58 +0100
          Re: the hourglass problem Frederick Williams <freddywilliams@btinternet.com> - 2012-01-03 13:22 +0000
        Re: the hourglass problem "BartC" <bc@freeuk.com> - 2012-01-03 12:59 +0000
      Re: the hourglass problem Thomas Mlynarczyk <thomas@mlynarczyk-webdesign.de> - 2012-01-03 12:47 +0100
    Re: the hourglass problem Frederick Williams <freddywilliams@btinternet.com> - 2012-01-05 14:09 +0000
      Re: the hourglass problem Patricia Shanahan <pats@acm.org> - 2012-01-05 08:17 -0800
        Re: the hourglass problem Frederick Williams <freddywilliams@btinternet.com> - 2012-01-05 16:27 +0000
        Re: the hourglass problem Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-05 11:57 -0800
        Re: the hourglass problem JohnF <john@please.see.sig.for.email.com> - 2012-01-06 06:42 +0000

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#1218

On Thu, 05 Jan 2012 07:55:15 -0000, Daniel Pitts  
<newsgroup.nospam@virtualinfinity.net> wrote:

> On 1/4/12 10:55 PM, Dave Dodson wrote:
>> On Jan 3, 5:19 pm, Daniel Pitts<newsgroup.nos...@virtualinfinity.net>
>> wrote:
>>
>>> Without having done any analysis, I think specifically that the LCD is  
>>> a
>>> key to the intervals, which may lead to the general solution.
>>
>> It is probably the GCD, not the LCD. GCD(4,7) = 1, meaning that you
>> can hit every integer beyond a certain one, in this case beyond 6.
>>
>> If the GCD(t1,t2) = 2, e.g., then you won't be able to hit any odd
>> integers. Etc.
>>
>> Dave
> Indeed, I meant GCD, though I typed the wrong thing :-) Thanks for the  
> correction.
>
> Although, I don't see how you would get 6 with 4 and 7.  The possible  
> values are 4,7,8,9...
>
> Another potentially interesting problem would be "how to get to n with  
> the fewest turns"
>
7-4=3
twice 3 is 6.

HTH

-- 
[dash dash space newline 4line sig]

Albi CNU

[toc] | [prev] | [next] | [standalone]

#1219

"Harry Vaderchi" <admin@127.0.0.1> wrote in message 
news:op.v7lvoebf1r0rdn@dell3100...
> On Thu, 05 Jan 2012 07:55:15 -0000, Daniel Pitts 
> <newsgroup.nospam@virtualinfinity.net> wrote:

>> Although, I don't see how you would get 6 with 4 and 7.  The possible 
>> values are 4,7,8,9...
>>
>> Another potentially interesting problem would be "how to get to n with 
>> the fewest turns"
>>
> 7-4=3
> twice 3 is 6.

If you're stilling talking about hourglasses, then yes the difference the 4 
minute and 7 minute timers is 3 minutes.

But to get 6 minutes, you might have to start the process again, and you 
will get the second 3 minutes starting 4 minutes later.

So not only has the '6' minutes actually taken 10 (try using that to boil an 
egg), but there was a setup time of 4 minutes. A long time to wait for 
breakfast.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#1221

BartC wrote:
> 
> 
> "Harry Vaderchi" <admin@127.0.0.1> wrote in message 
> news:op.v7lvoebf1r0rdn@dell3100...
>> On Thu, 05 Jan 2012 07:55:15 -0000, Daniel Pitts 
>> <newsgroup.nospam@virtualinfinity.net> wrote:
> 
>>> Although, I don't see how you would get 6 with 4 and 7.  The possible 
>>> values are 4,7,8,9...
>>>
>>> Another potentially interesting problem would be "how to get to n 
>>> with the fewest turns"
>>>
>> 7-4=3
>> twice 3 is 6.
> 
> If you're stilling talking about hourglasses, then yes the difference 
> the 4 minute and 7 minute timers is 3 minutes.
> 
> But to get 6 minutes, you might have to start the process again, and you 
> will get the second 3 minutes starting 4 minutes later.

No. When four minute timer expires, turn it over and declare the start
of the six minute period. When the seven minute timer expires, the four
minute timer has three minutes worth of sand in the lower chamber. Turn
it over to time the second three minutes.

You do have a four minute set-up period, which fails to follow the
original requirement of no set-up time, but it does get a continuous six
minutes.

> 
> So not only has the '6' minutes actually taken 10 (try using that to 
> boil an egg), but there was a setup time of 4 minutes. A long time to 
> wait for breakfast.
> 

[toc] | [prev] | [next] | [standalone]

#1224

On 1/5/12 8:13 AM, Patricia Shanahan wrote:
> BartC wrote:
>>
>>
>> "Harry Vaderchi" <admin@127.0.0.1> wrote in message
>> news:op.v7lvoebf1r0rdn@dell3100...
>>> On Thu, 05 Jan 2012 07:55:15 -0000, Daniel Pitts
>>> <newsgroup.nospam@virtualinfinity.net> wrote:
>>
>>>> Although, I don't see how you would get 6 with 4 and 7. The possible
>>>> values are 4,7,8,9...
>>>>
>>>> Another potentially interesting problem would be "how to get to n
>>>> with the fewest turns"
>>>>
>>> 7-4=3
>>> twice 3 is 6.
>>
>> If you're stilling talking about hourglasses, then yes the difference
>> the 4 minute and 7 minute timers is 3 minutes.
>>
>> But to get 6 minutes, you might have to start the process again, and
>> you will get the second 3 minutes starting 4 minutes later.
>
> No. When four minute timer expires, turn it over and declare the start
> of the six minute period. When the seven minute timer expires, the four
> minute timer has three minutes worth of sand in the lower chamber. Turn
> it over to time the second three minutes.
>
> You do have a four minute set-up period, which fails to follow the
> original requirement of no set-up time, but it does get a continuous six
> minutes.
>
Indeed, if you allow set-up, you can get every integer with 7 minute and 
4 minute times!

You could actually set-up once to get "one minute" left on either timer, 
and then from that point forward, you never need to set up again, for 
any other experiment.  Of course, for real-world applications having to 
"turn over two hourglasses" every minute (on the minute!) would be more 
distracting than helpful.  Hence my suggestion that the interesting 
problem is "using the fewest turns, how do you get 'n' minutes".  With 
or without set up is acceptable to me.

[toc] | [prev] | [next] | [standalone]

#1229

In sci.math Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
> [...] Hence my suggestion that the interesting problem is
> "using the fewest turns, how do you get 'n' minutes".

Not obvious that complexity theory (or accumulated error)
thrown into the "hourglass instruction set" really adds
anything of abstract interest. But it did originally seem
to me like the "language" might have interesting semantics
until someone pointed out you could measure four minutes
and then every minute after (and including) seven, with
just the 4- and 7-minute timers. So the "computable set"
of times is pretty trivial, being N\{1,2,3,5,6}.
    Is there any way to make it more interesting?
For example, suppose you're only allowed to reset the timer
after it runs out. Does that make the computable times
more interesting? Is there any way to make it more interesting?
    If so, then a question about the "algebra" occurred to me,
as follows. Suppose you have a set S1={k1,t1, k2,t2, ..., kn,tn}
meaning k1 hourglasses that time t1, ..., through kn that time tn.
And suppose that allows you to "compute" times T1={some set of times}.
Then T1 is the "semantics" of S1. And suppose you also have an
S2,T2. How do they (algebraically) combine? That is,
what's the T for S1\/S2 (the set-theoretic "or"), and
what's the T for S1/\S2 (the set-theoretic "and") of the S's?
And how do these T's relate to T1 and T2.
    Of course, you first need an instruction set that
gives rise to non-trivial T's (subsets of N) in the first place,
if that's possible. If not, is there some kind of
instruction set that does? I'd imagine so, but couldn't
figure out what to google.
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

[toc] | [prev] | [next] | [standalone]

#1227

On Jan 5, 1:55 am, Daniel Pitts <newsgroup.nos...@virtualinfinity.net>
wrote:
> On 1/4/12 10:55 PM, Dave Dodson wrote:> On Jan 3, 5:19 pm, Daniel Pitts<newsgroup.nos...@virtualinfinity.net>
> > wrote:
>
> >> Without having done any analysis, I think specifically that the LCD is a
> >> key to the intervals, which may lead to the general solution.
>
> > It is probably the GCD, not the LCD. GCD(4,7) = 1, meaning that you
> > can hit every integer beyond a certain one, in this case beyond 6.
>
> > If the GCD(t1,t2) = 2, e.g., then you won't be able to hit any odd
> > integers. Etc.
>
> > Dave
>
> Indeed, I meant GCD, though I typed the wrong thing :-) Thanks for the
> correction.
>
> Although, I don't see how you would get 6 with 4 and 7.  The possible
> values are 4,7,8,9...

"Beyond 6" does not include 6.

Dave

[toc] | [prev] | [next] | [standalone]

#1228

On 1/5/12 3:37 PM, Dave wrote:
> On Jan 5, 1:55 am, Daniel Pitts<newsgroup.nos...@virtualinfinity.net>
> wrote:
>> On 1/4/12 10:55 PM, Dave Dodson wrote:>  On Jan 3, 5:19 pm, Daniel Pitts<newsgroup.nos...@virtualinfinity.net>
>>> wrote:
>>
>>>> Without having done any analysis, I think specifically that the LCD is a
>>>> key to the intervals, which may lead to the general solution.
>>
>>> It is probably the GCD, not the LCD. GCD(4,7) = 1, meaning that you
>>> can hit every integer beyond a certain one, in this case beyond 6.
>>
>>> If the GCD(t1,t2) = 2, e.g., then you won't be able to hit any odd
>>> integers. Etc.
>>
>>> Dave
>>
>> Indeed, I meant GCD, though I typed the wrong thing :-) Thanks for the
>> correction.
>>
>> Although, I don't see how you would get 6 with 4 and 7.  The possible
>> values are 4,7,8,9...
>
> "Beyond 6" does not include 6.
>
> Dave
Ah, indeed.

[toc] | [prev] | [next] | [standalone]

#1183

RichD <r_delaney2001@yahoo.com> wrote:

> PS  The problem stated above is a Google
> interview question!  Which lowers my estimate of
> their intellectual prowess.

When I was being interviewed by Google they didn't ask me any questions 
like this one, but your generalized questions would be very much more the 
sort of thing they ask.

They are very keen on whiteboard coding questions so I wouldn't have been 
at all suprised if they had asked me "given two hourglasses of m and n 
minutes and a desired time t minutes write a function that would take the 
above as arguments and print out the required steps to reach the desired 
time."

-- 
Duncan Booth

[toc] | [prev] | [next] | [standalone]

#1186

RichD wrote:
> 
> You're given a 7 minute, and a 4 minute, sand
> hourglass.  Measure a 9 minute interval, in the first
> 9 minutes.  (no 'setup' period)

Take the 7 minute and 4 minute sand hourglasses to an hourglass shop. 
Trade them in for a 9 minute hourglass.

-- 
When a true genius appears in the world, you may know him by 
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[toc] | [prev] | [next] | [standalone]

#1187

Rich Delaney:
> > You're given a 7 minute, and a 4 minute, sand
> > hourglass.  Measure a 9 minute interval, in the first
> > 9 minutes.  (no 'setup' period)
 
Frederick Williams:
> Take the 7 minute and 4 minute sand hourglasses to an hourglass shop. 
> Trade them in for a 9 minute hourglass.

"If you don't time 9 minutes on your watch for me, I'll smash these
hourglasses into your face."
-- 
Mark Brader    |    "Have you got anything without Spam in it?"
Toronto        |    "Well, there's Spam, egg, sausage, and Spam.
msb@vex.net    |     That's not got *much* Spam in it."  --Monty Python

[toc] | [prev] | [next] | [standalone]

#1190

On Jan 2, m...@vex.net (Mark Brader) wrote:
> > > You're given a 7 minute, and a 4 minute, sand
> > > hourglass.  Measure a 9 minute interval, in the first
> > > 9 minutes.  (no 'setup' period)
>
> > Take the 7 minute and 4 minute sand hourglasses to
> > an hourglass shop.
> > Trade them in for a 9 minute hourglass.
>
> "If you don't time 9 minutes on your watch for me, I'll smash these
> hourglasses into your face."

Cute.

Do you remember the story of the mythical
chem student, who was given a barometer, and
asked to determine the height of a buildng?

--
Rich

[toc] | [prev] | [next] | [standalone]

#1191

Mark Brader:
> > "If you don't time 9 minutes on your watch for me, I'll smash these
> > hourglasses into your face."

Rich Delaney:
> Do you remember the story of the mythical
> chem student, who was given a barometer, and
> asked to determine the height of a buildng?

Well, duh -- where'd you think I got that from?
-- 
Mark Brader, Toronto, msb@vex.net
                     "sci fi: the plural of scum fum" -- Spider Robinson

[toc] | [prev] | [next] | [standalone]

#1192

On Mon, 2 Jan 2012 17:37:40 -0800 (PST), RichD wrote:

> On Jan 2, m...@vex.net (Mark Brader) wrote:

>> "If you don't time 9 minutes on your watch for me, I'll smash these
>> hourglasses into your face."
> 
> Cute.
> 
> Do you remember the story of the mythical
> chem student, who was given a barometer, and
> asked to determine the height of a buildng?

Wasn't it a thermometer and a stopwatch?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#1195

RichD schrieb:
>> "If you don't time 9 minutes on your watch for me, I'll smash these
>> hourglasses into your face."
> 
> Cute.
> 
> Do you remember the story of the mythical
> chem student, who was given a barometer, and
> asked to determine the height of a buildng?

Never heard of that one. So what did he do? "If you don't tell me the 
height of the building, I'll smash this barometer into your face"? Or 
did he drop it from the top and measure the time until it hit the ground 
and then compute the height from that?

Greetings,
Thomas


-- 
Ce n'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

[toc] | [prev] | [next] | [standalone]

#1198

Thomas Mlynarczyk <thomas@mlynarczyk-webdesign.de> writes:

> RichD schrieb:
>>> "If you don't time 9 minutes on your watch for me, I'll smash these
>>> hourglasses into your face."
>>
>> Cute.
>>
>> Do you remember the story of the mythical
>> chem student, who was given a barometer, and
>> asked to determine the height of a buildng?
>
> Never heard of that one. So what did he do? "If you don't tell me the
> height of the building, I'll smash this barometer into your face"? Or
> did he drop it from the top and measure the time until it hit the
> ground and then compute the height from that?

http://www.jokelibrary.net/education/physics2.html#finding_height_with_a_barometer

Nicolas

[toc] | [prev] | [next] | [standalone]

#1199

Nicolas Neuss schrieb:
  > 
http://www.jokelibrary.net/education/physics2.html#finding_height_with_a_barometer

Thanks :-)

Greetings,
Thomas

-- 
Ce n'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

[toc] | [prev] | [next] | [standalone]

#1197

RichD wrote:
 
> Do you remember the story of the mythical
> chem student, who was given a barometer, and
> asked to determine the height of a buildng?

Yes.  I heard the late Clement Freud recount it as if it were fact. 
Truth or myth, it's an entertaining story.

-- 
When a true genius appears in the world, you may know him by 
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[toc] | [prev] | [next] | [standalone]

#1196

"Mark Brader" <msb@vex.net> wrote in message 
news:7c2dnTN6lJrr3Z_SnZ2dnUVZ_jWdnZ2d@vex.net...
> Rich Delaney:
>> > You're given a 7 minute, and a 4 minute, sand
>> > hourglass.  Measure a 9 minute interval, in the first
>> > 9 minutes.  (no 'setup' period)
>
> Frederick Williams:
>> Take the 7 minute and 4 minute sand hourglasses to an hourglass shop.
>> Trade them in for a 9 minute hourglass.

That requires 'setup'. (But if the shop isn't too far, set the 7-minute one 
going as soon as you set off, and swap the 4-minute one for a 2-minute one 
in the shop. Set it going when the 7-minute one runs out.)

(Sorry can't see FW's actual post.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#1194

Frederick Williams schrieb:
> Take the 7 minute and 4 minute sand hourglasses to an hourglass shop. 
> Trade them in for a 9 minute hourglass.

... plus a 2 minute hourglass just to make the deal fair.

Greetings,
Thomas

-- 
Ce n'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

[toc] | [prev] | [next] | [standalone]

#1220

RichD wrote:
> 
> You're given a 7 minute, and a 4 minute, sand
> hourglass.  

What may one do with these hourglasses?  Turn them over, certainly, but
may one place them on their side so that they stop "ticking"?

-- 
When a true genius appears in the world, you may know him by 
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.programming

csiph-web