```--nextPart1235960.DI9U1TH8vc
Content-Type: text/plain;
charset="iso-8859-6"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

w00t!

I finally got it. At first I misunderstood the algorithm, I was counting th=
e=20
number of free  adjacent cells, and giving preference to the move with the=
=20
least amount. This actually made the script take longer than when I was=20
picking the move randomly. Finally I figured out we were scoring the least=
=20
amount of possible moves (per move)...I also refactored the code into a=20
class.

So here are a few timings:
\$ time ruby pnp.rb 15 > /dev/null
real    0m0.196s
user    0m0.092s
sys     0m0.009s
\$ time ruby pnp.rb 25 > /dev/null
real    0m0.460s
user    0m0.334s
sys     0m0.036s
\$ time ruby pnp.rb 50 > /dev/null
real    0m0.801s
user    0m0.659s
sys     0m0.052s
\$ time ruby pnp.rb 100 > /dev/null
real    0m5.472s
user    0m5.038s
sys     0m0.299s

Nothing to be thrilled about, that's fer shur.

And the code:
#####################################
#!/usr/bin/ruby
# PnP.rb :: quiz no.90

class SolveIt
def initialize(x,y,gridsize)
@gridsize =3D gridsize
@coords =3D [x,y]

@moves_offset =3D {
"l"  =3D> [0,-3],
"r"  =3D> [0,3],
"u"  =3D> [-3,0],
"d"  =3D> [3,0],
"ur" =3D> [-2,2],
"ul" =3D> [-2,-2],
"dr" =3D> [2,2],
"dl" =3D> [2,-2]
}

@matrix =3D Array.new(@gridsize) { Array.new(@gridsize) { "." } }
@matrix[@coords][@coords] =3D 1
@totalnums =3D @gridsize*@gridsize
@nextint =3D 2
end

def cell_free?(x,y)
if x >=3D 0 && x < @gridsize && y >=3D 0 && y < @gridsize &&=20
@matrix[x][y] =3D=3D "."
return true
else
return false
end
end

def num_moves(m)
moves =3D 0
x,y =3D @moves_offset[m]
@moves_offset.each do |k,v|
moves +=3D 1 if cell_free?(@coords+x+v,@coords+y+v)
end
moves
end

def check_moves_and_return_best_one
moves =3D []
@moves_offset.each do |k,v|
moves << k if cell_free?(@coords+v,@coords+v)
end
if moves.length =3D=3D 0
return nil
elsif moves.length =3D=3D1
return moves
end
score =3D {}
moves.each do |m|
score[m] =3D num_moves(m)
end
score =3D score.invert.sort
return score
end

def print_matrix
@matrix.each do |row|
row.each do |cell|
print " %3s " % cell
end
print "\n"
end
end

def do_it
@totalnums.times do
move =3D check_moves_and_return_best_one
if move =3D=3D nil
break # try again
end
x,y =3D @moves_offset[move]
@coords +=3D x
@coords +=3D y
@matrix[@coords][@coords] =3D @nextint
@nextint +=3D 1
if @nextint =3D=3D @totalnums + 1
print_matrix
exit
end
end
end
end

while 1:
gridsize =3D ARGV.to_i
x, y =3D rand(gridsize), rand(gridsize)
it =3D SolveIt.new(x,y,gridsize)
it.do_it
end
#############################################
=2Dd
=2D-=20
darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
"...the number of UNIX installations has grown to 10, with more expected..."
=2D Dennis Ritchie and Ken Thompson, June 1972

--nextPart1235960.DI9U1TH8vc
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.4 (GNU/Linux)

iD8DBQBE4BlJwPD5Cr/3CJgRAgrgAKCWL0E8YBdUTS/SXlG9PUDRQ7SepgCgnHwk
M8Iz67AGMTqYO0EEzvXTRGI=
=jRDq
-----END PGP SIGNATURE-----

--nextPart1235960.DI9U1TH8vc--

```