Asp Forum - [QUIZ] Knight's Travails (#27

James Gray

4/8/2005 6:38:00 PM

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

3. Enjoy!

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

by Jason Bailey

Given a standard 8 x 8 chessboard where each position is indicated in algebraic
notation (with the lower left corner being a1), design a script that accepts two
or more arguments.

The first argument indicates the starting position of the knight. The second
argument indicates the ending position of the knight. Any additional arguments
indicate positions that are forbidden to the knight.

Return an array indicating the shortest path that the knight must travel to get
to the end position without landing on one of the forbidden squares. If there is
no valid path to the destination return nil.

example 1:
a8, b7, b6

could return
[ c7 , b5 , d6 , b7 ]

Example 2:
a8 , g6 , b6 , c7

would return
nil

Note: That in the majority of cases it would be possible to have more then one
valid path.

15 Answers

ptkwt

4/10/2005 12:53:00 AM

In article <20050408183742.VWMB18351.lakermmtao08.cox.net@localhost.localdomain>,
Ruby Quiz <james@grayproductions.net> wrote:
>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.rub...
>
>3. Enjoy!
>
>-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
>by Jason Bailey
>
>Given a standard 8 x 8 chessboard where each position is indicated in algebraic
>notation (with the lower left corner being a1), design a script that
>accepts two
>or more arguments.
>
>The first argument indicates the starting position of the knight. The second
>argument indicates the ending position of the knight. Any additional arguments
>indicate positions that are forbidden to the knight.

Sounds fun... <sigh>I just wish I had the time...</sigh>

Phil

Carlos

4/10/2005 2:48:00 PM

[Ruby Quiz <james@grayproductions.net>, 2005-04-08 20.38 CEST]
> Return an array indicating the shortest path that the knight must travel to get
> to the end position without landing on one of the forbidden squares. If there is
> no valid path to the destination return nil.

