[QUIZ] Perl 'Hard' Quiz of the Week #2005-03-22

IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.  
        Thanks.

Finite State Machines (or Determinstic Finite Automata) are a limited type of 
programming environment. In an FSM, several states are maintained. When the 
program is found in a given state, and receives an input token, it moves to a 
different state that corresponds to this token. As a stream of input tokens 
are given, it switches from one state to another until the end of the input. 

Here's an example. Suppose we have the following state machine:

A: 0 ==> A
   1 ==> B

B: 0 ==> B
   1 ==> C

C: 0 ==> C
   1 ==> C

We start at state A, and then if we receive 0, we stay at A. If, on the other 
hand we receive 1, we move to B. Similarly in B, we stay in B at 0, and move 
to C upon 1. When the state machine is in C it will remain in C until the end 
of the input. What this state machine does is determine if a binary input 
contains at least two 1's. (if so, its final state would be C).

For more information consult:

http://en.wikipedia.org/wiki/Finite_state_machine

Your mission is to write a function - gen_is_divisable_fsm($N) - that when 
given a non-even number $N will generate a state machine to determine if a 
number represented by a sequence of binary digits (starting from the least 
significant bit) is evenly divisable by $N. 

The state machine generation function will return two values:

1. The initial state index.

2. An array reference of state. Each state is a hash reference that contains:
    'ret' - a flag that indicates the return value of the state machine if the        
            input stops at this point. 0 means the number is divisable. Any                
            other value means it is not.
    'next_states' - an array reference containing two values with the indices
            of the next states for an input of 0 and an input of 1 
            respectively.

As an example if the function is called with 3 as its argument it can generate 
the following state machine:

0
[
   {
	'ret' => 0,
	'next_states' => [0,1],
   },
   {
        'ret' => 1,
        'next_states' => [2,0],
   },
   {
        'ret' => 2,
        'next_states' => [1,2],
   },
]

Enjoy!

	Shlomi Fish

---------------------------------------------------------------------
Shlomi Fish      shlomif-ik1l9ssToec+JF/[email protected]
Homepage:        http://www.shlomifish.org/

Hacker sees bug. Hacker fixes bug.