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 1 of 3  [1] 2 3  Next page →

#1170 — the hourglass problem

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)

ok, this is trivial.  But as computer nerds, we're
interested in general solutions.  So, given hourglasses
of n and m minutes:

1)  Can you devise a formula which generates a list of
  all possible intervals produced by them?

2)  And an algorithm, which generates the interval,
  for any given number on the list.

Of course, this is solvable via brute force, but we
want something efficient.

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

--
Rich

[toc] | [next] | [standalone]

#1171

On Sat, 31 Dec 2011, 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)
>
Can't be done without a setup.

> So, given hourglasses of n and m minutes:
>
> 1)  Can you devise a formula which generates a list of
>  all possible intervals produced by them?
>
> 2)  And an algorithm, which generates the interval,
>  for any given number on the list.
>
> Of course, this is solvable via brute force, but we
> want something efficient.
>
> PS The problem stated above is a Google interview question!
> Which lowers my estimate of their intellectual prowess.

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

#1172

On Dec 31, 9:21 pm, William Elliot <ma...@rdrop.com> wrote:
> On Sat, 31 Dec 2011, 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)
>
> Can't be done without a setup.

How about this: Start both timers. When the four-minute timer runs out
(at 4 minutes), turn it over. When the seven-minute timer runs out (at
7 minutes), turn it over. When the four-minute timer runs out again
(at 8 minutes), turn the seven-minute timer over. It will run out at 9
minutes.

Dave

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

#1178

[Multipart message — attachments visible in raw view] — view raw

On Sat, 31 Dec 2011, Dave Dodson wrote:
> On Dec 31, 9:21 pm, William Elliot <ma...@rdrop.com> wrote:
>> On Sat, 31 Dec 2011, 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)
>>
>> Can't be done without a setup.
>
> How about this: Start both timers. When the four-minute timer runs out
> (at 4 minutes), turn it over. When the seven-minute timer runs out (at
> 7 minutes), turn it over. When the four-minute timer runs out again
> (at 8 minutes), turn the seven-minute timer over. It will run out at 9
> minutes.

Beside having a set up period, I dispute its correctness.
Here's what I saw.

Set off 7 and 4, reset 4, reset 7, reset 4, reset 4.
Mark end of second 7 as start.  Forth 4 has two minutes
to go.  At end of forth 4, again set off 7.

As that had set up period of 14 minutes, it was discarded.

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

#1180

On 1/1/2012 7:48 PM, William Elliot wrote:
> On Sat, 31 Dec 2011, Dave Dodson wrote:
>> On Dec 31, 9:21 pm, William Elliot <ma...@rdrop.com> wrote:
>>> On Sat, 31 Dec 2011, 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)
>>>
>>> Can't be done without a setup.
>>
>> How about this: Start both timers. When the four-minute timer runs out
>> (at 4 minutes), turn it over. When the seven-minute timer runs out (at
>> 7 minutes), turn it over. When the four-minute timer runs out again
>> (at 8 minutes), turn the seven-minute timer over. It will run out at 9
>> minutes.
>
> Beside having a set up period, I dispute its correctness.
> Here's what I saw.
>
> Set off 7 and 4, reset 4, reset 7, reset 4, reset 4.
> Mark end of second 7 as start. Forth 4 has two minutes
> to go. At end of forth 4, again set off 7.

I don't think "reset" is an operation for a sand hourglass.
The operations are:

1. Turning it over.

2. Observing the sand finishing flowing from one chamber to the other.

> As that had set up period of 14 minutes, it was discarded.

Here's the 9 minute sequence from above, reformatted and with a little
more explanation:

Time 0: start both timers.
Time 4: four-minute timer expires, turn it over.
Time 7: seven-minute time expires, turn it over.
Time 8: four-minute time expires again. Turn over the seven-minute timer.
Time 9: The one-minute's worth of sand that had passed through the
seven-minute timer between Time 7 and Time 8 finishes flowing back, and
the seven-minute timer expires again.

This depends on the idea that if an M minute timer is started with all
the sand in one chamber, run for N<=M minutes, and then turned over, it
will expire in another N minutes.

Patricia

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

#1181

