R
Ruby Quiz
One neat aspect of doing a simple problem now and then is checking out the
elegant solutions people apply to it. With Ruby, that usually means some pretty
code, at least in my mind.
I enjoyed all of the solutions, as usual, but I really thought Matthew D Moss
wrote some code that showed off how pretty and clever Ruby can be. His solution
is overflowing with cool idioms, so let's dive right in. Here's a "helper
class" from the code:
# 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
I couldn't decide if I thought this class was named correctly. It represents a
square or "tile" of the chess board, but when I think of a square it's as a
container for a piece. That's not what we're dealing with here. This class
holds x and y coordinates for the square on the board, nothing more. Once you
grasp that, the code is easy to follow. You can see this setup right at the top
of the class with the x and y readers and initialize() storing the values. From
there though, the work gets interesting.
The Tile.named() method is another constructor. Instead of building a Tile from
x and y coordinates ranged from 0 to 7, it builds them from traditional chess
strings naming a square like "a4". As you can see, it really just does the
conversion and calls the other constructor. The first step is to convert the
leading letter to an index, which is done by normalizing case and subtracting
the character value of "a" from the character value of the square's letter. The
'a'[0] construct is a little unusual and I'm not sure why it's used here. Most
Ruby gurus just use ?a, which means the exact same thing. The second conversion
works the same way. I think the goal here was consistency, but obviously the
downcase() call isn't needed for the number.
The next method is valid?() and its only job is to say if this is a legal square
on a real chess board. That translates to needing x and y in the Range (0..7).
Note that these Ranges are actually built with the ... operator, which excludes
the last number. The === check is used in clauses for case statements, but
you're welcome to call it yourself, as you can see. It's an alias for
Range.member?(), which just checks that the second argument is in the Range.
Both to_s and to_str allow the object to behave as a String, as long as it's a
valid?() Tile. Here again, we have a unique conversion. %w(...) builds an
Array of Strings from the "words" inside the parentheses. In this case, they're
just individual letters and numbers. Those Arrays are indexed by x and y, and
the results concatenated with simple String addition (+).
The == method can quickly determine if two Tile objects represent the same
square just by comparing both x and y values for each object. If they both
match, the objects are equal.
Finally, adjacent?() checks to see if the passed Tile is near the current Tile.
Both "adjacent" and "near" are tricky explanations though; the method actually
verifies that the Tiles are within a Knight's jump of each other. Like the
other methods of this class, the process is clever. First, dx and dy are filled
with deltas for the two x and y values of each object. If both Tiles are
valid?() and one delta is 1 while the other is 2, they are a Knight's jump
apart.
The next section of code puts those Tiles to work:
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
The knights_trip() method does all the grunt work for this solution. You pass
it the start, finish, and forbidden Tiles. It will return a path, if one can be
found.
The method starts by building a Tile for every board square. After that, any
forbidden Tiles are removed, so they won't be considered.
Next comes the heart of the algorithm. A Hash is created with pairs of search
depth keys and value Arrays that represent all the Tiles at that depth. (Note
that an Array could be used in place of the Hash, since the keys are ordered
numerical indexes.) The until loop fills in the Hash by searching each
successive depth until running out of illegal moves or locating the finish Tile.
Each depth is built in the call to inject(), which just adds all the adjacent?()
Tiles from the previous depth to an empty Array. Tiles are always removed from
the board as they are added to the depth Hash to keep them from coming up as
adjecent?() to later Tile searches. The final if statement builds the path by
working backwards through the depth search Hash one ply at a time, looking for
adjacent?() Tiles.
It only takes a little more code to finish the solution off:
# 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
This snippet just puts the above methods to use. ARGV is translated into Tile
objects and all those Tiles, if valid?(), are fed to knights_trip(). If a path
is returned, it's printed. Otherwise, a route is not available and a message
relates this.
My thanks go out to all Knights who made the leap this week. As always, they
provided a bunch of interesting code to examine and I recommend you do so.
Tomorrow's quiz is a simple but fun little challenge that may bring back
childhood memories for some...
elegant solutions people apply to it. With Ruby, that usually means some pretty
code, at least in my mind.
I enjoyed all of the solutions, as usual, but I really thought Matthew D Moss
wrote some code that showed off how pretty and clever Ruby can be. His solution
is overflowing with cool idioms, so let's dive right in. Here's a "helper
class" from the code:
# 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
I couldn't decide if I thought this class was named correctly. It represents a
square or "tile" of the chess board, but when I think of a square it's as a
container for a piece. That's not what we're dealing with here. This class
holds x and y coordinates for the square on the board, nothing more. Once you
grasp that, the code is easy to follow. You can see this setup right at the top
of the class with the x and y readers and initialize() storing the values. From
there though, the work gets interesting.
The Tile.named() method is another constructor. Instead of building a Tile from
x and y coordinates ranged from 0 to 7, it builds them from traditional chess
strings naming a square like "a4". As you can see, it really just does the
conversion and calls the other constructor. The first step is to convert the
leading letter to an index, which is done by normalizing case and subtracting
the character value of "a" from the character value of the square's letter. The
'a'[0] construct is a little unusual and I'm not sure why it's used here. Most
Ruby gurus just use ?a, which means the exact same thing. The second conversion
works the same way. I think the goal here was consistency, but obviously the
downcase() call isn't needed for the number.
The next method is valid?() and its only job is to say if this is a legal square
on a real chess board. That translates to needing x and y in the Range (0..7).
Note that these Ranges are actually built with the ... operator, which excludes
the last number. The === check is used in clauses for case statements, but
you're welcome to call it yourself, as you can see. It's an alias for
Range.member?(), which just checks that the second argument is in the Range.
Both to_s and to_str allow the object to behave as a String, as long as it's a
valid?() Tile. Here again, we have a unique conversion. %w(...) builds an
Array of Strings from the "words" inside the parentheses. In this case, they're
just individual letters and numbers. Those Arrays are indexed by x and y, and
the results concatenated with simple String addition (+).
The == method can quickly determine if two Tile objects represent the same
square just by comparing both x and y values for each object. If they both
match, the objects are equal.
Finally, adjacent?() checks to see if the passed Tile is near the current Tile.
Both "adjacent" and "near" are tricky explanations though; the method actually
verifies that the Tiles are within a Knight's jump of each other. Like the
other methods of this class, the process is clever. First, dx and dy are filled
with deltas for the two x and y values of each object. If both Tiles are
valid?() and one delta is 1 while the other is 2, they are a Knight's jump
apart.
The next section of code puts those Tiles to work:
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
The knights_trip() method does all the grunt work for this solution. You pass
it the start, finish, and forbidden Tiles. It will return a path, if one can be
found.
The method starts by building a Tile for every board square. After that, any
forbidden Tiles are removed, so they won't be considered.
Next comes the heart of the algorithm. A Hash is created with pairs of search
depth keys and value Arrays that represent all the Tiles at that depth. (Note
that an Array could be used in place of the Hash, since the keys are ordered
numerical indexes.) The until loop fills in the Hash by searching each
successive depth until running out of illegal moves or locating the finish Tile.
Each depth is built in the call to inject(), which just adds all the adjacent?()
Tiles from the previous depth to an empty Array. Tiles are always removed from
the board as they are added to the depth Hash to keep them from coming up as
adjecent?() to later Tile searches. The final if statement builds the path by
working backwards through the depth search Hash one ply at a time, looking for
adjacent?() Tiles.
It only takes a little more code to finish the solution off:
# 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
This snippet just puts the above methods to use. ARGV is translated into Tile
objects and all those Tiles, if valid?(), are fed to knights_trip(). If a path
is returned, it's printed. Otherwise, a route is not available and a message
relates this.
My thanks go out to all Knights who made the leap this week. As always, they
provided a bunch of interesting code to examine and I recommend you do so.
Tomorrow's quiz is a simple but fun little challenge that may bring back
childhood memories for some...