Here is a solution. I'm having a hard time trying to explain it in English,
I hope the code is clear enough (it's very simple).

Thanks.

# code:

class String
def to_coords
return [self[0] - ?a, self[1] - ?1]
end
end

class Array
def to_algebraic
return (self[0] + ?a).chr + (self[1] + ?1).chr
end
end

def where_can_jump_from (here, visited)
col, row = here
[
[col+2, row+1], [col+2, row-1], [col+1, row-2], [col-1, row-2],
[col-2, row-1], [col-2, row+1], [col-1, row+2], [col+1, row+2]
].select { |c,r|
r >= 0 && r < 8 && c >= 0 && c < 8 && !visited[c][r]
}
end

def knight_path (start_pos, finish_pos, forbidden)
visited = Array.new(8) { Array.new(8) }
forbidden.each do |col,row| visited[col][row] = true end

# special cases:
# shortest path: no movement at all
return [] if start_pos == finish_pos
# impossible task:
return nil if forbidden.include? finish_pos

# setup...
paths = [[start_pos]]
visited[start_pos[0]][start_pos[1]] = true

while !paths.empty?
# pp paths.map {|p| p.map {|c| c.to_algebraic } }
new_paths = []
paths.each do |path|
where_next = where_can_jump_from(path.last, visited)
where_next.each do |coord|
newpath = path.dup << coord
if coord == finish_pos
# clear first cell (start position)
newpath.shift
return newpath
end
c, r = coord
visited[c][r] = true
new_paths.push newpath
end
end
paths = new_paths
end

return nil
end

start_pos = ARGV.shift.to_coords
finish_pos = ARGV.shift.to_coords
forbidden = ARGV.map {|arg| arg.to_coords }

result = knight_path start_pos, finish_pos, forbidden

if (result)
result.map! { |coord| coord.to_algebraic }
puts "[ " + result.join(" , ") + " ]"
else
p nil
end

Timothy Byrd

4/10/2005 5:51:00 PM

Here's mine - still very C-like...

module Knight

Moves = [
[-2,-1], [-2, 1], [2,-1], [2, 1],
[-1,-2], [-1, 2], [1,-2], [1, 2]
]

def self.possible_moves(pos)
result = []
mv = 'a1'

Moves.each {|delta|
(0..1).each { |i| mv[i] = pos[i] + delta[i] }
if (?a..?h).include?(mv[0]) && (?1..?8).include?(mv[1])
result.push(mv.clone)
end
}
result
end

def self.find_path_recurse(pStart, pEnd, forbidden, max_moves = 64)

# Are we there yet?
#
return [pEnd.clone] if pStart == pEnd

# You can't get there from here!
#
return nil if forbidden.include?(pEnd) || max_moves <= 0

moves = possible_moves(pStart)
moves.delete_if {|x| forbidden.include?(x)}

return [pEnd.clone] if moves.include?(pEnd)

best_solution = nil
moves_left = max_moves - 1
cant_go = forbidden.clone.concat(moves)

moves.each do |m|
s = find_path_recurse(m, pEnd, cant_go, moves_left)
next if !s

s.insert(0, m)
if !best_solution || s.size < best_solution.size
# From now on only interested in solutions that
# are at least two moves shorter
#
moves_left = s.size - 2
best_solution = s
end
end

best_solution
end

def self.find_path(pStart, pEnd, forbidden)
forbidden = [] if !forbidden
if forbidden.empty?
puts "From #{pStart} to #{pEnd}"
else
puts "From #{pStart} to #{pEnd} excluding
[#{forbidden.join(', ')}]"
end
s = find_path_recurse(pStart, pEnd, forbidden, 64)
if s
puts s.join(', ')
else
puts nil
end
puts ''
end
end

if ARGV[1]
Knight.find_path(ARGV[0], ARGV[1], ARGV[2..-1])
else
Knight.find_path('a8', 'b7', ['b6'])
Knight.find_path('a8', 'g6', ['b6', 'c7'])
end

Dominik Bathon

4/10/2005 6:31:00 PM

Here is my solution:
It uses a ChessPos class to validate the given positions and to simplify
the moves.
The find_path method uses Dijkstra's Shortest Path Algorithm in a
simplified form.

Btw. does anybody know if this behavior is defined somewhere (adding
elements to an Array while iterating over it):
irb(main):001:0> (a=[0]).each { |i| a << i+1 if i < 10 }; a
=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The Code:

class ChessPos
attr_reader :pos

def initialize(str)
unless str.size==2 && (?a..?h).include?(str[0]) &&
(?1..?8).include?(str[1])
raise "#{str} is not a valid chess position"
end
@pos=str
end

def move(x, y)
ChessPos.new((pos[0]+x).chr+(pos[1]+y).chr)
end

def hash; pos.hash; end
def eql?(other); pos.eql?(other.pos) rescue false; end
alias :== :eql?
end

def all_knight_moves_from(pos)
[-2, -1, 1, 2].each { |x|
yt=3-x.abs
[-yt, yt].each { |y|
np=(pos.move(x, y) rescue nil)
yield np if np
}
}
end

def find_path(start, endp, forbidden={})
# simplified dijkstra
# all weights are equal -> no sorting
return [] if start==endp
pre=forbidden.merge({start=>nil})
(front=[start]).each { |pos|
all_knight_moves_from(pos) { |m|
unless pre.has_key? m # if not visited before
pre[m]=pos
front << m
if (endp==m) # path found
path=[endp]
path.unshift(pos) until start==(pos=pre[path[0]])
return path
end
end
}
}
nil
end

def main(s, e, *forb)
forbidden={}
forb.each { |f| forbidden[ChessPos.new(f)]=nil } # all keys are
forbidden
if path=find_path(ChessPos.new(s), ChessPos.new(e), forbidden)
puts "[ #{path.collect { |p| p.pos }.join(", ")} ]"
else
puts nil
end
end

main(*ARGV) rescue puts $!.message

linus sellberg

4/10/2005 6:33:00 PM

Here is my solution. It could use a fair bit of refactoring, but I'm too
tired now to do it :)

start_node, end_node,*forbidden = ARGV
start_node = [start_node[0] - 97, Integer(start_node[1,1]) - 1]
end_node = [end_node[0] - 97, Integer(end_node[1,1]) - 1]

success = false

Moves = [[1,2],[-1,2],[1,-2],[-1,-2],
[2,1],[-2,1],[2,-1],[-2,-1]]

board = Array.new(8) { Array.new(8) }

forbidden.each{|el|
board[el[0] - 97][Integer(el[1,1]) - 1] = :forbidden
}

board[start_node[0]][start_node[1]] = :start
queue = [start_node]

queue.each{ |i,j|
#create some moves
Moves.collect {|k,l|
[i+k, j+l]
}.reject{|k,l|
#remove the impossible and already used moves
k < 0 || l < 0 || k > 7 || l > 7 || (board[k][l])
}.collect{|k,l|
#checks if done, end looping or equeue the move.
if [k,l] == end_node
success = true
queue = []
else
queue << [k,l]
end
#mark the node
board[k][l] = [i,j]#node
}
}

if success
#traverse backwards from the end node
path = [end_node]
path.inject([]){|acc,node|
unless node == start_node
path << board[node[0]][node[1]]
acc << node
end
}

path.reverse!

path.each{|node|
i,j = *node
print (i+97).chr
puts j + 1
}
else
puts "no path found"
end

linus sellberg

4/10/2005 7:03:00 PM

linus sellberg wrote:
> #traverse backwards from the end node
> path = [end_node]
> path.inject([]){|acc,node|
> unless node == start_node
> path << board[node[0]][node[1]]
> acc << node
> end
> }

I wonder what I thought here, this should be an #each instead, I never
use the accumulated value :)