On Sun, 1 Jan 2012, Patricia Shanahan wrote:
> On 1/1/2012 7:48 PM, William Elliot wrote:
>> On Sat, 31 Dec 2011, Dave Dodson wrote:
>>> On Dec 31, 9:21 pm, William Elliot <ma...@rdrop.com> wrote:
>>>> On Sat, 31 Dec 2011, 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)
>>>> 
>>>> Can't be done without a setup.
>>> 
>>> How about this: Start both timers. When the four-minute timer runs out
>>> (at 4 minutes), turn it over. When the seven-minute timer runs out (at
>>> 7 minutes), turn it over. When the four-minute timer runs out again
>>> (at 8 minutes), turn the seven-minute timer over. It will run out at 9
>>> minutes.
>> 
>> Beside having a set up period, I dispute its correctness.
>> Here's what I saw.
>> 
>> Set off 7 and 4, reset 4, reset 7, reset 4, reset 4.
>> Mark end of second 7 as start. Forth 4 has two minutes
>> to go. At end of forth 4, again set off 7.
>
> I don't think "reset" is an operation for a sand hourglass.
> The operations are:
>
> 1. Turning it over.
> 2. Observing the sand finishing flowing from one chamber to the other.
>
>> As that had set up period of 14 minutes, it was discarded.
>
> Here's the 9 minute sequence from above, reformatted and with a little
> more explanation:
>
> Time 0: start both timers.
> Time 4: four-minute timer expires, turn it over.
> Time 7: seven-minute time expires, turn it over.

This is a 7 minute set up that's taken as the starting point.
The four minute timers has one more minute to go.  After it's
done restart it two times for a total of 9 minutes from the
starting point.

> Time 8: four-minute time expires again. Turn over the seven-minute timer.
> Time 9: The one-minute's worth of sand that had passed through the
> seven-minute timer between Time 7 and Time 8 finishes flowing back, and
> the seven-minute timer expires again.
>
> This depends on the idea that if an M minute timer is started with all
> the sand in one chamber, run for N<=M minutes, and then turned over, it
> will expire in another N minutes.
>
> Patricia
>

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

#1184

On 1/1/2012 11:08 PM, William Elliot wrote:
> On Sun, 1 Jan 2012, Patricia Shanahan wrote:
>> On 1/1/2012 7:48 PM, William Elliot wrote:
>>> On Sat, 31 Dec 2011, Dave Dodson wrote:
>>>> On Dec 31, 9:21 pm, William Elliot <ma...@rdrop.com> wrote:
>>>>> On Sat, 31 Dec 2011, 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)
>>>>>
>>>>> Can't be done without a setup.
>>>>
>>>> How about this: Start both timers. When the four-minute timer runs out
>>>> (at 4 minutes), turn it over. When the seven-minute timer runs out (at
>>>> 7 minutes), turn it over. When the four-minute timer runs out again
>>>> (at 8 minutes), turn the seven-minute timer over. It will run out at 9
>>>> minutes.
>>>
>>> Beside having a set up period, I dispute its correctness.
>>> Here's what I saw.
>>>
>>> Set off 7 and 4, reset 4, reset 7, reset 4, reset 4.
>>> Mark end of second 7 as start. Forth 4 has two minutes
>>> to go. At end of forth 4, again set off 7.
>>
>> I don't think "reset" is an operation for a sand hourglass.
>> The operations are:
>>
>> 1. Turning it over.
>> 2. Observing the sand finishing flowing from one chamber to the other.
>>
>>> As that had set up period of 14 minutes, it was discarded.
>>
>> Here's the 9 minute sequence from above, reformatted and with a little
>> more explanation:
>>
>> Time 0: start both timers.
>> Time 4: four-minute timer expires, turn it over.
>> Time 7: seven-minute time expires, turn it over.
>
> This is a 7 minute set up that's taken as the starting point.
> The four minute timers has one more minute to go. After it's
> done restart it two times for a total of 9 minutes from the
> starting point.

No, you need to continue with the specified sequence, which finishes in
9 minutes from the start.

I think you are ignoring two key features of a sand hourglass:

1. The sand flows at a more-or-less even rate if the top is not empty.

2. You can turn it over at any time, even if the top is not yet empty.

Suppose you start a M-minute timer (M>1) with all the sand in the top,
wait one minute, and then turn it over. The top now contains the amount
of sand that takes one minute to flow to the bottom, and it will empty
in one more minute.

>
>> Time 8: four-minute time expires again. Turn over the seven-minute timer.
>> Time 9: The one-minute's worth of sand that had passed through the
>> seven-minute timer between Time 7 and Time 8 finishes flowing back, and
>> the seven-minute timer expires again.
>>
>> This depends on the idea that if an M minute timer is started with all
>> the sand in one chamber, run for N<=M minutes, and then turned over, it
>> will expire in another N minutes.
>>
>> Patricia
>>

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

