[QUIZ] Knight's Travails (#27)

ruby-talk
1

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!

···

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

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.

2

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.rubyquiz.com/

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

3

[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

4

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

5

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

6

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

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

rubyquiz (3.29 KB)

7

# Ruby Quiz #27, Knight's Travails

···

#
# Author: Kero van Gelder
# License: LGPL, see http://www.gnu.org/licenses/lgpl.html
#
# 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 :stuck_out_tongue:

# 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

8

A very late entry for the knigh's travail. The solution can be found at:

http://ruby.brian-schroeder.de/quiz/knights-travail/

It's just the standard dijkstra.

regards,

Brian

···

--
http://ruby.brian-schroeder.de/

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabulaire.org/ | http://www.gloser.org/ | http://www.vokabeln.net/

9

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

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

10

[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.)

11

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

12

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]

If you just want to accumualte an array, here is a snippet from the
Programming Ruby HTML book:

(1..10).to_a » [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

-- Timothy
just realized I should have added start_pos to my initial forbidden
array so the algorithm wouldn't try to double back.

13

Kero wrote:

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

Oh, I wish I thought of that, my solution has to reverse the path afterwards :frowning:

14

And here is an iterative, breadth-first search that can be used in
place of my find_path_recurse().

module Knight

    def self.find_path_bf(pStart, pEnd, forbidden)

        # Are we there yet?

···

#
        return [pEnd.clone] if pStart == pEnd

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

        position_list = Hash.new
        forbidden.each {|f| position_list[f] = 'forbidden' }
        position_list[pStart] = []

        moves_to_check = [pStart]

        until moves_to_check.empty? do
            pos = moves_to_check.shift
            possible_moves(pos).each do |m|
                next if position_list[m]
                position_list[m] = position_list[pos] + [m]
                return position_list[m] if m == pEnd
                moves_to_check.push(m)
            end
        end

        nil
    end
end

-- Timothy

15

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

16

Thanks for the reply, but that wasn't the intetion.

While coding the solution, I first had something like this in my find_path method:

front=[start]
until front.empty?
   pos=front.shift
   all_moves(pos) { |m|
     if ...
       front << m
     end
   }
end

I experimented a bit and changed it to the following:

(front=[start]).each { |pos|
   all_moves(pos) { |m|
     if ...
       front << m
     end
   }
}

It basicly does the same. And I wondered if this is "defined" behavior, or if it is just coincidence, that it works (adding elements to front, while iterating over it).

Dominik

···

On Mon, 11 Apr 2005 06:49:37 +0200, Timothy Byrd <byrd.timothy@gmail.com> wrote:

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]

If you just want to accumualte an array, here is a snippet from the
Programming Ruby HTML book:

(1..10).to_a » [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]