| Prepared by
Adam M. Costello
Last modified: 2000-Nov-08-Wed 01:23:58 GMT |
The essence of this solution has been found independently by a number of people. This particular machine spec is the one I came up with. It is followed by a walk-through.
Mnemonics:
I = "input"
O = "output"
S = "state bit"
f = "full speed"
t = "third speed"
b = "bouncer"
l = "left"
r = "right"
g = "gun"
' = [next state]
Inputs:
Ifl, Ifr, Itl, Itr ; unconnected looks like 0
Ibl, Ibr ; unconnected looks like 1
Outputs:
Ofl, Ofr, Ohl, Ohr, Obl, Obr, Og
State bits:
Sfl, Sfr, Stl0, Stl1, Stl2, Str0, Str1, Str2, Sg ; initially 0
Sb ; Initially 0 except for the soldiers on the ends, where Sb
; is initially 1. If this is illegal, we could add a fourth
; set of I/O lines for the sole purpose of detecting whether
; a soldier has neighbors on both sides.
Combinational logic:
Ofl = Sfl
Ofr = Sfr
Otl = Stl2
Otr = Str2
Obl = Sb
Obr = Sb
Og = Sg
x = Ifl && (Stl0 || Stl2) || Ifr && (Str0 || Str2) ||
Sfl && Itl || Sfr && Itr
; triggers the soldier to become a bouncer
State transitions:
Sfl' = Sb ? Ifl : Ifr || x
Sfr' = Sb ? Ifr : Ifl || x
Stl0' = Itr
Str0' = Itl
Stl1' = !Sb && (Stl0 || x)
Str1' = !Sb && (Str0 || x)
Stl2' = Stl1
Str2' = Str1
Sb' = Sb || x
Sg' = Sb && Ibl && Ibr
Starting action:
Set Sfr and Str1 of the far left soldier to 1.
The initial state is stable, with all outputs 0. After the starting action, a 1 travels to the right through the full-speed lines, and another 1 travels to the right through the third-speed lines. When the full-speed 1 hits the far right soldier, it bounces and heads back to the left, meeting the third-speed 1 at the midpoint. If the number of soldiers is odd, they meet inside a single soldier, causing it to become a bouncer. If the number of soldiers is even, the two 1s cross between the two middle soldiers, which both detect that they are sending and receiving 1s on the same side, and both become bouncers. Whenever a soldier becomes a bouncer, it sends 1s on its full-speed and third-speed lines on both sides. By symmetry, the two halves of the row will proceed in lock-step, as mirror images of each other. The row continues to subdivide until every soldier is a bouncer, then they all fire their guns on the next clock tick.
You can watch it happen with this wish script: toysoldier version 3.0.0.
The number of ticks from start to finish is 3*(n-2)+1, or a little less depending on how the odds and evens work out. I haven't proved this, but you can get 3n analytically using a continuous approximation of the discrete system. The top level of the problem sends the full-speed signal 1.5 times the length of the chain, then does a subproblem half the size. 1.5 * (1 + 1/2 + 1/4 + ...) = 3.
As noticed by Dan Garcia, it's possible to modify this solution to get arbitrarily close to 2n. Instead of cutting the problem in half each time, cut it into p parts, using signals at speeds i/(2p-i) for i from 1 to p-1, plus one full-speed signal. The running time will be about (2+1/(p-1))n. This adds a lot of complexity to the state machine.
|