```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.
```
```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 )
}

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
```
```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 )
>     }
>
>     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.

Andrei
```
```Andrei Alexandrescu wrote:
>

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
```
```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]
// [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);
}
}
```
```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

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

{
subordinates ~= u;
subordinates.sort;
}
}

This class both arranges units in optimal order and calculates the cost
(time) of retreat.
```
```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
```
```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
```
```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.
```
```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
```
Next ›   Last »
1 2