Let's reconsider the problem of retreating from Iraq, with a twist.
Grace to new technology, teleconferencing is now possible. All direct
subordinates of any officer can be called SIMULTANEOUSLY. So there is no
more need for one officer to call each subordinate in sequence; he or she will call them all at once. Cool!

However, now the demands also increased. Your task, should you yadda
yadda, is to devise a schedule for teleconferenced such that EVERY rank
and file soldier finds the news at EXACTLY the same time. That means you
must insert some delays in the system. However, you should insert as few
delays as possible, and also to ensure there is minimal global delay
from the moment the President picks up the phone to the moment soldiers
get the news.

Be warned: this is quite a different problem than the previous one in
spite of the similarities. You may want to start from scratch instead of
adapting an algorithm suitable for the previous problem.


Good luck!

Andrei

Andrei Alexandrescu wrote:
> Let's reconsider the problem of retreating from Iraq, with a twist.
> Grace to new technology, teleconferencing is now possible. All direct
> subordinates of any officer can be called SIMULTANEOUSLY. So there is no
> more need for one officer to call each subordinate in sequence; he or she will call them all at once. Cool!
> 
> However, now the demands also increased. Your task, should you yadda
> yadda, is to devise a schedule for teleconferenced such that EVERY rank
> and file soldier finds the news at EXACTLY the same time. That means you
> must insert some delays in the system. However, you should insert as few
> delays as possible, and also to ensure there is minimal global delay
> from the moment the President picks up the phone to the moment soldiers
> get the news.
> 
> Be warned: this is quite a different problem than the previous one in
> spite of the similarities. You may want to start from scratch instead of
> adapting an algorithm suitable for the previous problem.
> 
> 
> Good luck!
> 
> Andrei

Hmmmmmm. Does each officer have the *option* of calling subordinates at different times? Can an officer have a conference call with all of his subordinates who have subordinates of their own, delaying a call with the leaf-node privates until later? If not, I can't imagine there's any generalizable solution...

--benji

Benji Smith wrote:
> Andrei Alexandrescu wrote:
>> Let's reconsider the problem of retreating from Iraq, with a twist.
>> Grace to new technology, teleconferencing is now possible. All direct
>> subordinates of any officer can be called SIMULTANEOUSLY. So there is no
>> more need for one officer to call each subordinate in sequence; he or she will call them all at once. Cool!
>>
>> However, now the demands also increased. Your task, should you yadda
>> yadda, is to devise a schedule for teleconferenced such that EVERY rank
>> and file soldier finds the news at EXACTLY the same time. That means you
>> must insert some delays in the system. However, you should insert as few
>> delays as possible, and also to ensure there is minimal global delay
>> from the moment the President picks up the phone to the moment soldiers
>> get the news.
>>
>> Be warned: this is quite a different problem than the previous one in
>> spite of the similarities. You may want to start from scratch instead of
>> adapting an algorithm suitable for the previous problem.
>>
>>
>> Good luck!
>>
>> Andrei
> 
> Hmmmmmm. Does each officer have the *option* of calling subordinates at different times? Can an officer have a conference call with all of his subordinates who have subordinates of their own, delaying a call with the leaf-node privates until later? If not, I can't imagine there's any generalizable solution...

Each officer can only wait for a specified time before calling all direct subordinates. You need to figure out how long each officer waits.

Andrei