#1185

Patricia Shanahan <pats@acm.org> writes:

> I think you are ignoring two key features of a sand hourglass:
>
> 1. The sand flows at a more-or-less even rate if the top is not empty.
>
> 2. You can turn it over at any time, even if the top is not yet empty.
>
> Suppose you start a M-minute timer (M>1) with all the sand in the top,
> wait one minute, and then turn it over. The top now contains the amount
> of sand that takes one minute to flow to the bottom, and it will empty
> in one more minute.

While this is clearly the right answer to the puzzle I wonder how
accurate feature (1.) actually is.  Does anyone have - say - a three
minute egg timer to hand who'd try the actual experiment of running it
for one minute, reversing it and seeing how long it takes to return?

I'm not prepared to speculate on whether increased pressure might push
the sand through faster or make it pack together and flow less freely.
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

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

#1193

On Mon, 02 Jan 2012 16:17:55 +0000, Dr Nick
<3-nospam@temporary-address.org.uk> wrote:

>Patricia Shanahan <pats@acm.org> writes:
>
>> I think you are ignoring two key features of a sand hourglass:
>>
>> 1. The sand flows at a more-or-less even rate if the top is not empty.
>>
>> 2. You can turn it over at any time, even if the top is not yet empty.
>>
>> Suppose you start a M-minute timer (M>1) with all the sand in the top,
>> wait one minute, and then turn it over. The top now contains the amount
>> of sand that takes one minute to flow to the bottom, and it will empty
>> in one more minute.
>
>While this is clearly the right answer to the puzzle I wonder how
>accurate feature (1.) actually is.  Does anyone have - say - a three
>minute egg timer to hand who'd try the actual experiment of running it
>for one minute, reversing it and seeing how long it takes to return?
>
>I'm not prepared to speculate on whether increased pressure might push
>the sand through faster or make it pack together and flow less freely.


It's actually fairly accurate - (dry) sand isn't a fluid, and most of
the (solid) sand grains are held up by being stacked on top of other
(solid) sand grains.  The bits that fall are the ones that no longer
have any support, which are basically in a conical area with the base
over the hole in the neck of the hourglass (as those on the edges of
the cone fall, they open space above for more sand to shift down).

Now if the sand were not dry, or the grains weren't fairly consistent
in size or were excessively shaped to link to each other*, or the hole
was very small (or too large), you'd get more oddities in the flow
rates with changes in pressure.


*The quality of the "sand" is a significant issue in hourglass
accuracy (ideally you want smooth round grains of consistent size),
and many materials other than silica sand are used as well

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

#1188

On Dec 31 2011, 10:21 pm, William Elliot <ma...@rdrop.com> wrote:
> On Sat, 31 Dec 2011, 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)
>
> Can't be done without a setup.

Start both timers. When the four minute is halfway through, stop the
seven minute. Proceed pouring the rest of the seven when the four is
expired.

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

#1189

"Remysun" <remysun2000@yahoo.com> wrote in message 
news:ffe240d6-3b3d-4bbc-b891-7ec41dceb867@v13g2000yqc.googlegroups.com...
> On Dec 31 2011, 10:21 pm, William Elliot <ma...@rdrop.com> wrote:
>> On Sat, 31 Dec 2011, 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)
>>
>> Can't be done without a setup.
>
> Start both timers. When the four minute is halfway through

You can't do that. You don't know when it will be exactly half-way.

-- 
Bartc 

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

#1173

RichD <r_delaney2001@yahoo.com> 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)
> 
> ok, this is trivial.  But as computer nerds, we're
> interested in general solutions.  So, given hourglasses
> of n and m minutes:
> 
> 1)  Can you devise a formula which generates a list of
>   all possible intervals produced by them?
> 
> 2)  And an algorithm, which generates the interval,
>   for any given number on the list.
> 
> Of course, this is solvable via brute force, but we
> want something efficient.
> 
> PS  The problem stated above is a Google
> interview question!  Which lowers my estimate of
> their intellectual prowess.
> 
> --
> Rich

This problem is very interesting. After you realize
how to get 9 minutes, you then realize you are
able to get 4 minutes, 7 minutes, and then every
integer minute thereafter. So the numbers realizable
without delay are:
4,7,8,9,10,11,12........

Then, clearly, with a 7 minute delay you can generate
every integer minute.

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

#1179

