[OT] Retreating from Iraq

[Nick Sabalausky]

"Andrei Alexandrescu" <SeeWebsiteForEmail at erdani.org> wrote in message 
news:gd078s$284f$1 at 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)
                yield nextToRet; // C#-style
            else
                done = true;
        }
    }
}