[SPOILER] Solution to Perl 'Hard' Quiz of the Week #2005-03-22

Since I was completely unable to solve the "hard" qotw as described, I
solved the "easy" version instead, which MSB first.

The solution is that each state $_ is the remainder ($_ % $N), so the
transition is to left shift the state and add the input (modulo $N).

Of course, the start state is 0 (0 % $N).

sub gen_is_divisible_fsm
{
  my ($N) = @_;

  return (0,
          [
           map {
                 {
                   ret => $_,
                   next_states => [
                                   ((2 * $_) + 0) % $N,
                                   ((2 * $_) + 1) % $N
                                  ]
                 }
               } (0 .. $N - 1)
          ]);
}

# Colin