The following puzzle comes verbatim courtesy of a coworker. It caused a lot of controversy amongst my colleagues and hopefully will bring some enjoyment to its problem solvers.
General and Solder Robots (Executing Simultaneous Shoot Command) Problem Description:
1. You have two types of robots, a General and many Solider robots.
2. They are linked up as follows GSSSSS…. (where G = General and S = Soldier)
3. There is a finite but indefinite number of Soldier robots.
4. Each robot can communicate with only the one or two robots that are adjacent to it, and this communication takes 1 unit of time.
5. The General has one program on it, and the Soldiers all have different instances of one program on them.
6. The General must execute the first communication to its neighbor robot and then it may not communicate any more.
7. Each of the soldiers have a shoot command on them this can be arbitrarily named ‘Shoot()’ for convenience.
8. Each of the Soldiers must execute the Shoot() command simultaneously and the Shoot() command can only be execute once.
Difficulty Levels of the Solution:
1. You are allowed that the robot is an Infinite State Machine.
2. The robot must be a Finite State Machine.
3. The robots must all shoot at time 2N-2, where N is the number of robots.
Attempt to solve the problem in incremental levels of difficulty. #1 should come fairly quickly whereas #2 & 3 are tougher.