www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [OT] Retreating from Iraq

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 13 2008
next sibling parent reply Russell Lewis <webmaster villagersonline.com> writes:
If every superior uses a conference call to talk to his subordinates, 
then the news propagates exactly proportional to the depth of the heirarchy.

:)

Of course, if he has to call all of his subordinates in sequence, then 
things are different...but in that case, we need a measurement for 
"fast."  Are we looking for an algorithm that provides the lowest 
possible maximum time, lowest average, or something else?

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

Oct 13 2008
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Russell Lewis wrote:
 If every superior uses a conference call to talk to his subordinates, 
 then the news propagates exactly proportional to the depth of the 
 heirarchy.
 
 :)
 
 Of course, if he has to call all of his subordinates in sequence, then 
 things are different...but in that case, we need a measurement for 
 "fast."  Are we looking for an algorithm that provides the lowest 
 possible maximum time, lowest average, or something else?

Time from the president lifting the phone to the time the last private hears it. Andrei
Oct 13 2008
parent Russell Lewis <webmaster villagersonline.com> writes:
-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

Andrei Alexandrescu wrote:
 Russell Lewis wrote:
 If every superior uses a conference call to talk to his subordinates, 
 then the news propagates exactly proportional to the depth of the 
 heirarchy.

 :)

 Of course, if he has to call all of his subordinates in sequence, then 
 things are different...but in that case, we need a measurement for 
 "fast."  Are we looking for an algorithm that provides the lowest 
 possible maximum time, lowest average, or something else?

Time from the president lifting the phone to the time the last private hears it. Andrei

Oct 13 2008
prev sibling next sibling parent "Nick Sabalausky" <a a.a> writes:
"Russell Lewis" <webmaster villagersonline.com> wrote in message 
news:gd07kk$28nu$1 digitalmars.com...
 If every superior uses a conference call to talk to his subordinates, then 
 the news propagates exactly proportional to the depth of the heirarchy.

 :)

Yea, but what's the overhead for arranging to get everyone in on the conference call at the same time? :)
Oct 13 2008
prev sibling parent "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
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

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.
Oct 15 2008
prev sibling next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
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

Hm, just call every subordinate you have? You need to tell everyone anyway. I can't figure out the problem.
Oct 13 2008
parent BCS <ao pathlink.com> writes:
Reply to KennyTM~,

 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
 

anyway. I can't figure out the problem.

who do you call first?
Oct 13 2008
prev sibling next sibling parent "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:gd078s$284f$1 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; } } }
Oct 13 2008
prev sibling next sibling parent Derek Parnell <derek psych.ward> writes:
On 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.

But wouldn't this be broadcast on al Jazzera before the generals get the "official" news? -- Derek Parnell Melbourne, Australia skype: derek.j.parnell
Oct 13 2008
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Andrei,

 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
 

Sort everyone under you (directly or indirectly) by the number of subordinates they have. Pick the subordinate with the most subordinates and call the next man in line to them. remove every subordinate down that chain of command and repeat. This assumes that the depth of command is more or less the same across the board.
Oct 13 2008
parent reply BCS <ao pathlink.com> writes:
Reply to Benjamin,

 Reply to Andrei,
 
 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
 

subordinates they have. Pick the subordinate with the most subordinates and call the next man in line to them. remove every subordinate down that chain of command and repeat. This assumes that the depth of command is more or less the same across the board.

This is based on the ssumption that the people with the most subordinates need to get started first.
Oct 13 2008
parent reply Benji Smith <dlanguage benjismith.net> writes:
BCS wrote:
 Sort everyone under you (directly or indirectly) by the number of
 subordinates they have. Pick the subordinate with the most
 subordinates and call the next man in line to them. remove every
 subordinate down that chain of command and repeat.

 This assumes that the depth of command is more or less the same across
 the board.

This is based on the ssumption that the people with the most subordinates need to get started first.

But consider this case... I have two subordinates: Dirk and Deek. Dirk has only one subordinate of his own, but Deek has three. It seems like I should call Deek first. But what if Dirk's single subordinate has twenty subordinates of his own, which Deek's subordinates are leaf-nodes? In that case, it makes a whole lot more sense to call Dirk first. So it seems essential to implement a cost function for each branch of the tree. Something more elaborate than just counting each person's subordinates. But a weighted-subtree function isn't the right approach either. Consider this case (with JSON-y goodness): A: { B: [ B1, B2, B3, B4, B5, B6, B7, B8 ], C: { C1: [ C1a, C1b, C1c ], C2: [ C2a, C2b, C2c ] } } In this case, "A" has two subordinates: "B" and "C". If I calculate my cost function by summing the number of subordinates under each officer, "B" and "C" seem to have identical cost, since they have a total of eight subordinates each. The cost of any soldier "s" can be calculated like this: 1 + max(s.subordinateCount(), + s.mostExpensiveSubordinate()) Each officer should contact his subordinates in decreasing-cost order. --benji
Oct 13 2008
parent reply BCS <ao pathlink.com> writes:
Reply to Benji,

 BCS wrote:
 
 Sort everyone under you 
 (directly or indirectly)         <<<<<
 by the number of
 subordinates they have. Pick the subordinate with the most
 subordinates and call the next man in line to them. remove every
 subordinate down that chain of command and repeat.
 
 This assumes that the depth of command is more or less the same
 across the board.
 

