[QUIZ] Pen and Paper (#90)

[Robert Evans]

Is it acceptable to roll over the edges to the other side?

I wrote a solution that did, but then I thought perhaps that wasn't
acceptable.

Bob

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this
quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone
on Ruby Talk follow the discussion. Please reply to the original
quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=-=-=

by Eric DUMINIL

Some classmates and I used to play a lot of pen and paper games
while sitting
in the last row of the classroom. My favorite game was this one.

We had to fill a 5x5 board as fast as possible with numbers from 1
to 25,
beginning at a random position and then going from one square to
another:

- jumping over 2 squares when traveling horizontally or vertically
- jumping over 1 square when traveling diagonally.

Here is an example with numbers from 1 to 14 (it would be
impossible to keep on
filling the board, since 1, 13, and 8 are blocking the way):

-------------------
| . 1 4 . 14|
| 10 . . 11 6|
| 3 . 8 2 .|
| . 12 5 . 13|
| 9 . . . 7|
-------------------

Here is a completed 5x5 board:

-------------------
| 14 1 8 25 2|
| 6 23 16 5 22|
| 18 10 13 19 9|
| 15 4 7 24 3|
| 12 20 17 11 21|
-------------------

Though this game is impossible with 2x2, 3x3 or 4x4 boards, it
appears that NxN
boards can be filled when N>4 (or n=1). For example, 6x6:

-----------------------
| 33 21 10 32 35 11|
| 16 26 5 13 25 6|
| 9 31 34 22 30 1|
| 4 20 17 27 36 12|
| 15 23 8 14 24 7|
| 18 28 3 19 29 2|
-----------------------

7x7:

---------------------------
| 46 33 26 8 32 35 9|
| 17 14 5 37 15 6 38|
| 27 22 47 34 25 48 31|
| 45 42 16 7 43 36 10|
| 18 13 4 21 12 3 39|
| 28 23 44 29 24 49 30|
| 1 41 19 2 40 20 11|
---------------------------

Here comes the quiz!

- Write a ruby script that fills a board (with a given NxN size)
as fast as possible
- Try to fill the biggest board you can with this script, in a
reasonable amount of time (let's say 48 hours minus scripting time)

You get extra points for:

- Finding more about this game (name, origin, related articles)
- Filling a 5x5 board with only pen and paper
- Filling a bigger board with only pen and paper
- Finding the worst attempt possible for a given size. For example,
getting stuck after 10 steps on a 5x5 board is pretty bad:

-------------------
| . 6 3 . 7|
| . . 9 . .|
| 4 1 . 5 2|
| . . . . 8|
| . . 10 . .|
-------------------

- Filling a board with a cycle pattern, i.e. where you can jump from
the last square to the first square:

-------------------
| 22 10 7 23 11|
| 14 19 4 1 16|
| 8 24 12 9 6|
| 21 2 15 20 3|
| 13 18 5 25 17|
-------------------

-----------------------
| 16 9 27 17 8 28|
| 35 12 6 30 13 23|
| 26 18 15 10 19 2|
| 5 31 34 22 7 29|
| 36 11 25 1 14 24|
| 33 21 4 32 20 3|
-----------------------

I can't wait to look at your solutions!

I daresay that brute-forcing won't help you much (it took me
98,268,583 attempts
and 4 days on a decent computer to fill a 10x10 board) but I don't
know many
other ways to fill a board.

Have fun with this quiz.

 

[Éric DUMINIL]

Is it acceptable to roll over the edges to the other side?

Please do! You might come up to interesting results by mapping the square on a
torus.
And I bet that finding a solution rolling over edges is easier that way.

I wrote a solution that did, but then I thought perhaps that wasn't
acceptable.

Can you still modify your solution to fit the initial goal?

Bob

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this
quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone
on Ruby Talk follow the discussion. Please reply to the original
quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=-=-=

by Eric DUMINIL

Some classmates and I used to play a lot of pen and paper games
while sitting
in the last row of the classroom. My favorite game was this one.

We had to fill a 5x5 board as fast as possible with numbers from 1
to 25,
beginning at a random position and then going from one square to
another:

- jumping over 2 squares when traveling horizontally or vertically
- jumping over 1 square when traveling diagonally.

Here is an example with numbers from 1 to 14 (it would be
impossible to keep on
filling the board, since 1, 13, and 8 are blocking the way):

-------------------

| . 1 4 . 14|
| 10 . . 11 6|
| 3 . 8 2 .|
| . 12 5 . 13|
| 9 . . . 7|

-------------------

Here is a completed 5x5 board:

-------------------

| 14 1 8 25 2|
| 6 23 16 5 22|
| 18 10 13 19 9|
| 15 4 7 24 3|
| 12 20 17 11 21|

-------------------

Though this game is impossible with 2x2, 3x3 or 4x4 boards, it
appears that NxN
boards can be filled when N>4 (or n=1). For example, 6x6:

-----------------------

| 33 21 10 32 35 11|
| 16 26 5 13 25 6|
| 9 31 34 22 30 1|
| 4 20 17 27 36 12|
| 15 23 8 14 24 7|
| 18 28 3 19 29 2|

-----------------------

7x7:

---------------------------

| 46 33 26 8 32 35 9|
| 17 14 5 37 15 6 38|
| 27 22 47 34 25 48 31|
| 45 42 16 7 43 36 10|
| 18 13 4 21 12 3 39|
| 28 23 44 29 24 49 30|
| 1 41 19 2 40 20 11|

---------------------------

Here comes the quiz!

- Write a ruby script that fills a board (with a given NxN size)
as fast as possible
- Try to fill the biggest board you can with this script, in a
reasonable amount of time (let's say 48 hours minus scripting time)

You get extra points for:

- Finding more about this game (name, origin, related articles)
- Filling a 5x5 board with only pen and paper
- Filling a bigger board with only pen and paper
- Finding the worst attempt possible for a given size. For example,
getting stuck after 10 steps on a 5x5 board is pretty bad:

-------------------

| . 6 3 . 7|
| . . 9 . .|
| 4 1 . 5 2|
| . . . . 8|
| . . 10 . .|

-------------------

- Filling a board with a cycle pattern, i.e. where you can jump from
the last square to the first square:

-------------------

| 22 10 7 23 11|
| 14 19 4 1 16|
| 8 24 12 9 6|
| 21 2 15 20 3|
| 13 18 5 25 17|

-------------------

-----------------------

| 16 9 27 17 8 28|
| 35 12 6 30 13 23|
| 26 18 15 10 19 2|
| 5 31 34 22 7 29|
| 36 11 25 1 14 24|
| 33 21 4 32 20 3|

-----------------------

I can't wait to look at your solutions!

I daresay that brute-forcing won't help you much (it took me
98,268,583 attempts
and 4 days on a decent computer to fill a 10x10 board) but I don't
know many
other ways to fill a board.

Have fun with this quiz.

 

[Éric DUMINIL]

Great explanation indeed!

Thank you very much for making this quiz easier to understand Suraj

Eric

PS:
Do you also receive my emails twice?
Do you know where the problem can be?

 

[Matt Todd]

Eric, if you use Gmail, it'll show up twice because Gmail adds your
response as well as the email you get of what you just sent back from
the list. So, in effect, you keep your response as well as getting
your response back, and Google shows it twice.

Sorry to be off topic!

M.T.

 

[Éric DUMINIL]

Thanks for your explanation Matt!

So if I get it right, the important thing is that I'm not bothering the
mailing list with double messages?

Sorry for being off topic too!

Eric


Am Sonntag, 13. August 2006 11:37 schrieb Matt Todd:

 

[Elliot Temple]

Here's my first solution. I have two completely different ones:


it works by assigning each square a point value based on how many
squares its connected to (there's a whole second matrix for this). i
visit places with low point values first b/c they are harder to get
to. each move updates the values of places next to it. for a 50x50
game it fails roughly half the time. usually wins 10x10, maybe 90%.


require "pp"
$s = ARGV[0].to_i

if $s <= 0
$s = 10
end

printboard = true

if ARGV[1]
if ARGV[1] == "y"
printboard = true
end
if ARGV[1] == "n"
printboard = false
end
end


$board = Array.new($s) {Array.new($s) {nil}}

Connections = [
[3,0],
[-3,0],
[0,3],
[0,-3],
[2,2],
[2,-2],
[-2,2],
[-2,-2]
]

def coord_to_connected coord
res = []
Connections.each do |conn|
x,y=coord
dx,dy=conn
x += dx
y += dy
res << [x,y] if x >= 0 and x < $s and y >= 0 and y < $s
end
res
end

$score_board = Array.new($s) {[]}

$s.times do |i|
cur = $score_board
$s.times do |j|
cur << coord_to_connected([i,j]).length
end
end


def success?
$board.each { |r| return false if r.include? nil }
true
end



def goto sq
$count += 1
$pos = sq
x,y=sq
$board[x][y] = $count
coord_to_connected(sq).each do |sq|
$score_board[x][y] = -1
x2,y2=sq
$score_board[x2][y2] -= 1
end
end

$count = 0
goto [0,0]

while true
options = coord_to_connected $pos
options.reject! {|sq| x,y=sq; not $board[x][y].nil?}
options.map! { |e| [$score_board[e[0]][e[1]], e] }
options = options.sort_by {|e| [e[0], rand]}
if options.length == 0
break
end
goto options.first[1]
end

if printboard
pp $board
end

if success?
puts "success".upcase
else
puts "failed".upcase
end

 

[Elliot Temple]

Here is my second solution.

Timings are on bottom but include size=15000 in under 5min. The way
this works is it starts with two solved 5x5 games with special
properties (end in center, and start on either the middle of the top,
or the middle of the left side -- pretty print them if that's
confusing). it then places as many of those as needed to fill the
entire board. it also has to deal with incrementing the numbers in
the original 2 patterns. i included some test code which makes sure
the final solution is valid.

The way placing the 5x5 pre-solved patterns works is i make a column
with a "left" on top and all the rest are the "up" variety. moving
from the middle of a 5x5 grid straight down takes you one square off
the grid, to they line up and all connect. now we're in the middle of
the bottom 5x5 pattern, so what we need is to move right and have
that transition to the next pattern, and then go back up to the top,
then back down again, etc to get the second variety of column which
goes back up, i just reversed the rows in the first column. before
combining the columns for the final solution, they are transposed to
be rows so I can just use +

maybe a better way to get a feel for how it works is to set the size
to 10 or 15 and pp the solution. then scan the answer for
1,25,26,50,51,75 etc to see how it's laid out



require "pp"
s = ARGV[0].to_i

if s <= 0
s = 165
end

if s % 5 != 0
puts "Invalid Input. Must be multiple of 5."
exit
end

Left = [[17, 9, 2, 18, 24], [4, 14, 22, 7, 13], [1, 19, 25, 10, 20],
[16, 8, 3, 15, 23], [5, 11, 21, 6, 12]]

Up = [[17, 4, 1, 16, 5], [9, 14, 19, 8, 11], [2, 22, 25, 3, 21], [18,
7, 10, 15, 6], [24, 13, 20, 23, 12]]

num = s / 5
$items_in_a_column = 25 * num

$inc_col_count = -$items_in_a_column
def inc_col m
$inc_col_count += $items_in_a_column
m.map { |e| e.map { |e2| e2 + $inc_col_count} }
end

$inc_count = 0
def inc m
$inc_count += 25
m.map { |e| e.map { |e2| e2 + $inc_count} }
end

col = Left
(num-1).times do |j|
col += inc(Up)
end

col2 = col.reverse.transpose
col = col.transpose

sol = []

(num/2).times {sol += inc_col(col) + inc_col(col2)}

if num % 2 == 1
sol += inc_col(col)
end

# pp sol

# =========
# = tests =
# =========



Connections = [
[3,0],
[-3,0],
[0,3],
[0,-3],
[2,2],
[2,-2],
[-2,2],
[-2,-2]
]

def check_valid_movement m
flat = m.flatten
n = flat.length
rt_n = Math.sqrt(n).to_i
1.upto(n-1) do |i|
a = flat.index i
b = flat.index i+1
fail "num not found #{i}" if a.nil? or b.nil?
x1 = a % rt_n
y1 = a / rt_n
x2 = b % rt_n
y2 = b / rt_n
move = [x1-x2, y1-y2]
return false unless Connections.include? move
end
true
end

if true # warning: SLOW. took 9 minutes with size = 265. it's n^4 if
you treat the input number as n.
fail "dups" unless sol.flatten.uniq.length == sol.flatten.length
fail "invalid moves" unless check_valid_movement(sol)
puts "valid moves!"
end



__END__

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 10000

real 1m34.483s
user 1m29.471s
sys 0m3.695s

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 15000

real 4m47.336s
user 4m30.390s
sys 0m11.935s

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 25000

real 23m0.525s
user 21m47.343s
sys 0m50.721s

26700 = gave up after 45min, incomplete. 30000 = gave up after 3
hours, incomplete.

 

[Elliot Temple]

You get extra points for:

- Finding more about this game (name, origin, related articles)
- Filling a 5x5 board with only pen and paper
- Filling a bigger board with only pen and paper
- Finding the worst attempt possible for a given size. For example,
getting stuck after 10 steps on a 5x5 board is pretty bad:

You can get stuck in 6 steps on 6x6 or larger:

-------------------------
| . . . . . . |
| 5 . . 4 . . |
| . . . . . . |
| . . 1 . . 2 |
| . . . . . . |
| 6 . . 3 . . |
-------------------------

For 5x5, I found 9 steps (which is just your example with the first
step removed b/c it wasn't needed):

-------------------
| . 5 2 . 6|
| . . 8 . .|
| 3 . . 4 1|
| . . . . 7|
| . . 9 . .|
-------------------






-- Elliot Temple
http://www.curi.us/blog/

 

[Suraj N. Kurapati]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Here is my solution, which uses recursion like the Civilization II
map generation example in Chris Pine's "Learn to Program" book.

With a stack limit of:

$ ulimit -s
8192

the maximum square size my solution can handle is 67x67. However, it
can handle larger squares if you increase the stack size.

Cheers.


#!/usr/bin/ruby -w
# @param 1 width of square
# @param 2 starting row (X coordinate)
# @param 3 starting column (Y coordinate)

class Square < Array
def initialize aWidth
super(aWidth) { Array.new aWidth }
@mark = 0
end

# Walks this square, from the given position,
# while marking unmarked (nil) cells.
def walk x, y
# skip invalid positions and marked cells
return if
x < 0 or x >= length or
y < 0 or y >= length or
self[x][y]

# mark the current cell
self[x][y] = @mark += 1

# walk to adjacent cells
walk x + 3, y # east
walk x + 2, y - 2 # north east
walk x, y - 3 # north
walk x - 2, y - 2 # north west
walk x - 3, y # west
walk x - 2, y + 2 # south west
walk x, y + 3 # south
walk x + 2, y + 2 # south east
end

# Pretty-prints this square.
def to_s
# pretty-print each row
fmt = '|' << "%#{length.to_s.length * 2}d " * length << '|'

lines = inject([]) do |memo, row|
memo << fmt % row
end

# add a border to top & bottom
border = '-' * lines.first.length

lines.unshift border
lines << border

lines.join("\n")
end
end

if $0 == __FILE__
# create a square with user's parameters
width = (ARGV.shift || 5).to_i
square = Square.new(width)

# walk the square from random position
origin = Array.new(2) { (ARGV.shift || rand(width)).to_i }
square.walk(*origin)

# pretty-print the walked square
puts square.to_s
end
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE32aYmV9O7RYnKMcRAqRyAKCxvnyB1ncwLl4IhM6vg20wjKz9AACfTZgC
yQFdSn2EBLE1YWrts0TGRXk=
=4dbC
-----END PGP SIGNATURE-----

 

[Justin Collins]

Here's my solution, which works the same way as Elliot's first solution,
although with very different code:
It picks a random starting position, then finds all available moves from
there, sorts them randomly, then picks the one with the fewest moves
available.
Without the random sort, you'll always move in a similar pattern. It
seems to work a little bit better with the random sort.

I also ended up spending some time on getting nice looking output.
And it could certainly be made more efficient.

class Board
def initialize(size)
@board = Array.new(size) { Array.new(size) { '.' } }
@size = size
@current = 1
end

#Checks if the spot at (x, y) is available
def available?(x, y)
if x >= 0 and x < @size and y >= 0 and y <= @size
@board[x][y] == '.'
else
false
end
end

#Returns a list of pairs which can be reached from (x, y)
def available_from(x, y)
available = [[x, y - 3], [x + 2, y - 2], [x + 3, y], [x + 2, y +
2], [x, y + 3], [x - 2, y + 2], [x - 3, y],[x - 2, y - 2]].map { |pair|
available?(*pair) ? pair : nil }.compact
end

#Checks if the board is completed
def full?
@size**2 < @current
end

#Marks the spot at (x,y)
def mark(x, y)
if available?(x, y)
@board[x][y] = @current
@current += 1
else
raise "#{x},#{y} is not available"
end
end

#Nice box output
def to_s
lines = "-" + "-"*5*@size + "\n"
out = ""
out << lines
@board.each do |row|
out << "|" << row.map { |num| num.to_s.rjust(4) }.join(' ')
<< "|\n"
end
out << lines
end
end

raise "Please supply size" if ARGV[0].nil?

size = ARGV[0].to_i
raise "Size must be greater than 4" if size < 5

success = false

until success
board = Board.new(size)

#Pick random starting point
x = rand(size)
y = rand(size)

#Mark the board there
board.mark(x,y)
success = true

#Fill the board
until board.full?
avail = board.available_from(x, y).sort { rand }

#No moves available
if avail.empty?
puts "Cannot proceed"
success = false
break
end

#Pick the best available move
best = avail.inject { |best, pair|
board.available_from(*pair).length <
board.available_from(*best).length ? pair : best
}

#Mark the board
x, y = best
board.mark(x, y)
end
end

#Output the solution
puts board


-Justin

 

[Boris Prinz]

Hi,

my solution is recursive and works only for small boards. The largest
I solved was
9x9 (in 45 minutes):
1 81 70 2 15 35 3 10 17
72 58 41 79 59 38 78 60 24
69 53 46 36 29 9 16 30 4
40 80 71 39 14 34 25 11 18
73 57 42 52 47 37 77 61 23
68 54 45 65 28 8 21 31 5
43 51 48 56 13 33 26 12 19
74 64 67 75 63 66 76 62 22
49 55 44 50 27 7 20 32 6

The main work is done in "each_neighbour" which iterates through all
possible hops.
The board is a one-dimensional array, so it's easy to clone.

Regards,
Boris


### pnp.rb
class PenAndPaper
def initialize(width)
@width = width
end

def each_neighbour(pos)
w = @width
x = pos % w
y = pos / w
# north
yield(pos - 3*w) if y > 2
# north east
yield(pos - 2*w + 2) if y > 1 and x < w - 2
# east
yield(pos + 3) if x < w - 3
# south east
yield(pos + 2*w + 2) if y < w - 2 and x < w - 2
# south
yield(pos + 3*w) if y < w - 3
# south west
yield(pos + 2*w - 2) if y < w - 2 and x > 1
# west
yield(pos - 3) if x > 2
# north west
yield(pos - 2*w - 2) if y > 1 and x > 1
end

def solve(pos=0)
board = []
board[pos] = 1
@board = solve_board(board, pos, 2)
end

def solve_board(board, pos, ind)
return board if ind > @width*@width
each_neighbour(pos) do |n|
next if board[n] # position already taken?
f = board.dup
f[n] = ind
f2 = solve_board(f, n, ind + 1)
return f2 if f2
end
nil # no more positions
end

def to_s
s = ''
(0...@width).each do |y|
(0...@width).each do |x|
s += "%3d " % @board[y*@width+x]
end
s += "\n"
end
s
end
end



### test_pnp.rb
require 'test/unit'
require 'pnp'

class PenAndPaperTest < Test::Unit::TestCase
def neighbours_of(pos)
neighbours = []
pnp = PenAndPaper.new(5)
pnp.each_neighbour(pos) {|i| neighbours << i}
neighbours
end

def test_neighbours
assert_equal [ 3, 12, 15], neighbours_of(0)
assert_equal [14, 17, 10], neighbours_of(2)
assert_equal [18, 11, 0], neighbours_of(3)
assert_equal [22, 11, 2], neighbours_of(14)
assert_equal [ 2, 9, 5], neighbours_of(17)
assert_equal [ 5, 12, 23], neighbours_of(20)
assert_equal [ 9, 21, 12], neighbours_of(24)
end

def test_solve
pnp = PenAndPaper.new(5)
pnp.solve(0)
assert_equal <<END, pnp.to_s
1 22 12 2 7
19 25 5 20 10
13 16 8 23 15
4 21 11 3 6
18 24 14 17 9
END
end
end

 

[Justin Collins]

Here's my solution, which works the same way as Elliot's first
solution, although with very different code:

Forgot to include some times, for those interested:

[justin@cheese ruby]$ time -p ruby penpaper.rb 5 > /dev/null
real 0.00
user 0.00
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 50 > /dev/null
real 0.63
user 0.63
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 100 > /dev/null
real 2.66
user 2.65
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 200 > /dev/null
real 11.59
user 11.58
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 300 > /dev/null
real 233.48
user 233.45
sys 0.02
[justin@cheese ruby]$ time -p ruby penpaper.rb 400 > /dev/null
real 332.94
user 332.91
sys 0.02


Note that the times for the larger boards almost certainly include
multiple attempts.

-Justin

 

[Sander Land]

My solution also uses the Warnsdorff heuristic (moving to the square
with the least amount of possible moves left).
It works very well for sizes under 100 or so, gets worse after that
and starts taking hundreds of tries at about n=175.

I also included an option to see how long tours are starting from each
square (give the script any second parameter to show this).
This shows how well (or poor) the algorithm works for that size, but
it's obviously quite slow for larger sizes as it runs the algorithm
for every square.


Pastie link: http://pastie.caboo.se/8427
Code:

module Enumerable
def x(enum) # Cartesian product
map{|a| enum.map{|b| [a,b].flatten }}.inject([]) {|a,b| a+b}
end
def **(n) # Cartesian power
if n == 1
self
else
self.x(self**(n-1))
end
end
end

module OpenStructable
def method_missing(method,*args)
(class<<self;self;end).sendattr_accessor, method.to_s.sub('=','') )
send(method,*args)
end
end

class Vertex < Array
include OpenStructable
def initialize(name)
self.name = name
end
end

class Graph
def initialize
@vertices = Hash.new{|h,k| h[k] = Vertex.new(k) }
end

def add_edge(from,to)
@vertices[from] << @vertices[to]
end

def warnsdorff_tour(start)
@vertices.each_value{|v|
v.score = v.size
v.done = false
}
curr_node = @vertices[start]
tour = []
while curr_node
tour << curr_node
curr_node.done = true
curr_node.each{|v| v.score -= 1}
curr_node = curr_node.reject{|v| v.done}.sort_by{|v| v.score}.first
end
tour.map{|t| t.name}
end

end

n = (ARGV[0] || 5).to_i
graph = Graph.new

dirs = [2,-2]**2 + [[0,3],[3,0],[0,-3],[-3,0]]

valid = 0...n

(valid**2).each {|x,y|
dirs.each{|dx,dy|
to_x, to_y = x + dx, y + dy
graph.add_edge([x,y] , [to_x,to_y]) if valid.include?(to_x) &&
valid.include?(to_y)
}
}
grid = Array.new(n){Array.new(n)}

# This shows how long a tour starting from each square is
if ARGV[1]
full_count = 0
(valid**2).each{|x,y|
grid[y][x] = graph.warnsdorff_tour([x,y]).length
full_count += 1 if grid[y][x] == n*n
}
puts "#{full_count} / #{n*n} = #{'%.2f' %
[100*full_count.to_f/(n*n)]} % of the possible starting positions give
a full tour."
else

solution = []
try = 0
([0,n-1]**2 + [0].x(1..n-2) + (1..n-2)**2).each{|sx,sy| # for
starting square, try corners first, then one edge, then inside
try += 1
solution = graph.warnsdorff_tour([sx,sy])
break if solution.length == n*n
}

if solution.length != n*n
puts "Failed to find tour."
exit!
end
puts "Found tour in #{try} tries."

solution.each_with_index{|(x,y),i| grid[y][x] = i+1 }
end

max_len = (n * n).to_s.length

sep = ('+' + '-' * (max_len+2) ) * n + '+'
puts sep, grid.map{|row| '| ' + row.map{|n| n.to_s.center(max_len)
}.join(' | ') + ' |' }.join("\n" + sep + "\n"), sep

 

[Suraj N. Kurapati]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Here is my solution, which uses recursion like the Civilization II
map generation example in Chris Pine's "Learn to Program" book.

With a stack limit of:

$ ulimit -s
8192

the maximum square size my solution can handle is 67x67. However, it
can handle larger squares if you increase the stack size.

Well, I discovered that this solution doesn't always find the
correct answer, so I fixed it accordingly. Now I can see why Eric
DUMINIL said a *brute force* approach is too slow.

Thanks for the fun quiz.


#!/usr/bin/ruby -w
# @param . width of square
# @param . starting row
# @param . starting column

class Square < Array
def initialize aWidth
super(aWidth) { Array.new aWidth }
@mark = 0
@size = aWidth ** 2
end

# Walks this square, from the given position,
# while marking unmarked (nil) cells.
def walk row, col
# skip invalid positions and marked cells
return false if
row < 0 or row >= length or
col < 0 or col >= length or
self[row][col]

# mark the current cell
self[row][col] = @mark += 1

# explore adjacent paths
if @mark >= @size or
walk(row + 3, col ) or # east
walk(row + 2, col - 2) or # north east
walk(row, col - 3) or # north
walk(row - 2, col - 2) or # north west
walk(row - 3, col ) or # west
walk(row - 2, col + 2) or # south west
walk(row, col + 3) or # south
walk(row + 2, col + 2) # south east

true
else
# unmark the current cell
@mark -= 1
self[row][col] = nil

false
end
end

# Pretty-prints this square.
def to_s
# pretty-print each row
fmt = '|' << "%#{length.to_s.length * 2}d " * length << '|'

lines = inject([]) do |memo, row|
memo << fmt % row
end

# add a border to top & bottom
border = '-' * lines.first.length

lines.unshift border
lines << border

lines.join("\n")
end
end

if $0 == __FILE__
# create a square with user's parameters
width = (ARGV.shift || 5).to_i
square = Square.new(width)

# walk the square from random position
origin = Array.new(2) { (ARGV.shift || rand(width)).to_i }
square.walk(*origin)

# pretty-print the walked square
puts square.to_s
end
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE35TumV9O7RYnKMcRAkezAKCUQQS7HsRq+MkdRsi4xYWbjXIdnQCfS6no
2e9bpIoRRP1XuXgHe275Pso=
=miH9
-----END PGP SIGNATURE-----

 

[Robert Evans]

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

 

[darren kirby]

--nextPart3944529.CyYQA1ERhg
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

quoth the Elliot Temple:

You can get stuck in 6 steps on 6x6 or larger:

-------------------------

-------------------------
| . . . . . . |
| 5 . . 4 . . |
| . . . . . . |
| . . 1 . . 2 |
| . . . . . . |
| 6 . . 3 . . |
=2D------------------------

Am I missing something here? Your vertical moves are jumping 3 squares...
=46rom the rules:

- jumping over 2 squares when traveling horizontally or vertically
- jumping over 1 square when traveling diagonally.

-- Elliot Temple
http://www.curi.us/blog/

=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

--nextPart3944529.CyYQA1ERhg
Content-Type: application/pgp-signature

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

iD8DBQBE39utwPD5Cr/3CJgRAinpAJ4tnqZ1FUFzw1eCJ3kKWpSpNQDqdACfWTR8
0OH1a2ZSOeQYL2oYNlAL0LI=
=Spm1
-----END PGP SIGNATURE-----

--nextPart3944529.CyYQA1ERhg--

 

[darren kirby]

--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--

 

[Elliot Temple]

quoth the Elliot Temple:

-------------------------
| . . . . . . |
| 5 . . 4 . . |
| . . . . . . |
| . . 1 . . 2 |
| . . . . . . |
| 6 . . 3 . . |
-------------------------

Am I missing something here? Your vertical moves are jumping 3
squares...
From the rules:

i think jumping over 2 squares means landing on third square away.
that's what it looked like in the examples.

-- Elliot Temple
http://www.curi.us/blog/

 

[Elliot Temple]

i think jumping over 2 squares means landing on third square away.
that's what it looked like in the examples.

oh haha. there are typos. the 4 and 5 should be one row lower. i
think it's right then.

-- Elliot Temple
http://www.curi.us/blog/

 

[darren kirby]

--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--