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

At first: sorry for my bad english and my bad perl ;)

I solved the problem for the LSB-FSM and I must say it was really a hard
task. The main problem was not to write the generator-function but to 
design the FSM itself. 

My first solution was an FSM with about O(n^2) ("n" is that FSM-number) 
states. It's a straightforward solution from the theory. Then i tried to 
minimize the FSM with a standard minimization-algorithm (i.e. I wrote an 
algorithm replacing equivalent states by a new one). This leads to my 
first real solution. This one is written in ruby because it was too hard 
for me to translate it into good perl. The main problem of this solution 
is that it has a complexity of O(n^4) because the minimization algorithm
has a complexity of O(n^2), too.

But I made an observation leading to my final solution which is pretty
small. The minimized FSM for "n" has alwasy n states. So I tried to find
a way to create the equivalent states and their connections directly
without using the minimization algorithm. 

Although that solution is really nice, it was a long way to get it ;). I
don't know if someone is interested in me explaining my thoughts in a
more detailed way, but this would be a long mail. If so, let me know.

I also created a simple third solution that is an extension to my second
one. This one also works for even n by checking for 2^k prime-factors
first and then do the standard algorithm on the odd rest (in fact, it's
essential for the standard FSM that n is not even).



Greetings

	Frank Fischer



=== first solution: O(n^2)-states with minimization (ruby) ===
# simulate the FSM
def run_fsm(states, n)
  n = n.to_i

  cur = 0
  while n > 0
    cur = states[cur]['next_states'][n & 0x1]
    n >>= 1
  end

  return states[cur]['ret']
end

# create the FSM
def gen_is_divisible_fsm(n)
  n = n.to_i
  # no even numbers till now
  raise "n must not be even" if n % 2 == 0

  states = [] # the states
  states_by_pq = { } # the (p,q) => state-number map
  # create the (p,q)=>number map for all possible values of (p,q)
  for p in 0...n do
    for q in 1...n do
      states_by_pq[[p,q]] = states_by_pq.size
    end
  end

  # now create the arcs for each state from state (p,q)
  # if we read a "0", go to (p,q*2)
  # if we read a "1", got to (p+q,q*2)
  # if we reach an accept-state (0,x), always use (0,1)
  states_by_pq.each_pair do |pq, idx|
    p,q = pq
    next_0 = [p, (q*2)%n]
    next_1 = [(p+q)%n, (q*2)%n]
    new_state = { 'next_states' => [ states_by_pq[next_0], 
	                             states_by_pq[next_1] ],
                  'ret' => p }
    states[idx] = new_state
  end

  # return the states
  return states
end

# minimize the FSM by replacing all equivalent states by one
def minimize(states)
  n_old_states = states.size

  # first we remove unreachable states
  # this is not really necessary for our FSM, but it's good in general
  remove_unreachable!( states ) 
  clear_states!( states ) # clean the states-array

  # the "marks"-map has a value of true for all pairs of states that are not
  # equivalent, false otherwise (i.e. if two states are equivalent,
  # marks[ [a,b] ] == false
  # at the beginning, two states are equivalent if and only if both
  # are accepting states or both are no accepting states
  marks = {}
  for p in 0...states.size do
    if states[p]
      for q in p...states.size do
	if states[q]
	  marks[[p,q]] = (states[p]['ret'] == 0) != (states[q]['ret'] == 0)
	end
      end
    end
  end

  # now we loop as long as we found two states that are not equivalent
  # i.e. as long as we can reduce the number of states
  begin
    new_mark = false
    marks.each_pair do |pair, mark|
      unless mark # only check if the may be equivalent
	s1 = states[pair[0]] 
	s2 = states[pair[1]]
	
	# two states are not equivalent if at least "0" or "1" leads to
	# two not-equivalent states (i.e. marked states)
	if marks[ [s1['next_states'][0], s2['next_states'][0]].sort ] or
           marks[ [s1['next_states'][1], s2['next_states'][1]].sort ] then
	  marks[pair] = true # mark that pair as not equivalent
	  new_mark = true # we reduced the number of stated
	end
      end
    end
  end while new_mark

  # now remove all equivalent states but one (of each equivalence class)
  map = Hash.new { |h,k| k }
  marks.delete_if { |k,v| v }
  marks.keys.sort.each { |pair| map[pair[1]] = map[pair[0]] }

  for idx in 0...states.size
    if states[idx]
      if map[idx] == idx then # repoint the first
	states[idx]['next_states'].map! { |n| map[n] }
      else
	states[idx] = nil # delete the others
      end
    end
  end

  clear_states!( states ) # clean up
  return states, n_old_states-states.size
