# [QUIZ] Word Search (#107)

Discussion in 'Ruby' started by Ruby Quiz, Dec 29, 2006.

1. ### Ruby QuizGuest

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
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
* Decide what to do with accented letters.
* Allow for wildcard letters.

Ruby Quiz, Dec 29, 2006

2. ### PhrogzGuest

Re: Word Search (#107)

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?

Phrogz, Dec 29, 2006

3. ### James Edward Gray IIGuest

Re: Word Search (#107)

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

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

James Edward Gray II

James Edward Gray II, Dec 30, 2006
4. ### Martin BoeseGuest

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

Martin Boese, Jan 1, 2007
5. ### Ben FordGuest

Re: [QUIZ] [SOLUTION] Word Search (#107)

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
def initialize(x, y)
@x = x
@y = y
end
def to_s
"(#{@x},#{@y})"
end
((@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
end
def same?
return false if length < 1
return true if length == 1
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 = []
tail = arr.slice(1, arr.length-1)
mixarrays(tail).each do |y|
temp << [x] + y
end
end
return temp
end

def connectedword(word)
return false if word.length < 1
return true if word.length == 1
end

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

answer = puzzle.map {|line| line.gsub(/./, '+')}
points.flatten.each do |p|
end
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?}]}

puts

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
> 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, Jan 1, 2007
6. ### Bob ShowalterGuest

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

# 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)
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
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

Bob Showalter, Jan 2, 2007
7. ### William JamesGuest

Re: Word Search (#107)

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(' ') }

William James, Jan 3, 2007