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

I also initially solved the problem for MSB first, rather than LSB.  Part
of the confusion, I think, stems from the fact that the example state
machine for $N=3 works in both cases!

Anyway, there's an obvious pattern for the MSB FSM, because it's easy to
track the remainder.  For the LSB FSM, you can't track the remainder
anymore, but there's still a pattern.  As Greg said, when $N is odd the LSB
FSM is simply the MSB FSM with the transitions reversed.  So, here's my
solution:

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

  my @states;

  foreach (0 .. $n - 1) {
    push @states,
      {
       ret => $_,
       next_states => [( $_         * ($n+1) / 2) % $n,
                       (($_ + $n-1) * ($n+1) / 2) % $n],
      };
  }

  return(0, \@states);
}


Here's a script that dumps the FSM and tests it on the supplied input.
This one also supports MSB-first and even numbers.

#!/usr/local/bin/perl -w

use strict;

use Data::Dump qw/ dump /;

my $n = shift or die "Must specify number to generate FSM.\n";
my $input = shift or die "Must specify input to FSM.\n";
my $most_first = shift;

my($initial, $states) = gen_is_divisible_fsm($n, $most_first);

print dump($states), "\n";

my $binary = sprintf("%b", $input);
$binary = reverse $binary if !$most_first;

my $result = run_numeric_fsm($initial, $states, $binary);

print "$input = $binary: $result\n";

sub gen_is_divisible_fsm {
  my($n, $most_first) = @_;

  my @states;

  if ($most_first) {

    my $next = 0;
  
    foreach (0 .. $n-1) {
      push @states,
        {
         ret => $_,
         next_states => [$next++ % $n, $next++ % $n],
        };
    }

  } elsif ($n % 2) {

    foreach (0 .. $n - 1) {
      push @states,
        {
         ret => $_,
         next_states => [( $_         * ($n+1) / 2) % $n,
                         (($_ + $n-1) * ($n+1) / 2) % $n],
        };
    }

  } else {

    foreach (0 .. $n/2 - 1) {
      push @states,
        {
         ret => 0,
         next_states => [$_ + 1, $n/2+1],
        };
    }

    push @states,
      {
       ret => 0,
       next_states => [$n/2, $n/2],
      };

    push @states,
      {
       ret => 1,
       next_states => [$n/2+1, $n/2+1],
      };

  }

  return(0, \@states);
}

sub run_numeric_fsm {
  my($initial, $states, $string) = @_;

  my $state = $initial;

  while ($string =~ /(.)/gs) {
    my $input = $1;
    my $next_state = $states->[$state]{'next_states'}[$input];
    defined $next_state
      or die "No such input '$input' in state '$state'.\n";
    $state = $next_state;
  }
  return $states->[$state]{'ret'};
}

__END__


Ronald