All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Firing Line (Posted on 2004-08-25) Difficulty: 3 of 5
There is a group of N soldiers arranged in a straight line, standing side by side. Soldier number 1 is at the extreme left and soldier "N" is at the extreme right. Each soldier has a rifle that can be fired only once, a primitive timer, understands a finite list of commands, and can exist in a finite number of states, like a finite state machine.

Each soldier has the ability to communicate only with the two adjacent soldiers, and has no means of communication with more distant soldiers. The i-th soldier can not see or hear any signals given by the (i+2)th soldier, for example. There are no radios, cell phones, or megaphones.

Your mission as the commander is to devise an algorithm by which all soldiers fire their weapons simultaneously. Soldiers 1 and N are aware of the fact that they are "different" in that they each have only one neighbor. Other than that, however, the soldiers are initially all identical. The algorithm has to work for any value of N>2.

The primitive timers are synchronized and tick off once a second. Once a soldier receives new information, the earliest he can respond in any way is on the next tick of the clock. (I would say he/she, except that they are all identical). A soldier can give a signal to each neighbor simultaneously, based on the information he received one tick earlier. Whenever a soldier's state changes, his neighbors are aware of this one tick later. At time=0, soldier 1 is given the command to start the firing procedure

1. Devise an algorithm that results in all N soldiers firing simultaneously
2. As a function of N, how many clock ticks does this take?

See The Solution Submitted by Larry    
Rating: 3.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Jacques Mazoyer's Solution | Comment 11 of 14 |
 
Here is my implementation of Jacques Mazoyer's solution in Perl.
For all values of n I have run so far, the number of ticks is 2n.

# fssp.pl
use warnings;
use strict;
{
my $n = 31;
my $k;
my $i;
my $j;
my $line;
my $lmr;
my %inputs;
my $states;
#   Read in the state transition table
    while($line=<STDIN>) {
      $lmr = substr($line,0,1) . substr($line,2,1) . substr($line,4,1);
      $inputs{$lmr} = substr($line,6,1);
    }
#   Initialize states
    $k = 2*$n+1;
    $states = "-" x ($n) . "G";
#   Time tick loop
    for ( $j=0 ; $j<$k ; $j++) {
      $lmr = "GG" . substr($states,0,1);
      $line = "%";
      print substr($states,0,$n)," ",$j," ";
#   Soldier loop
      for ( $i=0 ; $i<$n ; $i++) {
        $lmr = substr($lmr,1,2) . substr($states,$i+1,1);
        if ( exists $inputs{$lmr} ) {
          $line = $inputs{$lmr};
          substr($states,$i,1) = $line;
        }
      }
      last if $line eq "%";
    }
}
This is the state transition table - L M R N
   L : The previous state of the soldier to my left
   M : My previous state
   R : The previous state of the soldier to my right
   N : My next state
The states are {-,A,B,C,F,G} with "-" the quiescent state,
"G" the excite state, and "F" the fire state. In my
implementation the state of the soldier to the left of
soldier #1 and the state of the soldier to right of
soldier #n is always "G".
- - - -
- - B -
- - C -
- - G -

- A A A
- A B -
- A C G
- B A G
- B B B
- B C -
- B G B
- C - C
- C A A
- C B G
- C C C
- C G G
- G A G
- G B G
- G C G
A - - G
A - A -
A - B -
A - C -
A - G C

A A - A
A A A A
A A B B
A A C C
A A G B

A B - G
A B A B
A B B B
A B C -
A C - B
A C B B
A C G B

A G - B
A G B G
A G C G
B - - -
B - A -
B - B -
B - C -
B - G -

B A - G
B A B G
B A C C
B A G C

B B - G
B B A A
B B B B
B B C C
B B G B
B C - C
B C C C
B C G G

B G - B
B G B G
B G C G
B G G G

C - - A
C - A -
C - B -
C - C -
C - G G

C A - A
C A A A
C B - -
C B A A
C B G -

C C - C
C C A A
C C B B
C C C C
C C G B
C G - A
C G B G
C G C G
C G G A

G - - C
G - A -
G - B -
G - C -
G - G A

G A C C
G A G C

G B - C
G B A C
G B C B
G B G G