Andrei Alexandrescu wrote:
> Benji Smith wrote:
>> Andrei Alexandrescu wrote:
>>> Let's reconsider the problem of retreating from Iraq, with a twist.
>>> Grace to new technology, teleconferencing is now possible. All direct
>>> subordinates of any officer can be called SIMULTANEOUSLY. So there is no
>>> more need for one officer to call each subordinate in sequence; he or she will call them all at once. Cool!
>>>
>>> However, now the demands also increased. Your task, should you yadda
>>> yadda, is to devise a schedule for teleconferenced such that EVERY rank
>>> and file soldier finds the news at EXACTLY the same time. That means you
>>> must insert some delays in the system. However, you should insert as few
>>> delays as possible, and also to ensure there is minimal global delay
>>> from the moment the President picks up the phone to the moment soldiers
>>> get the news.
>>>
>>> Be warned: this is quite a different problem than the previous one in
>>> spite of the similarities. You may want to start from scratch instead of
>>> adapting an algorithm suitable for the previous problem.
>>>
>>>
>>> Good luck!
>>>
>>> Andrei
>>
>> Hmmmmmm. Does each officer have the *option* of calling subordinates at different times? Can an officer have a conference call with all of his subordinates who have subordinates of their own, delaying a call with the leaf-node privates until later? If not, I can't imagine there's any generalizable solution...
> 
> Each officer can only wait for a specified time before calling all direct subordinates. You need to figure out how long each officer waits.

Rats, I'm wrong (Sean just explained me over Skype). Yes, an officer can insert delays in calling certain subordinates.

Andrei

You want to destroy all life on Earth. However, you don't want people panicking as this could alter the result, so you want all humans to die at the same instant. To do this, you're creating nano-robots. A single nano-robot cannot control a persons mind: Seven are required (three in each half of the brain and one in the brain stem). Nano-robots can harvest material from their host to build new nano-robots, but the host will die after approximately twenty nano-robots-worth of material has been harvested (they require particular rare particles that can only be harvested from the heart and lungs). Nano-robots may communicate with one-another via broadcast, but the range is limited to 1 mile. Nano-robots do not have unique identification globally, but do have unique identification within a body (that is, nano-robots in the same body can distinguish each other, but broadcast messages from a nano-robot in one human cannot implicitly be distinguished from broadcasts from another). These broadcasts travel at the speed of light (seeing as that they are light). Nano-robots harvest energy from their host, and as such can survive indefinitely. A nano-robot in a dead host survives long enough that this variable is not relevant for this problem.

Robots can only be spread by direct physical contact from an infected host to an uninfected one, and the process of transferring one nano-robot destroys two nano-robots (that is, the infected host loses three robots in the process but the new host only gains one).

Devise an algorithm for these nano-robots that will destroy all human life on Earth in a minimum amount of time, but with which all humans will be destroyed within five minutes of each other. That is, minimize the time from deploying the first nano-robot to the initial human life being exterminated, and minimize the time from the initial human life being exterminated to all human life being exterminated. You may assume a maximum of twelve degrees of separation between average industrialized people and that even the most remote tribe is connected by at least one human to the industrialized world.

Bonus: How would you change this algorithm if you wanted to destroy all animal life? All life? How would you change it if astronauts were considered?

 - Gregor Richards

Hello Gregor,

> You want to destroy all life on Earth. However, you don't want people
> panicking as this could alter the result, so you want all humans to
> die at the same instant. To do this, you're creating nano-robots. A
> single nano-robot cannot control a persons mind: Seven are required
> (three in each half of the brain and one in the brain stem).
> Nano-robots can harvest material from their host to build new
> nano-robots, but the host will die after approximately twenty
> nano-robots-worth of material has been harvested (they require
> particular rare particles that can only be harvested from the heart
> and lungs). Nano-robots may communicate with one-another via
> broadcast, but the range is limited to 1 mile. Nano-robots do not have
> unique identification globally, but do have unique identification
> within a body (that is, nano-robots in the same body can distinguish
> each other, but broadcast messages from a nano-robot in one human
> cannot implicitly be distinguished from broadcasts from another).
> These broadcasts travel at the speed of light (seeing as that they are
> light). Nano-robots harvest energy from their host, and as such can
> survive indefinitely. A nano-robot in a dead host survives long enough
> that this variable is not relevant for this problem.
> 
> Robots can only be spread by direct physical contact from an infected
> host to an uninfected one, and the process of transferring one
> nano-robot destroys two nano-robots (that is, the infected host loses
> three robots in the process but the new host only gains one).
> 
> Devise an algorithm for these nano-robots that will destroy all human
> life on Earth in a minimum amount of time, but with which all humans
> will be destroyed within five minutes of each other. That is, minimize
> the time from deploying the first nano-robot to the initial human life
> being exterminated, and minimize the time from the initial human life
> being exterminated to all human life being exterminated. You may
> assume a maximum of twelve degrees of separation between average
> industrialized people and that even the most remote tribe is connected
> by at least one human to the industrialized world.
> 
> Bonus: How would you change this algorithm if you wanted to destroy
> all animal life? All life? How would you change it if astronauts were
> considered?
> 
> - Gregor Richards
> 


