···
----
Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com
====
# Solution to Ruby Quiz #149 provided by LearnRuby.com
#
# The code to this solution can also be found at:
# http://learnruby.com/examples/ruby-quiz-149.shtml
#
# This solution tries to find all solutions and then selects those
# with the maximum number of overlaps. Good words to try are
# "absolvable" and "chincherinchee". It is implemented with a
# recursive search.
# The Grid class is used to hold a grid where each cell contains a
# character or, if it's empty, nil. Furthermore, the grid keeps track
# of how many overlaps there are in the word that spins within it,
# since that's the measure of how good the arrangement is.
class Grid
attr_reader :overlaps
def initialize
@grid = Array.new
@overlaps = 0
end
def [](position)
sub_array(position[0])[position[1]]
end
def []=(position, value)
sub_array(position[0])[position[1]] = value
end
def inc_overlaps
@overlaps += 1
end
def dec_overlaps
@overlaps -= 1
end
def to_s
@grid.map do |row|
if row
row.map { |c| c || ' ' }.join('')
else
''
end
end.join("\n")
end
def dup
other = Grid.new
@grid.each_with_index do |row, i|
other.grid[i] = row.dup unless row.nil?
end
other.overlaps = @overlaps
other
end
# Trim grid so it's as small as possible. Assumes that filled areas
# are contiguous, so that an empty row would not sit between
# non-empty rows.
def trim!
@grid.delete_if { |row| row.nil? || row.all? { |c| c.nil? } }
trim_columns = empty_columns
@grid.each_index do |i|
@grid[i] = @grid[i][trim_columns..-1]
@grid[i].pop while @grid[i].last.nil?
end
self
end
protected
attr_reader :grid
attr_writer :overlaps
# Utility method that returns the sub-array of @grid at index.
# Since the sub-array may have not yet been created, will create it
# if necessary.
def sub_array(index)
sub_array = @grid[index]
sub_array = @grid[index] = Array.new if sub_array.nil?
sub_array
end
# returns the number of entries at the start of each sub-array that
# are empty, so the grid can be "left-trimmed".
def empty_columns
index = 0
index += 1 while @grid.all? { |row| row.nil? || row[index].nil? }
index
end
end
# This module contains some convenience methods to move a position in
# a direction, and to figure out a new direction when a right turn is
# made.
module Direction
RightTurns = {
[0, 1] => [1, 0],
[1, 0] => [0, -1],
[0, -1] => [-1, 0],
[-1, 0] => [0, 1],
}
# returns the rightwards direction
def self.rightwards
[0, 1]
end
def self.turn_right(direction)
RightTurns[direction]
end
def self.move(position, direction)
[position[0] + direction[0], position[1] + direction[1]]
end
end
# Recursively tries placing characters on grid until the full word is
# placed or a conflict is found. During the recursion we try two
# options -- continuing in same direction or making a right turn.
# Results are accumulated in result parameter, which is an array of
# Grids.
def find_loops(word, letter_index, grid, position, direction, result)
new_position = Direction.move(position, direction)
character_placed = false
# one of three conditions -- cell is empty, cell contains a letter
# that matches the current word letter, cell contains a letter that
# doesn't match current word letter
if grid[new_position].nil?
# empty cell -- put character in
grid[new_position] = word[letter_index, 1]
character_placed = true
elsif grid[new_position] == word[letter_index, 1]
# cell with matching character, increment overlap count
grid.inc_overlaps
else
# cell with non-matching character, quit searching this branch
return
end
# have we placed the entire word; add to results, otherwise recurse
# continuting in same direction and after making a right turn
if letter_index == word.size - 1
result << grid.dup
else
# try going in the same direction and also try making a right turn
find_loops(word, letter_index + 1, grid,
new_position, direction, result)
find_loops(word, letter_index + 1, grid,
new_position, Direction.turn_right(direction), result)
end
# restore the grid or overlap count depending on earlier condition
if character_placed
grid[new_position] = nil
else
grid.dec_overlaps
end
end
# This is the entry point to the loop-finding process. It places
# first letter in a new grid and calls the recursive find_loops
# methods.
def solve(word)
size = word.length
grid = Grid.new
# starting position allows room for word to go leftwards or upwards
# without bumping into left or top edges; assumes initially heading
# rightwards and only right turns can be made
position = [size - 5, size - 4]
direction = Direction.rightwards
# put first character at starting position
grid[position] = word[0, 1]
# generate solutions in results parameter
results = []
find_loops(word, 1, grid, position, direction, results)
results
end
# find the best results and display them
def display_best_results(results)
# the best results have most overlaps, so sort so most overlaps
# appear at front of array, and then use the first element's
# overlaps as best score
results = results.sort_by { |r| -r.overlaps }
best_score = results.first.overlaps
puts "Number of overlaps: #{best_score}"
puts "=" * 40
results.select { |r| r.overlaps == best_score }.each do |result|
puts result.trim!
puts "=" * 40
end
end
if $0 == __FILE__
if ARGV.size == 1
display_best_results(solve(ARGV[0].downcase))
else
$stderr.puts "Usage: #{$0} _word_"
exit 1
end
end
