www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [OT] Retreating from Iraq

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 13 2008
next sibling parent reply Russell Lewis <webmaster villagersonline.com> writes:
If every superior uses a conference call to talk to his subordinates, 
then the news propagates exactly proportional to the depth of the heirarchy.

:)

Of course, if he has to call all of his subordinates in sequence, then 
things are different...but in that case, we need a measurement for 
"fast."  Are we looking for an algorithm that provides the lowest 
possible maximum time, lowest average, or something else?

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.
 
 
 Andrei
Oct 13 2008
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Russell Lewis wrote:

 If every superior uses a conference call to talk to his subordinates, 
 then the news propagates exactly proportional to the depth of the 
 heirarchy.
 
 :)
 
 Of course, if he has to call all of his subordinates in sequence, then 
 things are different...but in that case, we need a measurement for 
 "fast."  Are we looking for an algorithm that provides the lowest 
 possible maximum time, lowest average, or something else?


Time from the president lifting the phone to the time the last private 
hears it.

Andrei
Oct 13 2008
parent reply Russell Lewis <webmaster villagersonline.com> writes:
-3.2 seconds.  It will be on the Drudge Report before the president 
picks up the phone.

Seriously, though, the algorithm is as follows:

- Give each private a "cost" of 0, since he has no calls to make
- Iterate through the list of superiors, starting with the lowest
   level and working upwards:
   - Sort the superior's subordinates by their cost, from greatest
     cost to least.
   - The superior will plan to call his subordinates in this order
   - The "cost" of the superior is equal to
        max (over subordinates si) i + cost(si)
     That is, each term in the max() is teh cost of the subordinate,
     plus his order in the list.  The total cost of this superior is
     the time from when he makes his first call, until the last
     private in his tree is notified.

This works because of two points:
1) The cost of a given officer notifying his tree doesn't depend on
    his upper heirarchy.  Thus, we can build the values from bottom up.
2) If an officer calls any high-cost subordinate after any lower-cost
    subordinate, then that obviously will make the tree finish later
    than in my suggested order.

Russ

Andrei Alexandrescu wrote:

 Russell Lewis wrote:

 If every superior uses a conference call to talk to his subordinates, 
 then the news propagates exactly proportional to the depth of the 
 heirarchy.

 :)

 Of course, if he has to call all of his subordinates in sequence, then 
 things are different...but in that case, we need a measurement for 
 "fast."  Are we looking for an algorithm that provides the lowest 
 possible maximum time, lowest average, or something else?


 
 Time from the president lifting the phone to the time the last private 
 hears it.
 
 Andrei
Oct 13 2008
parent "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
On Mon, 13 Oct 2008 21:50:30 +0100, Russell Lewis  
<webmaster villagersonline.com> wrote:


 -3.2 seconds.  It will be on the Drudge Report before the president  
 picks up the phone.

 Seriously, though, the algorithm is as follows:

 - Give each private a "cost" of 0, since he has no calls to make
 - Iterate through the list of superiors, starting with the lowest
    level and working upwards:
    - Sort the superior's subordinates by their cost, from greatest
      cost to least.
    - The superior will plan to call his subordinates in this order
    - The "cost" of the superior is equal to
         max (over subordinates si) i + cost(si)
      That is, each term in the max() is teh cost of the subordinate,
      plus his order in the list.  The total cost of this superior is
      the time from when he makes his first call, until the last
      private in his tree is notified.

 This works because of two points:
 1) The cost of a given officer notifying his tree doesn't depend on
     his upper heirarchy.  Thus, we can build the values from bottom up.
 2) If an officer calls any high-cost subordinate after any lower-cost
     subordinate, then that obviously will make the tree finish later
     than in my suggested order.

 Russ


You can improve on this if you are allowed to issue temporary field  
promotions
or use minions to dispatch orders. You can then send information side-ways.
Of course, the military would never go for that. It would break the chain  
of command.
The closest you get is "fire at will". Poor Will, he always gets caught in  
the crossfire.
Oct 15 2008
prev sibling parent "Nick Sabalausky" <a a.a> writes:
"Russell Lewis" <webmaster villagersonline.com> wrote in message 
news:gd07kk$28nu$1 digitalmars.com...

 If every superior uses a conference call to talk to his subordinates, then 
 the news propagates exactly proportional to the depth of the heirarchy.

 :)


Yea, but what's the overhead for arranging to get everyone in on the 
conference call at the same time? :)
Oct 13 2008
prev sibling next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
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.
 
 
 Andrei


Hm, just call every subordinate you have? You need to tell everyone anyway.

I can't figure out the problem.
Oct 13 2008
parent BCS <ao pathlink.com> writes:
Reply to KennyTM~,


 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.
 
 Andrei
 


 Hm, just call every subordinate you have? You need to tell everyone
 anyway.
 
 I can't figure out the problem.
 