Ok, Gregor.  I'll bite.  What's your fascination with this problem?  Are you trying to make a point about something?

If "yes", you may as well be direct about it.  If "no", then why the thread hijacking?  Come on... help me out... I'm a little slow sometimes. :) 

-JJR

John Reimer wrote:
> Hello Gregor,
> 
>> You want to destroy all life on Earth. However, you don't want people
>> panicking as this could alter the result, so you want all humans to
>> die at the same instant. To do this, you're creating nano-robots. A
>> single nano-robot cannot control a persons mind: Seven are required
>> (three in each half of the brain and one in the brain stem).
>> Nano-robots can harvest material from their host to build new
>> nano-robots, but the host will die after approximately twenty
>> nano-robots-worth of material has been harvested (they require
>> particular rare particles that can only be harvested from the heart
>> and lungs). Nano-robots may communicate with one-another via
>> broadcast, but the range is limited to 1 mile. Nano-robots do not have
>> unique identification globally, but do have unique identification
>> within a body (that is, nano-robots in the same body can distinguish
>> each other, but broadcast messages from a nano-robot in one human
>> cannot implicitly be distinguished from broadcasts from another).
>> These broadcasts travel at the speed of light (seeing as that they are
>> light). Nano-robots harvest energy from their host, and as such can
>> survive indefinitely. A nano-robot in a dead host survives long enough
>> that this variable is not relevant for this problem.
>>
>> Robots can only be spread by direct physical contact from an infected
>> host to an uninfected one, and the process of transferring one
>> nano-robot destroys two nano-robots (that is, the infected host loses
>> three robots in the process but the new host only gains one).
>>
>> Devise an algorithm for these nano-robots that will destroy all human
>> life on Earth in a minimum amount of time, but with which all humans
>> will be destroyed within five minutes of each other. That is, minimize
>> the time from deploying the first nano-robot to the initial human life
>> being exterminated, and minimize the time from the initial human life
>> being exterminated to all human life being exterminated. You may
>> assume a maximum of twelve degrees of separation between average
>> industrialized people and that even the most remote tribe is connected
>> by at least one human to the industrialized world.
>>
>> Bonus: How would you change this algorithm if you wanted to destroy
>> all animal life? All life? How would you change it if astronauts were
>> considered?
>>
>> - Gregor Richards
>>
> 
> 
> Ok, Gregor.  I'll bite.  What's your fascination with this problem?  Are you trying to make a point about something?
> 
> If "yes", you may as well be direct about it.  If "no", then why the thread hijacking?  Come on... help me out... I'm a little slow sometimes. :)
> -JJR
> 
> 

Thread hijacking? Seriously? This isn't a forum, there are totally disconnected subthreads within any thread.

This is what we call a "joke". On the one hand it's a parody of the always-annoying real-life-algorithm thread, on the other hand it's a parody of the needlessly-loaded choice of settings for the oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This problem could be formalized as a simple tree-based message-passing communication problem, but instead we've gone political. Well, so long as war is involved, let's step it up and destroy everything. Yeeee haw.

 - Gregor Richards

"Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:gd6ifg$8g3$3@digitalmars.com...
> Let's reconsider the problem of retreating from Iraq, with a twist. Grace to new technology, teleconferencing is now possible. All direct subordinates of any officer can be called SIMULTANEOUSLY. So there is no more need for one officer to call each subordinate in sequence; he or she will call them all at once. Cool!
>
> However, now the demands also increased. Your task, should you yadda yadda, is to devise a schedule for teleconferenced such that EVERY rank and file soldier finds the news at EXACTLY the same time. That means you must insert some delays in the system. However, you should insert as few delays as possible, and also to ensure there is minimal global delay from the moment the President picks up the phone to the moment soldiers get the news.
>
> Be warned: this is quite a different problem than the previous one in spite of the similarities. You may want to start from scratch instead of adapting an algorithm suitable for the previous problem.
>

