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

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

Well, here is my terrible contribution. It is just a bruteforce and it star=
ts=20
taking a real long time 7*7 and higher. I tried writing some logic to make=
=20
better moves but couldn't really figure out how. In fact, even after readin=
g=20
some other solutions I still can't really figure out how to do this.

I will play around some more and repost if I can figure it out....
######################################

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

def mov_hori(ip, matrix, gridsize)
  moves =3D []
  if ip[1]-3 >=3D 0 and matrix[ip[0]][ip[1]-3] =3D=3D "."
    moves << "l" # left
  end
  if ip[1]+3 < gridsize and matrix[ip[0]][ip[1]+3] =3D=3D "."
    moves << "r" # right
  end
  moves
end

def mov_vert(ip, matrix, gridsize)
  moves =3D []
  if ip[0]-3 >=3D 0 and matrix[ip[0]-3][ip[1]] =3D=3D "."
    moves << "u" # up
  end
  if ip[0]+3 < gridsize and matrix[ip[0]+3][ip[1]] =3D=3D "."
    moves << "d" # down
  end
  moves
end

def mov_diag(ip, matrix, gridsize)
  moves =3D []
  if ip[0]-2 >=3D 0 and ip[1]+2 < gridsize and matrix[ip[0]-2][ip[1]+2] =3D=
=3D "."
    moves << "ur" # up-right
  end
  if ip[0]-2 >=3D 0 and ip[1]-2 >=3D 0 and matrix[ip[0]-2][ip[1]-2] =3D=3D =
"."
    moves << "ul" # up-left
  end
  if ip[0]+2 < gridsize and ip[1]+2 < gridsize and matrix[ip[0]+2][ip[1]+2]=
=20
=3D=3D "."
    moves << "dr" # down-right=20
  end
  if ip[0]+2 < gridsize and ip[1]-2 >=3D 0 and matrix[ip[0]+2][ip[1]-2] =3D=
=3D "."
    moves << "dl" # down-left
  end
  moves
end

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

def do_it(gridsize,ind_p)
  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]
  }

  array =3D ["."]
  matrix =3D []
  totalnums =3D gridsize*gridsize

  gridsize.times do
    matrix << array * gridsize
  end

  matrix[ind_p[0]][ind_p[1]] =3D 1
  nextint =3D 2

  totalnums.times do
    hori =3D mov_hori(ind_p, matrix, gridsize)
    vert =3D mov_vert(ind_p, matrix, gridsize)
    diag =3D mov_diag(ind_p, matrix, gridsize)
    moves =3D hori + vert + diag

    if moves.length =3D=3D 0
      return # try again
    end

    try_a_move =3D moves[rand(moves.length)]
    x,y =3D moves_offset[try_a_move]
    ind_p[0] +=3D x
    ind_p[1] +=3D y

    matrix[ind_p[0]][ind_p[1]] =3D nextint
    nextint +=3D 1
    if nextint =3D=3D totalnums + 1
      print_matrix(matrix)
    end
  end
end

gridsize =3D ARGV[0].to_i
ind_p =3D [rand(gridsize), rand(gridsize)] # random initial coords

while 1:
  (1..10000).each do
    matrix =3D do_it(gridsize,ind_p)
  end
  puts "10k iterations..."
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

--nextPart2740000.nFKiSreJMb
Content-Type: application/pgp-signature

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

iD8DBQBE3910wPD5Cr/3CJgRAmY+AJ9KGUsWCzBHWrNHPtKK950/RmtZ8wCfeQq7
3lnpChr8mDT2CTzWnU04744=
=OvqR
-----END PGP SIGNATURE-----

--nextPart2740000.nFKiSreJMb--