[QUIZ] Knight's Travails (#27)

Discussion in 'Ruby' started by Ruby Quiz, Apr 8, 2005.

  1. Ruby Quiz

    Ruby Quiz Guest

    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.
    Ruby Quiz, Apr 8, 2005
    #1
    1. Advertising

  2. Ruby Quiz

    Phil Tomson Guest

    In article <>,
    Ruby Quiz <> 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
    Phil Tomson, Apr 10, 2005
    #2
    1. Advertising

  3. Ruby Quiz

    Carlos Guest

    [QUIZ][SOLUTION] Knight's Travails (#27)

    [Ruby Quiz <>, 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
    Carlos, Apr 10, 2005
    #3
  4. Ruby Quiz

    Timothy Byrd Guest

    Re: Knight's Travails (#27)

    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 = pos + delta }
    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
    Timothy Byrd, Apr 10, 2005
    #4
  5. [QUIZ][SOLUTION] Knight's Travails (#27)

    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
    Dominik Bathon, Apr 10, 2005
    #5
  6. Re: [QUIZ][SOLUTION] Knight's Travails (#27)

    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, Apr 10, 2005
    #6
  7. Re: [QUIZ][SOLUTION] Knight's Travails (#27)

    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 :)
    linus sellberg, Apr 10, 2005
    #7
  8. Ruby Quiz

    Carlos Guest

    Re: [QUIZ][SOLUTION] Knight's Travails (#27)

    [Ghislain Mary <>, 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.)
    Carlos, Apr 10, 2005
    #8
  9. Re: [QUIZ][SOLUTION] Knight's Travails (#27)

    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
    Matthew D Moss, Apr 10, 2005
    #9
  10. Ruby Quiz

    Kero Guest

    # 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 :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
    Kero, Apr 10, 2005
    #10
  11. Ruby Quiz

    Timothy Byrd Guest

    Re: [SOLUTION] Knight's Travails (#27)

    > 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.
    Timothy Byrd, Apr 11, 2005
    #11
  12. 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 :(
    linus sellberg, Apr 11, 2005
    #12
  13. Re: [SOLUTION] Knight's Travails (#27)

    On Mon, 11 Apr 2005 06:49:37 +0200, Timothy Byrd <>
    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]


    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
    Dominik Bathon, Apr 11, 2005
    #13
  14. Ruby Quiz

    Timothy Byrd Guest

    Re: Knight's Travails (#27)

    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
    Timothy Byrd, Apr 12, 2005
    #14
  15. Brian Schröder, May 10, 2005
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    9
    Views:
    504
    Kai-Uwe Bux
    Jan 30, 2006
  2. Bert

    In 3 moves, where can the knight go?

    Bert, Jun 20, 2008, in forum: C Programming
    Replies:
    13
    Views:
    500
    Keith Thompson
    Jun 26, 2008
  3. Robin Rytich
    Replies:
    0
    Views:
    669
    Robin Rytich
    Mar 10, 2010
  4. Gabriel Genellina

    Knight's tour Warndorff's algorithm problem

    Gabriel Genellina, Mar 10, 2010, in forum: Python
    Replies:
    4
    Views:
    1,094
    Terry Reedy
    Mar 11, 2010
  5. Ruby Quiz

    [SUMMARY] Knight's Travails (#27)

    Ruby Quiz, Apr 14, 2005, in forum: Ruby
    Replies:
    3
    Views:
    182
    James Edward Gray II
    Apr 15, 2005
Loading...

Share This Page