Can a subordinate initiate a call to a superior?

Hello Gregor,

> John Reimer wrote:
> 
>> Hello Gregor,
>> 
>>> You want to destroy all life on Earth. However, you don't want
>>> people panicking as this could alter the result, so you want all
>>> humans to die at the same instant. To do this, you're creating
>>> nano-robots. A single nano-robot cannot control a persons mind:
>>> Seven are required (three in each half of the brain and one in the
>>> brain stem). Nano-robots can harvest material from their host to
>>> build new nano-robots, but the host will die after approximately
>>> twenty nano-robots-worth of material has been harvested (they
>>> require particular rare particles that can only be harvested from
>>> the heart and lungs). Nano-robots may communicate with one-another
>>> via broadcast, but the range is limited to 1 mile. Nano-robots do
>>> not have unique identification globally, but do have unique
>>> identification within a body (that is, nano-robots in the same body
>>> can distinguish each other, but broadcast messages from a nano-robot
>>> in one human cannot implicitly be distinguished from broadcasts from
>>> another). These broadcasts travel at the speed of light (seeing as
>>> that they are light). Nano-robots harvest energy from their host,
>>> and as such can survive indefinitely. A nano-robot in a dead host
>>> survives long enough that this variable is not relevant for this
>>> problem.
>>> 
>>> Robots can only be spread by direct physical contact from an
>>> infected host to an uninfected one, and the process of transferring
>>> one nano-robot destroys two nano-robots (that is, the infected host
>>> loses three robots in the process but the new host only gains one).
>>> 
>>> Devise an algorithm for these nano-robots that will destroy all
>>> human life on Earth in a minimum amount of time, but with which all
>>> humans will be destroyed within five minutes of each other. That is,
>>> minimize the time from deploying the first nano-robot to the initial
>>> human life being exterminated, and minimize the time from the
>>> initial human life being exterminated to all human life being
>>> exterminated. You may assume a maximum of twelve degrees of
>>> separation between average industrialized people and that even the
>>> most remote tribe is connected by at least one human to the
>>> industrialized world.
>>> 
>>> Bonus: How would you change this algorithm if you wanted to destroy
>>> all animal life? All life? How would you change it if astronauts
>>> were considered?
>>> 
>>> - Gregor Richards
>>> 
>> Ok, Gregor.  I'll bite.  What's your fascination with this problem?
>> Are you trying to make a point about something?
>> 
>> If "yes", you may as well be direct about it.  If "no", then why the
>> thread hijacking?  Come on... help me out... I'm a little slow
>> sometimes. :)
>> -JJR
> Thread hijacking? Seriously? This isn't a forum, there are totally
> disconnected subthreads within any thread.
> 


Or whatever... thread "detracting" perhaps is a better term. 


> This is what we call a "joke". On the one hand it's a parody of the
> always-annoying real-life-algorithm thread, on the other hand it's a
> parody of the needlessly-loaded choice of settings for the
> oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This
> problem could be formalized as a simple tree-based message-passing
> communication problem, but instead we've gone political. Well, so long
> as war is involved, let's step it up and destroy everything. Yeeee
> haw.
> 
> - Gregor Richards
> 


Ok, that's better.  Thanks for clarifying.  Actually, I didn't find it near as annoying as you did, but I do agree that it was getting a little too close to a political tune on something that is very likely a touchy subject... good call.

-JJR

Hello Gregor,


> This is what we call a "joke". 

Yet... if it is just a "joke", that implies you are not serious... and yet I do think your parody is meant to make a statement beyond just a "joke". Sorry, I think it's fair to hold you accountable for your "jokes". :)  In short, it's not a joke then.

Your parody and strong statement of annoyance appear to have been meant to "educate" the community. 

-JJR