From: Martin Boese <boesemar@...>
Date: 2007-01-02T03:19:44+09:00
Subject: [QUIZ] [SOLUTION] Word Search (#107)

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][x] = 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][x].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.