From: Ben Ford <fordbc@...>
Date: 2007-01-02T08:15:08+09:00
Subject: 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
  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 << [x] + 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.