Reply to Benjamin,

> Reply to Andrei,
> 
>> Suppose that a miracle happen and the decision is taken at the
>> highest level to retreat all of US military presence from Iraq. That
>> will take a while, but sending the orders quickly is a must.
>> 
>> For utmost certainty, all orders are to be sent via phone and down
>> the command chain, and only to direct subordinates. Each officer has
>> a variable number of subordinates. Initially the president calls his
>> immediate subordinates, who call their immediate subordinates, etc.
>> Each call can be assumed to take the same amount of time.
>> 
>> Devise an algorithm that ensures every foot soldier gets the news as
>> quickly as possible, show it is correct, and show it is fast.
>> 
>> Andrei
>> 
> Sort everyone under you (directly or indirectly) by the number of
> subordinates they have. Pick the subordinate with the most
> subordinates and call the next man in line to them. remove every
> subordinate down that chain of command and repeat.
> 
> This assumes that the depth of command is more or less the same across
> the board.
> 

This is based on the ssumption that the people with the most subordinates need to get started first.

You want to destroy all life on Earth. 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).

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 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 the minimum amount of time. That is, minimize the time from deploying the first nano-robot to every human life being eliminated. 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?

 - Gregor Richards

Gregor Richards wrote:
> 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 nano-robots (that is, the infected host loses three robots in the process but the new host only gains one).

Clarification: Destroys /two/ nano-robots.

Andrei Alexandrescu wrote:
> Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.
> 
> For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.
> 
> Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.

Ah, we're finally getting into concurrent programming :-)  I'm sure the syntax could be made more D 2.0-like, but something like this should do the trick:

class Soldier
{
    Soldier[] subordinates;

    void notify()
    {
        foreach( s; subordinates )
            pool.add( &s.notify() );
        pool.add( &flee() );
    }

    void flee()
    {
        // make 'this' actually flee
    }
}

Assume 'pool' is a global thread pool with some number of worker threads proportional to the number of cores on the system.  This will issue instructions for all Soldiers to flee in an optimally parallel manner for the target system.


Sean

BCS wrote:
>> Sort everyone under you (directly or indirectly) by the number of
>> subordinates they have. Pick the subordinate with the most
>> subordinates and call the next man in line to them. remove every
>> subordinate down that chain of command and repeat.
>>
>> This assumes that the depth of command is more or less the same across
>> the board.
>>
> 
> This is based on the ssumption that the people with the most subordinates need to get started first.

But consider this case...

I have two subordinates: Dirk and Deek. Dirk has only one subordinate of his own, but Deek has three. It seems like I should call Deek first.

But what if Dirk's single subordinate has twenty subordinates of his own, which Deek's subordinates are leaf-nodes? In that case, it makes a whole lot more sense to call Dirk first.

So it seems essential to implement a cost function for each branch of the tree. Something more elaborate than just counting each person's subordinates.

But a weighted-subtree function isn't the right approach either.

Consider this case (with JSON-y goodness):

A: {
   B: [ B1, B2, B3, B4, B5, B6, B7, B8 ],
   C: {
      C1: [ C1a, C1b, C1c ],
      C2: [ C2a, C2b, C2c ]
   }
}

In this case, "A" has two subordinates: "B" and "C". If I calculate my cost function by summing the number of subordinates under each officer, "B" and "C" seem to have identical cost, since they have a total of eight subordinates each.

The cost of any soldier "s" can be calculated like this:

   1 + max(s.subordinateCount(), + s.mostExpensiveSubordinate())

Each officer should contact his subordinates in decreasing-cost order.

--benji

Sean Kelly wrote:
> Andrei Alexandrescu wrote:
>> Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.
>>
>> For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.
>>
>> Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.
> 
> Ah, we're finally getting into concurrent programming :-)  I'm sure the syntax could be made more D 2.0-like, but something like this should do the trick:
> 
> class Soldier
> {
>     Soldier[] subordinates;
> 
>     void notify()
>     {
>         foreach( s; subordinates )
>             pool.add( &s.notify() );
>         pool.add( &flee() );
>     }
> 
>     void flee()
>     {
>         // make 'this' actually flee
>     }
> }
> 
> Assume 'pool' is a global thread pool with some number of worker threads proportional to the number of cores on the system.  This will issue instructions for all Soldiers to flee in an optimally parallel manner for the target system.

Nope, not optimal. Please reread the spec.

Andrei

Reply to Benji,

