View mode: basic / threaded / horizontal-split · Log in · Help
October 13, 2008
Re: [OT] Retreating from Iraq
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.
October 13, 2008
Re: [OT] Destroying all human life on Earth
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
October 13, 2008
Re: [OT] Destroying all human life on Earth
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.
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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.
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 14, 2008
Re: [OT] Retreating from Iraq
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
1 2 3
Top | Discussion index | About this forum | D home