[QUIZ] Word Search (#107)

[James_Edward_Gray_II]

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.

[Gavin_Kistner2 (Gavin Kistner)]

Ruby Quiz wrote:

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 + + +
  + + + + + + + + + +
  + + + + + + + + + +

Shouldn't that be:

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

?

What should happen if the same word occurs more than once in the puzzle?

[Mariano_Kamp]

Hi,

   nice quiz ... Not too time intensive

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.

I attached my solution. See test_ruby_quiz. Please be gentle

  * 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!

I like the current format.

  * Allow for "snaking" of answers, in other words, the letters
    composing a word don't have to be in a straight line.

It allows for snaking, see "test_snake", and also for matches that leave the field on one side and comes back on another, e.g. YRUB. See test_overflow.

  * An option to give a hint, i.e., "The word ruby traverses the bottom
    left and bottom right quadrants."

nah.

  * Decide what to do with accented letters.

Didn't implement that either.

  * Allow for wildcard letters.

Didn't go all the way like using regexp, but "*" is allowed as a wild card character.

Funny enough, my Sudoku solution took less lines than this one ...

Cheers,
Mariano



word_search_test.rb (2.74 KB)

word_search.rb (3.95 KB)

···

On Dec 29, 2006, at 5:06 PM, Ruby Quiz wrote:

[Martin_Boese]

Here is my solution for the word search quiz. It's faily simple and stupid and
doesn't do any of the extras, except it accepts a '?' wildcard.

But then it also finds words that break the board boundaries and continue on
the other side.. call it bug of feature , so this:

$ ruby wordsearch.rb
UEWRTRBHCB
CXGZUWRYUR
ROCKSBARCU
SFKFMTYSGE
YSOOUNMZIM
TCGPRTIDAN
HZGHQGWTUV
HQMNDXZBST
NTCLATNBCE
YBURPZUXMS

Ruby, rocks, DAN, matZ

... gives you:

+++R+++++B
++++U+++U+
ROCKSB+R++
++++++Y+++
+++++++++M
+++++++DAN
+++++++T++
++++++Z+++

···

++++++++++
YBUR++++++

Happy new year,
Martin

# wordquiz.rb

# create a each_chr method
class String
def each_chr
  self.each_byte { |b| yield b.chr }
end
end

class Puz
DIRECTIONS = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]]

# puzzle - array of strings (one for each line)
# word_list - array for words to look for
def initialize(puzzle, word_list)
  @puzzle = puzzle
  @word_list = word_list

  # get dimention of the board
  @x,@y = @puzzle[0].length-1, @puzzle.length-1

  # create an empty result board
  @result = Array.new(@y+1)
  0.upto(@y) { |i| @result[i] = String.new("+"*(@x+1)) }
end

protected

# return cursor to the next position in direction
def gonext(x,y,d)
  x+=d[0]; y+=d[1]
  x = 0 if x > @x; x = @x if x < 0
  y = 0 if y > @y; y = @y if y < 0
  [x,y]
end

# writes a word into the @result container
def write_result(word, x,y, direction)
   word.each_chr do |c|
    @result[y] = c
    x,y = gonext(x,y, direction)
   end
end

# yields all possible cursor positions of the board
def each_position
   0.upto(@y) { |y| 0.upto(@x) { |x| yield x,y }}
end

def char_match(char, x, y)
   return true if char == '?' # allow wildcard '?'
   @puzzle[y].chr == char
end

# finds a given word on a position in a specific direction
def find_in_direction(word, x, y, d)
   word.each_chr do |c|
    return false if !self.char_match(c, x, y)
    x,y = gonext(x,y,d)
   end
  true
end

# finds a word on a position
def find(word, x, y)
   DIRECTIONS.each do |d|
       write_result(word, x,y,d) if find_in_direction(word, x,y, d)
   end
end

public

def resolve
   @word_list.each do |word|
     each_position { |x,y| find(word, x, y) }
   end
   return (@result.join("\n"))
end
end

board =
while true do
inp = STDIN.gets.strip
if inp.length > 0 then board << inp else break end
end

puts Puz.new(board, STDIN.gets.split(',').collect{ |w|
w.strip.upcase}).resolve

On Friday 29 December 2006 16:06, Ruby Quiz 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.

[Ben_Ford]

Here is my solution. It is my first Ruby program. I was able to get two
of the extra credit with virtually no work. I had snaking already
because I generated the snaked answers before eliminating the ones that
weren't a straight line. I had an alternative output format because I
was using it to debug my code as I went along before I wrote the code
to generate the answer grid. Using the sample input set, here is my
output:

+++R+R++++
++++U+++++
ROCKSB++++
++K+++Y+++
+S+++++++M
+++++++DAN
+++++++T++
+++ND+Z+++
++++A+++++
YBUR++++++

RUBY
(3,0)(4,1)(5,2)(6,3)
(5,0)(4,1)(5,2)(6,3)
(3,9)(2,9)(1,9)(0,9)
ROCKS
(0,2)(1,2)(2,2)(3,2)(4,2)
(0,2)(1,2)(2,2)(2,3)(1,4)
DAN
(7,5)(8,5)(9,5)
(4,7)(4,8)(3,7)
MATZ
(9,4)(8,5)(7,6)(6,7)

The coordinates in the output set are 0-based x,y originating from the
upper-left corner.

-Ben

require "enumerator"

class Point
  attr_reader(:x, :y)
  def initialize(x, y)
    @x = x
    @y = y
  end
  def to_s
    "(#{@x},#{@y})"
  end
  def adj?(p)
    ((@x - p.x).abs <= 1) & ((@y - p.y).abs <= 1) & !(self == p)
  end
  def -(p)
    Point.new(@x - p.x, @y - p.y)
  end
  def ==(p)
    (@x == p.x) & (@y == p.y)
  end
end

class Array
  def diff
    return to_enum(:each_cons, 2).map{|a,b| a-b}
  end
  def same?
    return false if length < 1
    return true if length == 1
    return to_enum(:each_cons, 2).all? {|a,b| a==b}
  end
end