subordinates need to get started first.

I have two subordinates: Dirk and Deek. Dirk has only one subordinate of his own, but Deek has three. It seems like I should call Deek first. But what if Dirk's single subordinate has twenty subordinates of his own, which Deek's subordinates are leaf-nodes? In that case, it makes a whole lot more sense to call Dirk first.

my solution does exactly that. It first calls the commander, however removed, from whoever has the most subordinates. Assuming that each call take the same amount of time, the man with the most subordinates will be the first man at his rank to get the order.
Oct 13 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
BCS wrote:
 Reply to Benji,
 
 BCS wrote:

 Sort everyone under you (directly or indirectly)         <<<<<
 by the number of
 subordinates they have. Pick the subordinate with the most
 subordinates and call the next man in line to them. remove every
 subordinate down that chain of command and repeat.

 This assumes that the depth of command is more or less the same
 across the board.

subordinates need to get started first.

I have two subordinates: Dirk and Deek. Dirk has only one subordinate of his own, but Deek has three. It seems like I should call Deek first. But what if Dirk's single subordinate has twenty subordinates of his own, which Deek's subordinates are leaf-nodes? In that case, it makes a whole lot more sense to call Dirk first.

my solution does exactly that. It first calls the commander, however removed, from whoever has the most subordinates. Assuming that each call take the same amount of time, the man with the most subordinates will be the first man at his rank to get the order.

Define subordinate. Andrei
Oct 13 2008
parent BCS <ao pathlink.com> writes:
Reply to Andrei,

 BCS wrote:
 
 Reply to Benji,
 
 BCS wrote:
 
 Sort everyone under you (directly or indirectly)         <<<<<
 by the number of
 subordinates they have. Pick the subordinate with the most
 subordinates and call the next man in line to them. remove every
 subordinate down that chain of command and repeat.
 This assumes that the depth of command is more or less the same
 across the board.
 

subordinates need to get started first.

I have two subordinates: Dirk and Deek. Dirk has only one subordinate of his own, but Deek has three. It seems like I should call Deek first. But what if Dirk's single subordinate has twenty subordinates of his own, which Deek's subordinates are leaf-nodes? In that case, it makes a whole lot more sense to call Dirk first.

removed, from whoever has the most subordinates. Assuming that each call take the same amount of time, the man with the most subordinates will be the first man at his rank to get the order.

Andrei

1 step down
Oct 13 2008
prev sibling next sibling parent reply Gregor Richards <Richards codu.org> writes:
You want to destroy all life on Earth. To do this, you're creating 
nano-robots. A single nano-robot cannot control a persons mind: Seven 
are required (three in each half of the brain and one in the brain 
stem). Nano-robots can harvest material from their host to build new 
nano-robots, but the host will die after approximately twenty 
nano-robots-worth of material has been harvested (they require 
particular rare particles that can only be harvested from the heart and 
lungs).

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

Devise an algorithm for these nano-robots that will destroy all human 
life on Earth in the minimum amount of time. That is, minimize the time 
from deploying the first nano-robot to every human life being 
eliminated. You may assume a maximum of twelve degrees of separation 
between average industrialized people and that even the most remote 
tribe is connected by at least one human to the industrialized world.

Bonus: How would you change this algorithm if you wanted to destroy all 
animal life? All life?

  - Gregor Richards
Oct 13 2008
parent Gregor Richards <Richards codu.org> writes:
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.
Oct 13 2008
prev sibling next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
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 ) pool.add( &s.notify() ); pool.add( &flee() ); } 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
Oct 13 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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 ) pool.add( &s.notify() ); pool.add( &flee() ); } 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.

Nope, not optimal. Please reread the spec. Andrei
Oct 13 2008
parent Sean Kelly <sean invisibleduck.org> writes:
Andrei Alexandrescu wrote:
 
 Nope, not optimal. Please reread the spec.

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
Oct 13 2008
prev sibling next sibling parent Christopher Wright <dhasenan gmail.com> writes:
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); } }
Oct 13 2008
prev sibling next sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
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.
Oct 14 2008
prev sibling next sibling parent BLS <nanali nospam-wanadoo.fr> writes:
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
Oct 14 2008
prev sibling next sibling parent BLS <nanali nospam-wanadoo.fr> writes:
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
Oct 14 2008
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 15 2008