From: "Eric I." <rubytraining@...>
Date: 2007-12-10T04:50:38+09:00
Subject: Re: Word Loop (#149) [SOLUTION]

Here is my solution that tries to make all possible arrangements and
displays solutions with the maximum number of overlaps.

Eric

----

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