From: "Glen F. Pankow" <Glen.F.Pankow@...>
Date: 2007-01-02T09:52:08+09:00
Subject: Re: [QUIZ] Word Search (#107)

#! /usr/bin/env ruby
#
#  quiz-107  --  Ruby Quiz #107.
#
#  See the Ruby Quiz #107 documentation for more information
#  (http://www.rubyquiz.com/quiz107.html).
#
#  I do the basic quiz, although with no extra credit work.
#
#  Glen Pankow      12/29/06
#
#  Licensed under the Ruby License.
#
#----------------------------------------------------------------------------
#
#  When thinking about this quiz, I didn't want to take the usual matrix-type
#  approach, but instead to do simple string matches against interesting or
#  clever transformations of the quiz text lines.  I thought this would be
#  quite easy, but soon found a way to use more interesting transformations
#  that proved a bit trickier.  Not that this turned out amenable for the quiz
#  extra credit problems, but what the hey.
#


class String

    #
    # upcase_trim
    #
    # Return a copy of the current string with a non-letter characters trimmed
    # and all lower case letters converted to upper case.
    #
    def upcase_trim
        upcase.gsub(/[^A-Z]/, '')
    end


    #
    # replicate_match(strs, replication_str)
    #
    # If any of the simple Strings in the Array <strs> is found in the current
    # string (possibly in multiple places and possibly overlapping), the String
    # <replication_str> is updated with the matching string in the corresponding
    # location.  <strs> may also be a single String object.
    #
    # For example, 'abdcbcbcb'.replicate_match(['cbc', 'ab'], '---------')
    # updates the '---------' to 'ab-cbcbc-'.
    #
    def replicate_match(strs, replication_str)
        strs = [ strs ] unless (strs.is_a?(Array))
        strs.each do |str|
            str_len = str.length
            next if (length < str_len)
            offset, last_offset = 0, length - str_len
            while (offset <= last_offset)
                if str_pos = index(str, offset)
                    replication_str[str_pos, str_len] = str
                    offset = str_pos
                end
                offset += 1
            end
        end
    end


    #
    # spacey_str = string.space_out
    #
    # Return a copy of the current string with space characters inserted
    # between its characters (plus an initial space character).
    #
    def space_out
        gsub(/(.)/, ' \1')
    end
end



class WordSearch

    #
    # word_search = WordSearch.new
    #
    # Initialize and return an empty word search puzzle object.
    #
    def initialize
        @text_lines = [ ]
    end


    #
    # word_search.add_line(line)
    #
    # Add the String <line> to the current word search puzzle object.
    #
    def add_line(line)
        @text_lines << line.upcase_trim
    end


    #
    # word_search.solve(*words)
    #
    # Solve the current word search object for the words <words>.  The solution
    # is returned, which is an Array of Strings in the same shape as the
    # original puzzle, where the solution word letters are kept intact, but the
    # non-solution word letters replaced with the character '+'.
    #
    # We tackle this problem by doing simple string matches of <words> over
    # repeated transformations of the puzzle text lines:
    #
    #    ABCD hflip  DCBA diag  D  hflip  D  undiag  DHL
    #    EFGH -----> HGFE ----> CH -----> HC ------> CGK
    #    IJKL        LKJI       BGL       LGB        BFJ
    #    (L->R)      (R->L)     AFK       KFA        AEI
    #     ^                     EJ        JE         (T->B)
    #     |                     I         I           |
    #     | undiag              (TL->BR)  (BR->TL)    | hflip
    #     |                                           v
    #    A   hflip  A   diag  AEI  hflip  IEA  vflip LHD
    #    BE <------ EB <----- BFJ <-----  JFB <----- KGC
    #    CFI        IFC       CGK         KGC        JFB
    #    DGJ        JGD       DHL         LHD        IEA
    #    HK         KH                               (B->T)
    #    L          L
    #    (TR->BL)  (BL->TR)
    #
    # Other types of transformations (such as straight transpose) would be
    # easier (by simply undoing some transformation steps), but would require
    # more steps.
    #
    def solve(*words)
        words = words.collect { |word| word.upcase_trim }

        #
        # Make the various transformations, checking for matches along the
        # way.
        #
        normalize            ;  replicate_match(words)      # match L->R
        flip_horizontal      ;  replicate_match(words)      # match R->L
        diagonalize          ;  replicate_match(words)      # match TL->BR
        flip_horizontal      ;  replicate_match(words)      # match BR->TL
        undiagonalize(true)  ;  replicate_match(words)      # match T->B
        flip_horizontal      ;  replicate_match(words)      # match B->T
        flip_vertical ; flip_horizontal
        diagonalize          ;  replicate_match(words)      # match BL->TR
        flip_horizontal      ;  replicate_match(words)      # match TR->BL
        undiagonalize(false)

        #
        # And return the solution.
        #
        @sltn_lines
    end

protected

    #
    # word_search.normalize
    #
    # Undiagonalizing is somewhat tricky, as we need to recover its original
    # (or transposed) shape.  Set the internal state of this object for
    # suitable shape information.
    #
    # Also, (un)diagonalizing will be screwed up if this shape is not a nice,
    # full rectangle.  Pad it if necessary.  And, clear out the solution array
    # (and give it the same shape).
    #
    def normalize
        @height = @text_lines.size
        @width = 0
        @sltn_lines = [ ]
        @text_lines.each do |line|
            len = line.length
            @width = len if (len > @width)
            @sltn_lines << '+' * len
        end
        (0...@text_lines.size).each do |i|
            no_pad_chars = @width - @text_lines[i].length
            1.upto(no_pad_chars) do
                @text_lines[i] << '+'
                @sltn_lines[i] << '+'
            end
        end
    end


    #
    # word_search.flip_horizontal()
    #
    # Flip all the lines of the current word search puzzle object horizontally.
    #
    # (Note:  this and all similar methods should more appropriately be named
    # in their bang (!) forms, but I don't do that for this quiz, nor do I do
    # other normal things here like returning self.)
    #
    def flip_horizontal
        (0...@text_lines.size).each do |i|
            @text_lines[i].reverse!
            @sltn_lines[i].reverse!
        end
    end


    #
    # word_search.flip_vertical()
    #
    # Flip all the lines of the current word search puzzle object vertically.
    #
    def flip_vertical
        @text_lines.reverse!
        @sltn_lines.reverse!
    end


    #
    # word_search.diagonalize()
    #
    # Convert the lines of the current word search puzzle object to a kind of
    # diagonalized form.
    #
    # Note that here I don't presize the arrays, and so use the ||= trick
    # (well, I suppose it's possible to figure out how big to make the arrays,
    # but I didn't bother doing that).
    #
    def diagonalize
        text_lines = @text_lines  ;  @text_lines = [ ]
        sltn_lines = @sltn_lines  ;  @sltn_lines = [ ]
        text_lines.each_with_index do |line, i|
            line.split('').each_with_index do |char, j|
                (@text_lines[i+j] ||= '') << char
                (@sltn_lines[i+j] ||= '') << sltn_lines[i][j]
            end
        end
    end


    #
    # word_search.undiagonalize(transposed)
    #
    # Convert the lines of the current word search puzzle object back into a
    # rectangular form.  Because we don't do true matrix-like manipulation (we
    # work with simple strings) and thus lose any original indexing (via simple
    # string appending), we need original shape information in order to do the
    # reconstruction.
    #
    # But this is perhaps fortuitous, because we can in fact reconstruct the
    # lines into a transposed-like shape (saving us several transformation
    # steps).
    #
    def undiagonalize(transposed)
        text_lines = @text_lines
        @text_lines = Array.new(transposed ? @width : @height) { String.new }
        sltn_lines = @sltn_lines
        @sltn_lines = Array.new(transposed ? @width : @height) { String.new }
        text_lines.each_with_index do |line, i|
            if (transposed)
                o = (i + 1 < @height)? 0 : i + 1 - @height
            else
                o = (i + 1 < @width)? 0 : i + 1 - @width
            end
            line.split('').each_with_index do |char, j|
                @text_lines[j+o] << char
                @sltn_lines[j+o] << sltn_lines[i][j]
            end
        end
    end


    #
    # word_search.replicate_match(words)
    #
    # Update the solution lines of the current word search puzzle object with
    # any matches of the word Strings <words>.
    #
    def replicate_match(words)
        @text_lines.each_with_index do |line, i|
            line.replicate_match(words, @sltn_lines[i])
        end
    end
end


#
# Go for it!
#
puzzle = WordSearch.new
infile = ((ARGV.size == 0) || (ARGV[0] == '-'))? $stdin : File.open(ARGV[0])
loop do
    line = infile.gets
    break if line =~ /^\s*$/
    puzzle.add_line(line)
end
words = infile.gets.strip.split(/\s+/)
print "\nAnd the solution is:\n  ",
  puzzle.solve(*words).collect { |line| line.space_out }.join("\n  "), "\n"