G C - B
G C B B
G C G B

G G - B
G G B G
G G C G
G G G F
Here is the output for n = 31:
------------------------------- 0
C------------------------------ 1
BA----------------------------- 2
CGG---------------------------- 3
BABC--------------------------- 4
CG-CA-------------------------- 5
BA-AAG------------------------- 6
CG-ABBC------------------------ 7
BA--BCCA----------------------- 8
CGG--CAAG---------------------- 9
BABC-AABBC--------------------- 10
CG-C-ABBCCA-------------------- 11
BA-C--BCCAAG------------------- 12
CG-CA--CAABBC------------------ 13
BA-AAG-AABBCCA----------------- 14
CG-ABB-ABBCCAAG---------------- 15
BA--BG--BCCAABBC--------------- 16
CGG-BBC--CAABBCCA-------------- 17
BAB-BCCA-AABBCCAAG------------- 18
CGG--CAA-ABBCCAABBC------------ 19
BABC-AAA--BCCAABBCCA----------- 20
CG-C-AAAG--CAABBCCAAG---------- 21
BA-C-AABBC-AABBCCAABBC--------- 22
CG-C-ABBCC-ABBCCAABBCCA-------- 23
BA-C--BCCC--BCCAABBCCAAG------- 24
CG-CA--CCCA--CAABBCCAABBC------ 25
BA-AAG-CCAAG-AABBCCAABBCCA----- 26
CG-ABB-CAABB-ABBCCAABBCCAAG---- 27
BA--BG-AABBG--BCCAABBCCAABBC--- 28
CGG-BB-ABBBBC--CAABBCCAABBCCA-- 29
BAB-BG--BBBCCA-AABBCCAABBCCAAG- 30
CGG-BBC-BBCCAA-ABBCCAABBCCAABBA 31
BAB-BCC-BCCAAA--BCCAABBCCAABBAC 32
CGG--CC--CAAAAG--CAABBCCAABBACB 33
BABC-CCA-AAAABBC-AABBCCAABBACB- 34
CG-C-CAA-AAABBCC-ABBCCAABBACB-- 35
BA-C-AAA-AABBCCC--BCCAABBACB--- 36
CG-C-AAA-ABBCCCCA--CAABBACB---- 37
BA-C-AAA--BCCCCAAG-AABBACB----- 38
CG-C-AAAG--CCCAABB-ABBACB------ 39
BA-C-AABBC-CCAABBG--BACB------- 40
CG-C-ABBCC-CAABBBBC-GCB-------- 41
BA-C--BCCC-AABBBBCCGGB--------- 42
CG-CA--CCC-ABBBBCCBAGC--------- 43
BA-AAG-CCC--BBBCCBACGBA-------- 44
CG-ABB-CCCA-BBCCBACBGCGG------- 45
BA--BG-CCAA-BCCBACB-GBABC------ 46
CGG-BB-CAAA--CBACB--GCG-CA----- 47
BAB-BG-AAAAG-GACB---GBA-AAG---- 48
CGG-BB-AAABBAGCB----GCG-ABBC--- 49
BAB-BG-AABBACGB-----GBA--BCCA-- 50
CGG-BB-ABBACBGC-----GCGG--CAAG- 51
BAB-BG--BACB-GBA----GBABC-AABBA 52
CGG-BBC-GCB--GCGG---GCG-C-ABBAC 53
BAB-BCCGGB---GBABC--GBA-C--BACB 54
CGG--CBAGC---GCG-CA-GCG-CA-GCB- 55
BABC-GACGBA--GBA-AACGBA-AACGB-- 56
CG-CGGCBGCGG-GCG-ACBGCG-ACBGC-- 57
BA-GAGB-GBABAGBA-GB-GBA-GB-GBA- 58
CGCGCGC-GCGBCGCGCGC-GCGCGC-GCGC 59
BGBGBGBGGBGBGGBGBGBGGBGBGBGGBGB 60
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG 61
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 62
 

Edited on August 28, 2004, 1:17 am

Edited on August 28, 2004, 1:19 am

Edited on August 30, 2004, 12:29 am
  Posted by Bractals on 2004-08-27 23:35:38

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information