Ghislain MARY

4/10/2005 7:28:00 PM

Here's my first attempt to a ruby quiz :)

I take a look at what is happening here all weeks since a certain amount
of time now but have never posted a solution. First I'd like to say that
I found the last week's quiz very interesting even if there was only a
small participation. I wish I could have sent a solution but I didn't
have the time for this.

So, back to this week's quiz, my solution is simply a breadth-first tree
walk. I believe there may be a simplier way to solve this but that's
what I came with and it works. So I'm really happy with it :)
However, even with the code part, I think it could be more rubyist, and
so, prettier to read. Any comments on it are welcome.

Thanks a lot for this quiz. I'm waiting for the other's solution and of
course for the next quiz.

Ghislain
#!/usr/bin/env ruby# -*- coding: UTF-8 -*-# A Position on the chess board. Can be checked if valid using the# Position#valid? method.class Position < String # Create a new position. Default to 'a1'. def initialize(value = 'a1') super(value) end # Check whether the Position if valid (between 'a1' to 'h8'). def valid? self =~ /[a-h][1-8]/ end # Apply a move to a Position, returning a new Position. def change(move) value = self.dup value[0] += move[0] value[1] += move[1] Position.new(value) endend# Represent the Knight which will try to find his way on the chess board# labyrinth we imaginated for him.class Knight # The moves that the Knight is allowed to do. VALID_MOVES = [ [-2, -1], [-1, -2], [ 1, -2], [ 2, -1], [ 2, 1], [ 1, 2], [-1, 2], [-2, 1] ] # Create a new Knight. def initialize(initial_position) @position = Position.new(initial_position) @path = nil @forbidden_positions = [] end # Define the positions where the Knight is not allowed to go. def forbidden_positions=(forbidden_positions) forbidden_positions.each do |position| @forbidden_positions << Position.new(position) end end # Ask to find the path to the final Position _final_position_. def find_path_to(final_position) @final_position = Position.new(final_position) find_path end private # Recursive method to search the shortest path. def find_path(paths = [[@position]]) if not @path and finished?(paths) return @path else new_paths = [] change = false paths.each do |path| possible_positions?(path).each do |position| new_paths << path.dup.push(position) change = true end end find_path(new_paths) if change end end # Check if the Knight has found is way out of here. def finished?(paths) paths.each do |path| if path.last == @final_position @path = path[1..-1] end end @path end # Find the positions where the Knight can go knowing the path he # already has taken. def possible_positions?(already_passed = []) possible_positions = [] Knight::VALID_MOVES.each do |move| possible_position = already_passed.last.change(move) if possible_position.valid? and not already_passed.include?(possible_position) and not @forbidden_positions.include?(possible_position) possible_positions << possible_position end end possible_positions endendif ARGV.size < 2 puts "usage: ruby knight.rb initial_position final_position [(forbidden positions)*]"else # Check if all positions passed as argument are valid begin ARGV.each do |position| raise Exception.new("Invalid position #{ position }") unless Position.new(position).valid? end rescue Exception => e puts e exit end # Solve the problem knight = Knight.new(ARGV[0]) knight.forbidden_positions=(ARGV[2..-1]) puts knight.find_path_to(ARGV[1])end

Carlos

4/10/2005 8:13:00 PM

[Ghislain Mary <nospam@lunacymaze.org>, 2005-04-10 21.27 CEST]
> However, even with the code part, I think it could be more rubyist, and
> so, prettier to read. Any comments on it are welcome.

