From: Robert Evans <robert.evans@...>
Date: 2006-08-14T07:28:04+09:00
Subject: [Solution] Re: [QUIZ] Pen and Paper (#90)

Here's my solution that does not roll over the edges. I'll post that  
one in a bit as this one ended up with a lot more modification that  
I'd like to throw in that one too.

This follows the Warnsdorff algorithm. This one started out as a  
decently clean program although not super-idiomatic Ruby or  
particularly OO. In trying to get it to go faster, I have added some  
pretty ugly versions of some of the methods. The profiler was telling  
me that I spent most of my time in array accessing, since I was  
building up a collection of next moves, then filtering them. I  
decided to make more of the checks inline instead of building arrays  
first. The methods prefixed with fast_ represent the denormalized  
version.

Getting rid of those extra array operations took the 500x500 grid  
from 47s of user time to 29s of user time!

Bob

RESULTS
[segovia:~/Documents/projects/rubyplay] bobevans% /usr/bin/time -p  
ruby quiz90c.rb 10
starting at (7, 7)
Completed!
10 81 32  9 82 48 22 62 49 23
76 27 12 75 26 13 51 25 14 52
33  8 95 86 31 69 85 47 21 61
11 80 77 28 83 78 29 63 50 24
98 91 34 74 94 87 54 70 15 53
38  7 96 79 30 68 84 46 20 60
35 41 99 90 65 71 18 64 57  3
97 92 37 73 93 88 55  1 16 45
39  6 66 40  5 67 58  4 19 59
36 42 100 89 43 72 17 44 56  2
real         0.01
user         0.01
sys          0.00

[segovia:~/Documents/projects/rubyplay] bobevans% /usr/bin/time -p  
ruby quiz90c.rb 50
starting at (31, 33)
Completed!
real         0.30
user         0.29
sys          0.00

[segovia:~/Documents/projects/rubyplay] bobevans% /usr/bin/time -p  
ruby quiz90c.rb 100
starting at (98, 12)
Completed!
real         1.14
user         1.13
sys          0.00

That one took a few runs to pass. Given the high rate of false starts  
on larger grids, it makes sense to implement a different strategy,  
perhaps the Conrad-like strategy that Elliot used.
===============================

class Grid
   SM = 3 # square move length
   DM = 2 # diagonal move length

   def initialize(size)
     @matrix = Array.new(size).map{Array.new(size)}
     @counter = 0
     @max = size * size
     @size = size
   end

   def solve
     no_moves_left = false
     pick_start_place
     while !no_moves_left && @counter < @max
       next_move = pick_move
       if next_move.nil?
         no_moves_left = true
       else
         move(next_move[0], next_move[1])
       end
     end

     puts no_moves_left ? "Out of moves :-(" : "Completed!"
     print_matrix unless @size > 30
   end

   def pick_start_place
     x = rand(@size)
     y = rand(@size)
     puts "starting at (#{x}, #{y})"
     move(x, y)
   end

   def pick_move
     moves = fast_available_moves
     if !moves.empty?
       moves.sort[0][1]
     else
       nil
     end
   end

   def move(x,y)
     @x = x
     @y = y
     # puts "moving to #{x},#{y}"
     @matrix[x][y] = @counter += 1
     # print_matrix
   end

   def available_moves
     [n(@x,@y), ne(@x,@y), e(@x,@y),
      se(@x,@y), s(@x,@y), sw(@x,@y),
      w(@x,@y), nw(@x,@y)].reject{ |ma| move_illegal?(ma) || !clear? 
(ma[0], ma[1]) }.map { |m| [count_moves(m), m] }
   end

   def fast_available_moves
     moves = []
     moves << [fast_count_moves([@x-SM, @y]), [@x-SM, @y]]  unless  
coord_illegal?(@x-SM) || !clear?(@x-SM, @y)
     moves << [fast_count_moves([@x-DM, @y+DM]), [@x-DM, @y+DM]]  
unless (coord_illegal?(@x-DM) || coord_illegal?(@y+DM)) || !clear?(@x- 
DM, @y+DM)
     moves << [fast_count_moves([@x, @y+SM]), [@x, @y+SM]] unless  
coord_illegal?(@y+SM) || !clear?(@x, @y+SM)
     moves << [fast_count_moves([@x+DM, @y+DM]), [@x+DM, @y+DM]]  
unless (coord_illegal?(@x+DM) || coord_illegal?(@y+DM)) || !clear?(@x 
+DM, @y+DM)
     moves << [fast_count_moves([@x+SM, @y]), [@x+SM, @y]] unless  
coord_illegal?(@x+SM) || !clear?(@x+SM, @y)
     moves << [fast_count_moves([@x+DM, @y-DM]), [@x+DM, @y-DM]]  
unless (coord_illegal?(@x+DM) || coord_illegal?(@y-DM)) || !clear?(@x 
+DM, @y-DM)
     moves << [fast_count_moves([@x, @y-SM]), [@x, @y-SM]] unless  
coord_illegal?(@y-SM) || !clear?(@x, @y-SM)
     moves << [fast_count_moves([@x-DM, @y-DM]), [@x-DM, @y-DM]]  
unless (coord_illegal?(@x-DM) || coord_illegal?(@y-DM)) || !clear?(@x- 
DM, @y-DM)
     moves
   end

   def n(x, y); [x - SM, y]; end

   def ne(x, y); [x - DM, y + DM]; end

   def e(x, y); [x, y + SM]; end

   def se(x, y); [x + DM, y + DM] ; end

   def s(x, y); [x + SM, y]; end

   def sw(x, y); [x + DM, y - DM] ; end

   def w(x, y); [x, y - SM]; end

   def nw(x, y); [x - DM, y - DM]; end

   def count_moves(m)
     x = m[0]
     y = m[1]
     [n(x, y), ne(x, y), e(x, y),
      se(x, y), s(x, y), sw(x, y),
      w(x, y), nw(x, y)].reject{ |ma| move_illegal?(ma) || !clear?(ma 
[0], ma[1])}.length
   end

   def fast_count_moves(m)
     x = m[0]
     y = m[1]
     count = 0
     count += 1 unless coord_illegal?(x-SM) || !clear?(x-SM, y)
     count += 1 unless (coord_illegal?(x-DM) || coord_illegal?(y+DM))  
|| !clear?(x-DM, y+DM)
     count += 1 unless coord_illegal?(y+SM) || !clear?(x, y+SM)
     count += 1 unless (coord_illegal?(x+DM) || coord_illegal?(y+DM))  
|| !clear?(x+DM, y+DM)
     count += 1 unless coord_illegal?(x+SM) || !clear?(x+SM, y)
     count += 1 unless (coord_illegal?(x+DM) || coord_illegal?(y-DM))  
|| !clear?(x+DM, y-DM)
     count += 1 unless coord_illegal?(y-SM) || !clear?(x, y-SM)
     count += 1 unless (coord_illegal?(x-DM) || coord_illegal?(y-DM))  
|| !clear?(x-DM, y-DM)
     count
   end

   def clear?(x,y)
     @matrix[x][y].nil?
   end

   def move_illegal?(m)
     x = m[0]
     y = m[1]
     x >= @size || x < 0 || y >= @size || y < 0
   end

   def coord_illegal?(n)
     n >= @size || n < 0
   end

   def print_matrix
     @matrix.each { |r|  r.each { |c| printf("%2d ", c)}; puts "\n"}
   end
end

def run(size=6)
   g = Grid.new(size)
   g.solve
   nil
end

if $0 == __FILE__
   run(ARGV[0].to_i)
end