October 14, 2008
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);
    }
}

October 14, 2008
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.
October 14, 2008
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
October 14, 2008
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
October 16, 2008
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.
October 16, 2008
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
1 2 3
Next ›   Last »