def findletter(puzzle, c)
  locations =
  puzzle.each_with_index do |line, y|
    line.split(//).each_with_index do |letter, x|
      locations << Point.new(x, y) if letter == c
    end
  end
  return locations
end

def getletters(puzzle, term)
  term.split(//).map{|c| findletter(puzzle, c)}
end

def mixarrays(arr)
  return if (arr.empty?)
  return arr.first.zip if (arr.length == 1)

  temp =
  head = arr.first
  tail = arr.slice(1, arr.length-1)
  head.each do |x|
    mixarrays(tail).each do |y|
      temp << + y
    end
  end
  return temp
end

def connectedword(word)
  return false if word.length < 1
  return true if word.length == 1
  return word.to_enum(:each_cons, 2).all? {|a,b| a.adj?(b)}
end

def showpoints(term, points)
  puts term
  points.each {|x| print x, "\n" }
end

def answergrid(puzzle, points)
  answer = puzzle.map {|line| line.gsub(/./, '+')}
  points.flatten.each do |p|
    answer[p.y][p.x] = puzzle[p.y][p.x] if p.kind_of?(Point)
  end
  return answer
end

puzzle =
while (line = gets.chomp) != ''
  puzzle << line
end
terms = gets.chomp.upcase.split(/\s*\,\s*/)

terms_words = terms.map{|term|
  [term, mixarrays(getletters(puzzle, term))]}

terms_connectedwords = terms_words.map{|term, words|
  [term, words.select {|word| connectedword(word)}]}

terms_samediffconnectedwords = terms_connectedwords.map{|term, words|
  [term, words.select {|word| word.diff.same?}]}

answerkey = terms_connectedwords

puts
puts answergrid(puzzle, answerkey)

puts
answerkey.each {|term, words| showpoints(term, words) }

Ruby Quiz 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.

[Glen_F_Pankow]

#! /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"

[Bob_Showalter1 (Bob Showalter)]

Here's my submission. No extra credits.

# RubyQuiz Word Search (107)
# Bob Showalter

class WordSearch

  class Board < Array

    def to_s
      collect {|s| s.split(//).join(' ')}.join("\n")
    end

  end

  attr_reader :board, :solution

  # creates a new, empty solver
  def initialize
    @board = Board.new
    @solution = Board.new
  end

  # resets the solution
  def reset
    @solution.clear
    @board.each {|row| @solution << row.gsub(/./, '+')}
  end

  # checks that the board contains only letters and that it has a uniform
  # rectangular shape
  def validate
    @board.size > 0 or raise "Board has no rows"
    @board.grep(/[^A-Z]/).empty? or raise "Board contains non-letters"
    w = @board.collect {|row| row.size}.uniq
    w.size == 1 or raise "Board rows are not all the same length"
    w.first > 0 or raise "Board has no columns"
  end

  # parses the board by reading lines from io until a blank line (or EOF)
  # is read.
  def parse(io = ARGV)
    @board.clear
    while line = io.gets
      line = line.strip.upcase
      break if line == ''
      @board << line
    end
    validate
    reset
  end

  # search for word. returns number of times found. solution is updated with
  # all occurences.
  def search(word)
    found = 0
    0.upto(board.size-1) do |y|
      0.upto(board[y].size-1) do |x|
        [-1, 0, 1].each do |dy|
          [-1, 0, 1].each do |dx|
            next if dx == 0 and dy == 0
            found += 1 if search_for(word.strip.upcase, x, y, dx, dy)
          end
        end
      end
    end
    found
  end

  # search for word in board starting at position (x,y) and moving in direction
  # (dx,dy). returns true if found, false if not found.
  def search_for(word, x, y, dx, dy)
    return false if x < 0 or x >= board.first.size or y < 0 or y >= board.size
    return false if board[y][x] != word[0]
    prev = solution[y][x]
    solution[y][x] = board[y][x]
    return true if word.length <= 1
    found = search_for(word[1,word.length-1], x + dx, y + dy, dx, dy)
    solution[y][x] = prev unless found
    found
  end

  # creates a new puzzle by parsing the board from io. see WordSearch#parse
  def self.parse(io = ARGF)
    obj = new
    obj.parse(io)
    obj
  end

  def to_s
    solution.to_s
  end

end

# parse the board first
p = WordSearch.parse

# parse the words until a blank line is read
words = []
while line = ARGF.gets
  line = line.strip.upcase
  break if line == ''
  words += line.gsub(',', ' ').split
end

# submit each word and show how many times it was found
for word in words.sort.uniq
  n = p.search(word)
  puts word + ' was ' + (n == 0 ? 'not found' : n == 1 ? 'found once'
: "found #{n} times")
end

# show the solution
puts p

[Chunyun_Zhao]

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(chunyun.zhao@gmail.com)
#
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[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[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 <james@grayproductions.net> 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.

[W_James]

Ruby Quiz wrote:

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 + + +
  + + + + + + + + + +
  + + + + + + + + + +

If you don't want snaking, put "--straight" on the command line.

def write ary
  ary.each{|c,row,col| $out[row][col] = c }
end

def outside y, x
  y<0 or y>=Board.size or x<0 or x>=Board.first.size
end

def snake letters, row, col, directions, placed
  return if letters[0] != Board[row][col]
  placed << [letters[0],row,col]
  if letters.size == 1
    write placed
    return
  end
  directions.each{|dy,dx|
    y = row + dy ; x = col + dx
    next if outside( y, x )
    snake letters[1..-1], y, x, directions, placed.dup
  }
end

straight = ARGV.delete '--straight'

puts "Enter grid line by line, followed by blank line."
Board =
while (line = gets.strip.upcase) != "" do
  Board << line
end

puts "Enter words separated by commas."
words = gets.strip.upcase.split(/\s*,\s*/)

$out = Board.map{|s| "+" * s.size}

all_directions = (-1..1).inject(){|a,m| (-1..1).each{|n|
  a<<[m,n]}; a}
all_directions.delete [0,0]

Board.each_index{|row|
  Board[0].size.times{|col|
    words.each{|word|
      if straight
        all_directions.each{|direction|
          snake word, row, col, [direction],
        }
      else
        snake word, row, col, all_directions,
      end
    }
  }
}

puts "", $out.map{|s| s.split('').join(' ') }

[James_Edward_Gray_II]

Good catch. I agree that the second match should be shown.

James Edward Gray II

···

On Dec 29, 2006, at 11:45 AM, Phrogz wrote:

Ruby Quiz wrote:

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 + + +
  + + + + + + + + + +

Shouldn't that be:

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

?

[Mariano_Kamp]

Oh, and btw. wrt the "overflow" mechanism the actual quiz solution looks like this:

+++R++++++

···

++++++++++
ROC+++++++
++K+++++++
+S+++++++M
+++++++DAN
+++++++T++
++++++Z+++
++++++++++
YBU+++++++

Note, that I don't try to find multiple solutions.

Cheers,
Mariano
On Jan 1, 2007, at 4:46 PM, Mariano Kamp wrote:

Hi,

  nice quiz ... Not too time intensive

On Dec 29, 2006, at 5:06 PM, Ruby Quiz wrote:

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.

I attached my solution. See test_ruby_quiz. Please be gentle

  * 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!

I like the current format.

  * Allow for "snaking" of answers, in other words, the letters
    composing a word don't have to be in a straight line.

It allows for snaking, see "test_snake", and also for matches that leave the field on one side and comes back on another, e.g. YRUB. See test_overflow.

  * An option to give a hint, i.e., "The word ruby traverses the bottom
    left and bottom right quadrants."

nah.

  * Decide what to do with accented letters.

Didn't implement that either.

  * Allow for wildcard letters.

Didn't go all the way like using regexp, but "*" is allowed as a wild card character.

Funny enough, my Sudoku solution took less lines than this one ...

Cheers,
Mariano

<word_search_test.rb>
<word_search.rb>