[OT] Retreating from Iraq

[Sergey Gromov]

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.