From: darren kirby <bulliver@...>
Date: 2006-08-14T15:34:19+09:00
Subject: [QUIZ][Much better solution] Pen and Paper (#90)

--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[0]][@coords[1]] =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[0]+x+v[0],@coords[1]+y+v[1])
    end
    moves
  end

  def check_moves_and_return_best_one
    moves =3D []
    @moves_offset.each do |k,v|
      moves << k if cell_free?(@coords[0]+v[0],@coords[1]+v[1])
    end
    if moves.length =3D=3D 0
       return nil
    elsif moves.length =3D=3D1
      return moves[0]
    end
    score =3D {}
    moves.each do |m|
      score[m] =3D num_moves(m)
    end
    score =3D score.invert.sort
    return score[0][1]
  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[0] +=3D x
      @coords[1] +=3D y
      @matrix[@coords[0]][@coords[1]] =3D @nextint
      @nextint +=3D 1
      if @nextint =3D=3D @totalnums + 1
        print_matrix
        exit
      end
    end
  end
end

while 1:
  gridsize =3D ARGV[0].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--