Source: Homework problem in a CompSci Agents course at Stanford University, Fall, 1991.
Hello, Ken, Here's a solution to your PUZZLE with the General and the Drummer. I think this one's really easy. It reminds me of a dual-slope or triple-slope ADC. THE GENERAL has to do some planning, before the time of the Attack, just as a real General does. See below. The DRUMMER has to keep beating the drum, one beat per second, uniformly, or at the required rate. It would be wise if he keeps on beating all the time, even when there are no orders to be passed. (Although the general might arrange for a BACKUP who can substitute in so the Drummer can go to the John before his work becomes critical.) The DRUMMER must also pass the ORDER on to his left or right, per the procedure as stated below for the men. The INFANTRYMEN have simple tasks: 1. Pass the ORDER: If the man receives an ORDER on the left, he must pass it to the man on the right, on the next drum beat, for a delay of exactly one drum beat. If he cannot pass it to the right, because there is no-one there, he must pass it back to the left. (If he receives orders on the RIGHT, then VICE VERSA of above.) 2. Count. The first time he gets an ORDER, he must COUNT until he gets the ORDER back again. Then he must REMEMBER that count, N. 3. The THIRD time he gets the order, he must start counting DOWN from (N/2 + 1). When his count gets to ZERO, he must FIRE. (Note, if he whispers his countdown out loud, he can hear his comrades on each side, counting down just the same.) The GENERAL must send out the first ORDER at a suitable early time before the ATTACK. He must count the number of Drum beats M until he gets the ORDER repeated back, on the Left (ML) and on the Right (MR). He must remember these counts. (an Odd number, each.) When he is ready to call an attack at time T, he must send out the ORDER to the left at a time t = T - ML/2 -1/2. He must likewise send out an ORDER to the right at a time t = T - MR/2 - 1/2. After that delay, everybody will fire at time = T. (Option, everybody counts down from N/2 + 2) for best precision. Start sending out the orders to start firing at t = T - M/2 -1.5 ) It's hard to think of any procedure much simpler (or quicker) than that. Any good software writer could write that one. Even I could write that one - in BASIC. Best regards/ rap