Re: [QUIZ] Word Search (#107)

Here is my solution. It supports ? and * as wildcard letters.

-Chunyun

Sample input:

U E W R T R B H C D
C X U Z U W R Y E R
R O C K S B A U C U
Y F K F M T Y S G E
Y S O O U N M E I M
T C G P R T I D A N
Y Z G H Q G W T U R
H B M N D X Z B U T
N T U L A T N X C E
Y B U R P Z Y X M S

Ru?y Year ro*s DAN matZ

Output:

+ + + R + + + + + +
+ + U + U + + + + +
R O C K S B + + + +
Y + + + + + Y + + +
+ + + + + + + E + M
+ + + + + + + D A N
Y + + + + + + T + R
+ B + + + + Z + U +
+ + U + + + + X + +
Y B U R + + Y + + +

Code:
#== Synopsis
#This is the solution to Ruby Quiz #107 described on
http://www.rubyquiz.com/quiz107.html.
#
#== Usage
#   ruby word_search.rb
#   OR
#   ruby word_search.rb input_file
#
#== Author
#   Chunyun Zhao([e-mail])
#
class WordSearch
  attr_reader :found_coords

  def initialize(box)
    @box = box
    @height = @box.size
    @width = @box[0].size
  end

  def search_words(words)
    @found_coords=[]
    regexize_words(words)
    each_line do |line_coords|
      line_str = get_line_str(line_coords)
      words.each do |word|
        if line_str=~/#{word}/i
          offset = $~.offset(0)
          @found_coords |= line_coords[offset[0]...offset[1]]
        end
      end
    end
  end

  def display_words
    for x in 0...@height
      for y in 0...@width
        @found_coords.include?([x,y])? print(@box[x][y]):print('+')
        print ' '
      end
      puts
    end
  end

  private
  #Generates all possible lines(represented as arrays of coordinates) from
@box , and
  #calls the block with the line coordinates.
  def each_line
    vertical_line_proc = lambda {|x, y| [x+1, y]}
    horizonal_line_proc = lambda {|x, y| [x, y+1]}
    backward_diagonal_line_proc = lambda {|x, y| [x+1, y+1]}
    forward_diagonal_line_proc = lambda {|x, y| [x+1, y-1]}

    lines = []
    #Genernates the lines starting with the top horizonal line
    for y in 0...@width
      lines << get_line_coords(0, y, &vertical_line_proc)
      lines << get_line_coords(0, y, &backward_diagonal_line_proc)
      lines << get_line_coords(0, y, &forward_diagonal_line_proc)
    end
    #Genernates the lines starting with the leftmost and rightmost vertical
lines
    for x in 0...@height
      lines << get_line_coords(x, 0, &horizonal_line_proc)
      lines << get_line_coords(x, 0, &backward_diagonal_line_proc)
      lines << get_line_coords(x, @width-1, &forward_diagonal_line_proc)
    end
    lines.each{|line_coords|yield line_coords; yield line_coords.reverse}
  end

  #Generates the line starting with coordinate [x,y]. It calls the block to
find the
  #next position in the line. It can be used to generate snake lines if
necessary.
  def get_line_coords(x, y)
     line = [[x,y]]
     loop do
       next_x, next_y = yield x, y
       @box[next_x] && @box[next_x][next_y] ? line << [next_x, next_y] :
break
       x, y = next_x, next_y
     end
     line
  end

  #Gets the string represented by an array of coordinates.
  def get_line_str(coords)
    line_str = ''
    coords.each{|x,y| line_str << @box[x][y]}
    line_str
  end

  #Replaces ? and * with \w? and \w* in each word so that it could be used
  #as the regex to support wildcard letter matching.
  def regexize_words(words)
    words.each {|word|word.gsub!(/(\?|\*)/, '\w\1')}
  end
end

box = []
width = nil
while line=gets
  break if line.strip.empty?
  row = line.split
  raise "The width of all the rows must be equal!" if !width.nil? and width
!= row.size
  width = row.size
  box << row
end
raise "You need at least enter one row of letters!" if box.empty?
words = gets.split
raise "You need at least enter one word!" if words.empty?

ws = WordSearch.new(box)
ws.search_words(words)
ws.display_words

__END__

On 12/29/06, Ruby Quiz <[e-mail]> 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!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps
> everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz
> message,
> if you can.
>
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Daniel Finnie
>
> Today's quiz would've been most useful in elementary school, where over
> half of
> the homework assignments were word search puzzles. The concept of these
> puzzles
> is simple enough that an elementary school student could understand
> it:  given a
> box of letters, find a line containing the letters of a specified word in
> order.
>
> For example, find the words ruby, dan, rocks, and matz in the following
> text:
>
>         U E W R T R B H C D
>         C X G Z U W R Y E R
>         R O C K S B A U C U
>         S F K F M T Y S G E
>         Y S O O U N M Z I M
>         T C G P R T I D A N
>         H Z G H Q G W T U V
>         H Q M N D X Z B S T
>         N T C L A T N B C E
>         Y B U R P Z U X M S
>
> The correct answer in the correct output format:
>
>         + + + R + + + + + +
>         + + + + U + + + + +
>         R O C K S B + + + +
>         + + + + + + Y + + +
>         + + + + + + + + + M
>         + + + + + + + D A N
>         + + + + + + + T + +
>         + + + + + + Z + + +
>         + + + + + + + + + +
>         + + + + + + + + + +
>
> Notice that the words can go backwards and diagonally, and can intersect
> one
> another. Searching is case insensitive.
>
> The word search solver should accept input entered by the user after
> running the
> program, i.e., not exclusively through STDIN or a file, by entering the
> puzzle
> line by line, pressing return after each line. A blank line indicates the
> end of
> the puzzle and the start of the comma separated words to find. The
> following
> example shows how a user would enter the above puzzle, with descriptive
> text
> from the program removed.
>
>         $ ./wordsearch.rb
>         UEWRTRBHCD
>         CXGZUWRYER
>         ROCKSBAUCU
>         SFKFMTYSGE
>         YSOOUNMZIM
>         TCGPRTIDAN
>         HZGHQGWTUV
>         HQMNDXZBST
>         NTCLATNBCE
>         YBURPZUXMS
>
>         Ruby, rocks, DAN, matZ
>
> Now, by itself, this quiz is fairly simple, so I offer an additional
> challenge.
> Write a beautiful, extensible, and easily-modifiable program without
> looking at
> the extra credit before starting. When you're done, try implementing extra
> credit options using less than 5 or 6 (reasonable) lines of code.
>
>         * An output format superior to the one given. The output format
> given
>           should remain the default unless both formats don't differ on a
>           textual basis. That should sound cryptic until pondered, I can't
>           give too much away!
>         * Allow for "snaking" of answers, in other words, the letters
>           composing a word don't have to be in a straight line.
>         * An option to give a hint, i.e., "The word ruby traverses the
> bottom
>           left and bottom right quadrants."
>         * Decide what to do with accented letters.
>         * Allow for wildcard letters.
>
>