end

# do a simple depth-first-search to find unreachable states (which are removed)
def remove_unreachable!(states)
  reached = Hash.new(false)

  stack = [0]
  while !stack.empty? do
    idx = stack.pop
    reached[idx] = true
    states[idx]['next_states'].each do |next_state|
      stack.push next_state unless reached[next_state]
    end
  end

  states.each_index do |idx|
    states[idx] = nil unless reached[idx]
  end

  return states 
end

# remove nil-states from the array and fix the numbering
def clear_states!(states)
  i = 0
  map = {}
  states.each_index do |idx|
    s = states[idx]
    unless s.nil?
      map[idx] = i
      i += 1
    end
  end
  states.delete_if { |s| s.nil? }
  states.each do |s|
    s['next_states'].map! { |idx| map[idx] }
  end

  return states
end

# create FSM
m = gen_is_divisible_fsm( ARGV[0] )
# minimize FSM
m, n_removed = minimize( m )
# show it
m.each do |s|
  puts s.inspect
end

puts "States: #{m.size}, removed: #{n_removed}"

# a simple test: check the FSM for some numbers
n = ARGV[0].to_i
for i in 0..10000 
  rest = i%n
  result = run_fsm( m, i )
  if (rest == 0 and result != 0) or (rest != 0 and result == 0)
     raise "Error: #{i}"
  end
end

=== second solution: O(n)-states and really nice ===
use Carp;

sub gen_is_divisible_fsm {
  my $n = $_[0];
  my @states = ();

  croak "Number must not be even\n" if $n % 2 == 0;
  
  for (my $i = 0; $i < $n; $i++) {
    push(@states, { "next_states" => [ ($i*($n+1)/2) % $n, 
	                               (($i+1)*($n+1)/2) % $n ],
	            "ret" => $i });
  }

  return \@states
}

sub run_fsm {
  my ($states, $n) = @_;
  my $cur = 0;
  while ($n > 0) {
    $cur = $$states[$cur]->{next_states}[$n & 0x1];
    $n >>= 1;
  }
  return $$states[$cur]->{ret}
}

my $n = $ARGV[0];
my $m = gen_is_divisible_fsm($n);

print "States: ", $#$m+1, "\n";

for (my $i = 0; $i < 10000; $i++) {
  my $rest = $i % $n;
  my $result = run_fsm( $m, $i );
  if ( ($rest == 0 && $result != 0) or ($rest != 0 && $result == 0) ) {
    print $i, " ", $rest, " ", $result, "\n";
    croak "Invalid FSM\n";
  }
}
  
print "Test passed\n";

=== third solution: n states with even numbers ===
sub gen_is_divisible_fsm {
  my $n = $_[0];
  my @states = ();
  my $epow = 0;

  while ($n > 0 && $n % 2 == 0) {
    $epow++;
    $n >>= 1;
  }

  for (my $i = 0; $i < $epow; $i++) {
    push(@states, { "next_states" => [ $i+1, $epow + $n ],
		    "ret" => 0 });
  }

  for (my $i = 0; $i < $n; $i++) {
    push(@states, { "next_states" => [ ($i*($n+1)/2) % $n + $epow, 
	                               (($i+1)*($n+1)/2) % $n + $epow ],
	            "ret" => $i });
  }

  push(@states, { "next_states" => [ $n + $epow, $n + $epow ], "ret" => 1 })
    if ($epow > 0);

  return \@states
}
==================================================

-- 
eMail: frank.fischer-JJ2xi2hz/[email protected] 
Jabber: lyro-/[email protected]
ICQ: 49470926
freebits.de - Linux, Unix && OpenSource