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/nGntIXQ@xxxxxxxxxxxxxxxx
Homepage: http://www.shlomifish.org/
Hacker sees bug. Hacker fixes bug.
|