> BCS wrote:
> 
>>> Sort everyone under you (directly or indirectly)         <<<<<
>>> by the number of
>>> subordinates they have. Pick the subordinate with the most
>>> subordinates and call the next man in line to them. remove every
>>> subordinate down that chain of command and repeat.
>>> 
>>> This assumes that the depth of command is more or less the same
>>> across the board.
>>> 
>> This is based on the ssumption that the people with the most
>> subordinates need to get started first.
>> 
> But consider this case...
> 
> I have two subordinates: Dirk and Deek. Dirk has only one subordinate
> of his own, but Deek has three. It seems like I should call Deek
> first.
> 
> But what if Dirk's single subordinate has twenty subordinates of his
> own, which Deek's subordinates are leaf-nodes? In that case, it makes
> a whole lot more sense to call Dirk first.

my solution does exactly that. It first calls the commander, however removed, from whoever has the most subordinates. Assuming that each call take the same amount of time, the man with the most subordinates will be the first man at his rank to get the order.

BCS wrote:
> Reply to Benji,
> 
>> BCS wrote:
>>
>>>> Sort everyone under you (directly or indirectly)         <<<<<
>>>> by the number of
>>>> subordinates they have. Pick the subordinate with the most
>>>> subordinates and call the next man in line to them. remove every
>>>> subordinate down that chain of command and repeat.
>>>>
>>>> This assumes that the depth of command is more or less the same
>>>> across the board.
>>>>
>>> This is based on the ssumption that the people with the most
>>> subordinates need to get started first.
>>>
>> But consider this case...
>>
>> I have two subordinates: Dirk and Deek. Dirk has only one subordinate
>> of his own, but Deek has three. It seems like I should call Deek
>> first.
>>
>> But what if Dirk's single subordinate has twenty subordinates of his
>> own, which Deek's subordinates are leaf-nodes? In that case, it makes
>> a whole lot more sense to call Dirk first.
> 
> my solution does exactly that. It first calls the commander, however removed, from whoever has the most subordinates. Assuming that each call take the same amount of time, the man with the most subordinates will be the first man at his rank to get the order.

Define subordinate.

Andrei

Reply to Andrei,

> BCS wrote:
> 
>> Reply to Benji,
>> 
>>> BCS wrote:
>>> 
>>>>> Sort everyone under you (directly or indirectly)         <<<<<
>>>>> by the number of
>>>>> subordinates they have. Pick the subordinate with the most
>>>>> subordinates and call the next man in line to them. remove every
>>>>> subordinate down that chain of command and repeat.
>>>>> This assumes that the depth of command is more or less the same
>>>>> across the board.
>>>>> 
>>>> This is based on the ssumption that the people with the most
>>>> subordinates need to get started first.
>>>> 
>>> But consider this case...
>>> 
>>> I have two subordinates: Dirk and Deek. Dirk has only one
>>> subordinate of his own, but Deek has three. It seems like I should
>>> call Deek first.
>>> 
>>> But what if Dirk's single subordinate has twenty subordinates of his
>>> own, which Deek's subordinates are leaf-nodes? In that case, it
>>> makes a whole lot more sense to call Dirk first.
>>> 
>> my solution does exactly that. It first calls the commander, however
>> removed, from whoever has the most subordinates. Assuming that each
>> call take the same amount of time, the man with the most subordinates
>> will be the first man at his rank to get the order.
>> 
> Define subordinate.
> 
> Andrei
> 

1 step down

Andrei Alexandrescu wrote:
> 
> Nope, not optimal. Please reread the spec.

Hm... based on the requirements, the options available are very limited.  Each person must call his subordinates iteratively, so the time required for all members of a subtree to be notified is a function of the size of that subtree.

I'm sure there's a great way to summarize the time taken with this method using graph theory (this smells a lot like trying to optimize a breadth-first search), but in essence the time taken to notify all members of a subtree will be proportional to the number of edges to be traversed to reach the most distant member, with the number of siblings contacted prior to any member included in the distance.  For example:

a: b,c
b: d
c: e,f,g
d: h
e:
f:
g:
h: i
i:

The following edges must be evaluated to reach g:

a->b, a->c, c->e, c->f, c->g

So assuming:

class Person
{
    Peson[] subs;
    size_t calls();
}

To construct an optimal calling strategy,  subs must be ordered as a max heap on calls(), where calls() represents the number of phone calls required before the most distant subordinate is contacted.  This should be relatively easy to construct from the bottom up.


Sean