(!) Your code is clear as water. I think yours is the most readable solution
so far. (And linus' the best thought.)

Matthew Moss

4/10/2005 10:18:00 PM

Here's my solution... This actually turned out to be relatively easy
for me, both in algorithm and programming. Simple but fun problem.

#!/usr/bin/env ruby

# Helper class
class Tile
attr_reader :x, :y
protected :x, :y

def initialize(x, y)
@x, @y = x, y
end

def Tile.named(s)
Tile.new(s.downcase[0] - 'a'[0], s.downcase[1] - '1'[0])
end

def valid?
(0...8) === @x and (0...8) === @y
end

def to_s
to_str
end

def to_str
%w(a b c d e f g h)[@x] + %w(1 2 3 4 5 6 7 8)[@y] if valid?
end

def ==(c)
@x == c.x and @y == c.y
end

def adjacent?(c)
dx = (@x - c.x).abs
dy = (@y - c.y).abs
valid? and c.valid? and (dx == 1 && dy == 2 or dx == 2 && dy == 1)
end
end

def knights_trip(start, finish, *forbidden)
# First, build big bucket o' tiles.
board = (0...64).collect { |n| Tile.new(n % 8, n / 8) }

# Second, pull out forbidden tiles.
board.reject! { |t| forbidden.include?(t) }

# Third, prepare a hash, where layer 0 is just the start.
# Remove start from the board.
x = 0
flood = { x => [start] }
board.delete(start)

# Fourth, perform a "flood fill" step, finding all board tiles
# adjacent to the previous step.
until flood[x].empty? or flood[x].include?(finish) do
x += 1
flood[x] = flood[x-1].inject([]) do |mem, obj|
mem.concat(board.find_all { |t| t.adjacent?(obj) })
end

# Remove those found from the board.
board.reject! { |t| flood[x].include?(t) }
end

# Finally, determine if we found a way to the finish and, if so,
# build a path.
if not flood[x].empty?
# We found a way. Time to build the path. This is built
# backwards, so finish goes in first.
path = [finish]

# Since we got to finish in X steps, we know there must be
# at least one adjancent to finish at X-1 steps, and so on.
until x == 0
x -= 1

# Find in flood[x] a tile adjacent to the head of our
# path. Doesn't matter which one. Make it the new head
# of our path.
jumps = flood[x].find_all { |t| t.adjacent?(path.first) }
path[0,0] = jumps.sort_by { rand }.first
end

# Tada!
path
end
end

# main
args = ARGV.collect { |arg| Tile.named(arg) }
if args.any? { |c| not c.valid? }
puts "Invalid argument(s)!"
else
trip = knights_trip(*args)
if trip
puts "Knight's trip: " + trip.join(", ")
else
puts "No route available!"
end
end

Kero van Gelder

4/10/2005 10:57:00 PM

# Ruby Quiz #27, Knight's Travails
#
# Author: Kero van Gelder
# License: LGPL, see http://www.gnu.org/licenses...
#
# Given: Chess board, start_pos, finish_pos and forbidden squares
# Find: a shortest route from start to finish, for a knight, without using the
# forbidden squares.
#
# Observations:
# - shortest path requires Dijkstra, but all distances are 1, so we do not need
# a priority queue, we can use a regular queue
# - breadth first search like this (dynamic programming style, too) keeps
# pointers (steps) towards the point where you start the algorithm, so we
# have to start at the finish. Quite normal for Dijkstra, now that I think of
# it...
#
# Apologies for:
# - not checking the input (ignoring commas happily, no spaces)
# - the use of @board and @q which are pseudo-global variables
# - not returning an array, but printing the result (hey, you left the
# *content* of the array undescribed; mine is like [[?b, 7], [?c, 5]],
# perhaps you need ["b7", "c5"] ?) Printing is with spaces before the commas,
# too? How tasteless :P

# Input helper
def decode_pos(str)
[str[0], str[1,1].to_i]
end

# Used in breadth first search
def try_pos(c, d, rc, rd)
(c >= ?a and c <= ?h) or return
(d >= 1 and d <= 8) or return
unless @board[c][d]
@board[c][d] = [rc, rd]
@q << [c, d]
end
end

start_pos, finish_pos, *forbidden = *ARGV
@board = {}
(?a..?h).each { |c| @board[c] = [] }
forbidden.each { |pos|
c, d = decode_pos(pos)
@board[c][d] = :forbidden
}

fc, fd = decode_pos(finish_pos)
@board[fc][fd] = :finish
@q = [[fc, fd]]
sc, sd = decode_pos(start_pos)

while not @q.empty?
c, d = *@q.shift
break if c == sc and d == sd
try_pos(c-2, d-1, c, d)
try_pos(c-2, d+1, c, d)
try_pos(c-1, d-2, c, d)
try_pos(c-1, d+2, c, d)
try_pos(c+1, d-2, c, d)
try_pos(c+1, d+2, c, d)
try_pos(c+2, d-1, c, d)
try_pos(c+2, d+1, c, d)
end

# It is a good defensive programming habit to look whether you actually found a
# solution (and don't check q.empty? as I did, 'coz the queue will be empty
# when the search looked at all 64 squares for a route from e.g. a8 to h1).
if @board[sc][sd]
route = []
rc, rd = sc, sd
while rc != fc or rd != fd
next_pos = @board[rc][rd]
route << "#{next_pos[0].chr}#{next_pos[1]}"
rc, rd = *next_pos
end
puts "[ #{route.join" , "} ]"
else
puts nil
end

comp.lang.ruby

[QUIZ] Knight's Travails (#27

James Gray

ptkwt

Carlos

Timothy Byrd

Dominik Bathon

linus sellberg

linus sellberg

Ghislain MARY

Carlos

Matthew Moss

Kero van Gelder

x Login to ForumsZone