who do you call first?
Oct 13 2008
prev sibling next sibling parent "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:gd078s$284f$1 digitalmars.com...

 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.


The problem can be thought of as running on a multicore machine with one 
separate core assigned to each person. Ie, every member of the military can 
all be doing independant actions simultaniously. Of course, the actual phone 
call prevents the people involved in the call from doing other things at the 
same time: unless they each have two phone lines and are really good 
multitaskers, but I'm going to assume that's not true in the general case 
(or the liutenant case, or the private case, etc ;) ).

I'm also going to ignore the case where a person is in the same room with 
one or more of their subordinates, because that would require enough 
knowledge of the mlitary to know how likely that is to occur at each level 
of the hierarchy. And I don't know that much about the military ;).

Whenever a person has subordinates left to call, they're doing nothing but 
calling their subordinates, because that news would be too significant to be 
wasting time taking a restroom or lunch break ;)

Assume N levels of hierarchy (again because I don't know that much about the 
military ;) ).

A person at level n has M direct subordinates, and calls each in sequence. 
With the obvious exception of m[0], m[x] will be receiving the message at 
the same time m[x-1] is calling their first subordinate. The message is 
trivial enough, and military people are assumed to be disciplined enough, 
that we can assume each instance of informing a subordinate takes the same 
amount of time across the board.

class MilitaryPerson
{
    MilitaryPerson[] subordinates;
    ProcessingCore core;
    bool gotMsg = false;

    void inform()
    {
        receiveMsg();
        hangUpPhone();

        // We can inform our subordinates
        // while our commanding officer
        // informs the rest of our "sibling"
        // comrades in the parent process.
        core.perform(
        {
            foreach(auto sub; iteratorDecreasingNumSubSubordinates)
                sub.inform();
        });
    }

    void receiveMsg()
    {
        gotMsg = true;
    }

    // The purpose of using this type of ordering
    // is to maximize simultaneous core utilization
    MilitaryPerson iteratorDecreasingNumSubSubordinates()
    {
        bool done = false;
        while(!done)
        {
            int maxSub = 0;
            bool found = false;
            MilitaryPerson nextToRet;
            foreach(int i, MilitaryPerson sub; subordinates)
            {
                if(!sub.gotMsg && sub.subordinates.length > maxSub)
                {
                    maxSub = sub.subordinates.length;
                    nextToRet = sub;
                    found = true;
                }
            }

            if(found)

            else
                done = true;
        }
    }
}
Oct 13 2008
prev sibling next sibling parent Derek Parnell <derek psych.ward> writes:
On Mon, 13 Oct 2008 14:24:14 -0500, 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.


But wouldn't this be broadcast on al Jazzera before the generals get the
"official" news?

-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell
Oct 13 2008
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
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.
Oct 13 2008
parent reply BCS <ao pathlink.com> writes:
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.
Oct 13 2008
parent reply Benji Smith <dlanguage benjismith.net> writes:
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
Oct 13 2008
parent reply BCS <ao pathlink.com> writes:
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.
Oct 13 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 13 2008
parent BCS <ao pathlink.com> writes:
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
Oct 13 2008
prev sibling next sibling parent reply Gregor Richards <Richards codu.org> writes:
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
Oct 13 2008
parent Gregor Richards <Richards codu.org> writes:
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.
Oct 13 2008
prev sibling next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
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
Oct 13 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 13 2008
parent Sean Kelly <sean invisibleduck.org> writes:
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
Oct 13 2008
prev sibling next sibling parent Christopher Wright <dhasenan gmail.com> writes:
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.
 
 
 Andrei


How long will it take for a message to reach someone, given that their 
direct superior just received the message?

Anywhere from 1 to superior.children.length.

The time it will take to inform a subgraph of height 2, then, is equal 
to the number of nodes in that subgraph.

What about a subgraph of height 3? You get to parallelize, but you have 
to inform the height 2 subgraphs in serial. The cost of handling the kth 
child graph is k + the cost of that graph.

In each graph, you want to minimize the maximum cost of handling a 
subgraph. I believe you can simply order the graphs by their cost (max 
heap or the like) and handle them in that order. In many cases, it won't 
matter at all what order you handle any but the most expensive child 
graph. But if you have subordinates with costs of, say, 8, 7, and 6, 
visiting 8 then 6 then 7 would be suboptimal (cost would then be 10 
rather than 9).

This only matters if informing someone is much more expensive than 
traversing (and decorating) the graph.

This is actually a good situation for using coroutines. I need to build 
a heap of my most expensive children, and most of the setup for that 
gets duplicated when I want to inform my children of stuff.

Anywho, some code. It's pseudocode that looks suspiciously like D:

struct Pair
{
     Soldier soldier;
     Fiber fiber;
}

alias MaxHeap!(Pair) LumpOfSoldiers;

class Soldier
{
     Soldier[] soldiers;
     uint cost = 0;

     Fiber notify ()
     {
         return new NotifyFiber (this);
     }

     void inform () { /* expensive op here */ }

     int opCmp (Object other)
     {
         // This order is probably wrong.
         return cost - (cast(Soldier)other).cost;
     }
}

class NotifyFiber : Fiber
{
     Soldier self;

     this (Soldier soldier)
     {
         self = soldier;
     }

     Pair[] sortSoldiers ()
     {
         auto lump = new LumpOfSoldiers;
         foreach (soldier; self.soldiers)
         {
             auto pair = Pair (soldier, soldier.notify);
             pair.fiber.run;
             lump ~= pair;
         }
         return lump.toSortedArray;
     }

     void getCost (Pair[] sorted)
     {
         // You can't do better than the given order.
         // However, let's say you have costs like:
         // [8, 7, 7, 7]
         // Adjusted costs will be:
         // [9, 8, 9, 10]
         // So you can't assign a cost until you've checked the entire 
list, or near enough.
         uint max = 0;
         foreach (i, pair; sorted)
         {
             if (i + pair.soldier.cost > max) max = i + pair.soldier.cost;
         }
         self.cost = max;
     }

     void inform (Pair[] sorted)
     {
         self.inform;
         foreach (pair; sorted)
         {
             pair.fiber.run;
         }
     }

     override void run ()
     {
         auto sorted = sortSoldiers;
         getCost (sorted);
         yield;
         inform (sorted);
     }
}
Oct 13 2008
prev sibling next sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
Mon, 13 Oct 2008 14:24:14 -0500,
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.


The time required to retreat a particular unit is the number of 
*sequential* calls to be made.

A private (leaf) has zero cost to retreat because they have nobody to 
call.

One level higher, the cost is simply the sum of direct subordinates 
(privates) under command.

Then things become more general.  First of all, it makes sense to first 
call a subordinate with the highest cost.  So direct subordinates should 
be sorted by descending cost.  Then the unit retreat cost would be

class Unit
{
  Unit[] subordinates;

  int cost()
  {
    int result = 0;
    foreach(i, sub; subordinates)
      cost = max(cost, i + S[i].cost);
  }

  int opCmp(Object o)
  {
    return cost - (cast(Unit)o).cost;
  }

  void addSubordinate(Unit u)
  {
    subordinates ~= u;
    subordinates.sort;
  }
}

This class both arranges units in optimal order and calculates the cost 
(time) of retreat.
Oct 14 2008
prev sibling next sibling parent BLS <nanali nospam-wanadoo.fr> writes:
Andrei Alexandrescu schrieb:

 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


I would use the Propagator pattern.
Q:
The Propagator pattern belongs to a family of patterns for consistently 
updating objects in a dependency network. The propagator patterns are 
found in such diverse applications as MAKE, WWW, spreadsheets, GUIs, 
reactive control systems, simulation systems, distributed file systems, 
distributed databases, workflow systems and multilevel caches.
----

You can find the code on my Blog : http://wdinspire.blogspot.com/

In this case I would prefer the push method instead of the pull method. 
States are simple : 1 Stay, 2 Go Home (This behaviour is similar to the 
observer pattern)

A detailed doc (pdf) at 
http://www.sei.cmu.edu/publications/articles/propagator.html
Bjoern
Oct 14 2008
prev sibling next sibling parent BLS <nanali nospam-wanadoo.fr> writes:
Andrei Alexandrescu schrieb:

 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


Thanks for that task! Just had an idea for a new software :) 
Implementing a database driven "Chaine Of Responsibility/ CoR" software.

I think it could be designed as stand alone programm or as  ERP- CRM- 
plugin. Another idea is to create a "CoR" plugin for BUG/QA tracking 
Systems.

Simple prototype should be ready within 2-3 days... Well, fine tuning 
(security levels f.i.) requires much more planning/time.
I'll give it a go. <enthusiastic>
Bjoern
Oct 14 2008
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.


Thanks for all the answers! Whew, it's been a wild ride. A few notes:

* Solutions that focused on the number of sub-subordinates without 
taking into consideration global structure are, alas, wrong.

* Looking over the thread in increasing order of date, I see Russell 
Lewis was the first to give the correct algorithm, and also sketched a 
proof. Kudos! Benji and Sergey also gave correct answers.

* Sorry Bjoern, I did not have the time to follow the Propagator pattern.

* I couldn't follow Nick's solution, but given that the right answer is 
rather simple, there may be some issues there.

The next problem also concerns retreating from Iraq, with a twist.


Andrei
Oct 15 2008