On Sun, 1 Jan 2012, root wrote:
> RichD <r_delaney2001@yahoo.com> 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)
>>
>> ok, this is trivial.  But as computer nerds, we're
>> interested in general solutions.  So, given hourglasses
>> of n and m minutes:
>>
>> 1)  Can you devise a formula which generates a list of
>>   all possible intervals produced by them?

> This problem is very interesting. After you realize
> how to get 9 minutes, you then realize you are
> able to get 4 minutes, 7 minutes, and then every
> integer minute thereafter. So the numbers realizable
> without delay are:
> 4,7,8,9,10,11,12........
>
How did you realize 9, 10 and 11 without any delay?

> Then, clearly, with a 7 minute delay you can generate
> every integer minute.

How can you generate 2 and 9 with only a 7 minute delay?

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

#1182

William Elliot <marsh@rdrop.com> wrote:

> On Sun, 1 Jan 2012, root wrote:
>> RichD <r_delaney2001@yahoo.com> 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)
>>>
>>> ok, this is trivial.  But as computer nerds, we're
>>> interested in general solutions.  So, given hourglasses
>>> of n and m minutes:
>>>
>>> 1)  Can you devise a formula which generates a list of
>>>   all possible intervals produced by them?
> 
>> This problem is very interesting. After you realize
>> how to get 9 minutes, you then realize you are
>> able to get 4 minutes, 7 minutes, and then every
>> integer minute thereafter. So the numbers realizable
>> without delay are:
>> 4,7,8,9,10,11,12........
>>
> How did you realize 9, 10 and 11 without any delay?

The solution for 9 has already been posted multiple times.

10 and 11 are simple extensions of the solution for 9:

start both timers (t=0)
turn over the 4 minute timer when it expires (t=4)
turn over the 7 minute timer when it expires (t=7)
turn over both timers when the 4 minute timer expires (t=8)
turn over both timers when the 7 minute timer expires (t=9)
turn over both timers when the 4 minute timer expires (t=10)
turn over both timers when the 7 minute timer expires (t=11)
... and keep on marking every minute from 7 until you get bored.

> 
>> Then, clearly, with a 7 minute delay you can generate
>> every integer minute.
> 
> How can you generate 2 and 9 with only a 7 minute delay?

Same way you generate 9 and 16 with no delay.



-- 
Duncan Booth

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

#1200

On Dec 31 2011,  root <NoEM...@home.org> 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)
>
> > this is trivial.
> > So, given hourglasses of n and m minutes:
>
> > 1)  Can you devise a formula which generates a list of
> >   all possible intervals produced by them?
>
> > 2)  And an algorithm, which generates the interval,
> >   for any given number on the list.
>
> > Of course, this is solvable via brute force, but we
> > want something efficient.
>
> This problem is very interesting. After you realize
> how to get 9 minutes, you then realize you are
> able to get 4 minutes, 7 minutes, and then every
> integer minute thereafter. So the numbers realizable
> without delay are:
> 4,7,8,9,10,11,
> Then, clearly, with a 7 minute delay you can generate
> every integer minute.

Good.

So, as soon as you construct a small differential
between the units, you can repeat that interval
indefinitely.  In this example, after 8 mintes, we
have a 1 minute timer, whcih can generate any
minute thereafter.

However, this isn't always possible.  Consider
any 2 even minute hourglasses - we cannot time
any odd length interval.  But is it guaranteed we
can eventually construct a 2 minute timer?

It seems that number theory must become a factor,
and prime numbers the key.

--
Rich

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

#1201

On 1/3/12 3:05 PM, RichD wrote:
> On Dec 31 2011,  root<NoEM...@home.org>  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)
>>
>>> this is trivial.
>>> So, given hourglasses of n and m minutes:
>>
>>> 1)  Can you devise a formula which generates a list of
>>>    all possible intervals produced by them?
>>
>>> 2)  And an algorithm, which generates the interval,
>>>    for any given number on the list.
>>
>>> Of course, this is solvable via brute force, but we
>>> want something efficient.
>>
>> This problem is very interesting. After you realize
>> how to get 9 minutes, you then realize you are
>> able to get 4 minutes, 7 minutes, and then every
>> integer minute thereafter. So the numbers realizable
>> without delay are:
>> 4,7,8,9,10,11,
>> Then, clearly, with a 7 minute delay you can generate
>> every integer minute.
>
> Good.
>
> So, as soon as you construct a small differential
> between the units, you can repeat that interval
> indefinitely.  In this example, after 8 mintes, we
> have a 1 minute timer, whcih can generate any
> minute thereafter.
>
> However, this isn't always possible.  Consider
> any 2 even minute hourglasses - we cannot time
> any odd length interval.  But is it guaranteed we
> can eventually construct a 2 minute timer?
>
> It seems that number theory must become a factor,
> and prime numbers the key.

