[OT] Retreating from Iraq

[Christopher Wright]

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);
     }
}