Without having done any analysis, I think specifically that the LCD is a 
key to the intervals, which may lead to the general solution.

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

#1214

On Jan 3, Daniel Pitts <newsgroup.nos...@virtualinfinity.net> 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)
>
> >>>this is trivial.
> >>> So, given hourglasses of n and m minutes:
> >>> 1)  Can you devise a formula which generates a list
> >>>   of all possible intervals produced by them?
> >>> 2)  And an algorithm, which generates the interval,
> >>>    for any given number on the list.
>
> >>> Of course, this is solvable via brute force, but we
> >>> want something efficient.
>
> >> This problem is very interesting. After you realize
> >> how to get 9 minutes, you then realize you are
> >> able to get 4 minutes, 7 minutes, and then every
> >> integer minute thereafter. So the numbers realizable
> >> without delay are:
> >> 4,7,8,9,10,11,
> >> Then, clearly, with a 7 minute delay you can generate
> >> every integer minute.
>
> > Good.
> > So, as soon as you construct a small differential
> > between the units, you can repeat that interval
> > indefinitely.  In this example, after 8 mintes, we
> > have a 1 minute timer, whcih can generate any
> > minute thereafter.
>
> > However, this isn't always possible.  Consider
> > any 2 even minute hourglasses - we cannot time
> > any odd length interval.  But is it guaranteed we
> > can eventually construct a 2 minute timer?
>
> > It seems that number theory must become a factor,
> > and prime numbers the key.
>
> Without having done any analysis, I think specifically
> that the LCD is a key to the intervals, which may lead
> to the general  solution.

LCD?

It strikes me as structurally similar to the knapsack
problem:  the hourglasses corrrespond to the
various size sticks.  It would be extremely
interesting, perhaps a new result, to demonstrate
an isomorphism, reducing any hourglass instance
to a knapsack problem.

Considering the amount of work done in this area,
if this hourglass thing really is NP-complete, I
suspect someone would have discovered it
heretofore -


---
Paul T.

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

#1215

On 1/4/12 12:28 PM, PT wrote:
> On Jan 3, Daniel Pitts<newsgroup.nos...@virtualinfinity.net>  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)
>>
>>>>> this is trivial.
>>>>> So, given hourglasses of n and m minutes:
>>>>> 1)  Can you devise a formula which generates a list
>>>>>    of all possible intervals produced by them?
>>>>> 2)  And an algorithm, which generates the interval,
>>>>>     for any given number on the list.
>>
>>>>> Of course, this is solvable via brute force, but we
>>>>> want something efficient.
>>
>>>> This problem is very interesting. After you realize
>>>> how to get 9 minutes, you then realize you are
>>>> able to get 4 minutes, 7 minutes, and then every
>>>> integer minute thereafter. So the numbers realizable
>>>> without delay are:
>>>> 4,7,8,9,10,11,
>>>> Then, clearly, with a 7 minute delay you can generate
>>>> every integer minute.
>>
>>> Good.
>>> So, as soon as you construct a small differential
>>> between the units, you can repeat that interval
>>> indefinitely.  In this example, after 8 mintes, we
>>> have a 1 minute timer, whcih can generate any
>>> minute thereafter.
>>
>>> However, this isn't always possible.  Consider
>>> any 2 even minute hourglasses - we cannot time
>>> any odd length interval.  But is it guaranteed we
>>> can eventually construct a 2 minute timer?
>>
>>> It seems that number theory must become a factor,
>>> and prime numbers the key.
>>
>> Without having done any analysis, I think specifically
>> that the LCD is a key to the intervals, which may lead
>> to the general  solution.
>
> LCD?
>
> It strikes me as structurally similar to the knapsack
> problem:  the hourglasses corrrespond to the
> various size sticks.  It would be extremely
> interesting, perhaps a new result, to demonstrate
> an isomorphism, reducing any hourglass instance
> to a knapsack problem.
>
> Considering the amount of work done in this area,
> if this hourglass thing really is NP-complete, I
> suspect someone would have discovered it
> heretofore -
>
>
> ---
> Paul T.

I doubt it is isomorphic to the knapsack problem, because you can "cut" 
any one length of time by a multiple of the other length of time.

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

#1216

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

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

#1217

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"

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

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.programming

csiph-web