--Apple-Mail-3-380631163 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8; delsp=yes; format=flowed 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 =20 > over half of > the homework assignments were word search puzzles. The concept of =20 > these puzzles > is simple enough that an elementary school student could understand =20= > it: given a > box of letters, find a line containing the letters of a specified =20 > 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 =20 leave the field on one side and comes back on another, e.g. YRUB. See =20= 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 =20 wild card character. Funny enough, my Sudoku solution took less lines than this one ... Cheers, Mariano =EF=BF=BC=EF=BF=BC= --Apple-Mail-3-380631163 Content-Type: multipart/mixed; boundary=Apple-Mail-4-380631163 --Apple-Mail-4-380631163 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=ISO-8859-1 <HTML><BODY style=3D"word-wrap: break-word; -khtml-nbsp-mode: space; = -khtml-line-break: after-white-space; ">Hi,<DIV><BR = class=3D"khtml-block-placeholder"></DIV><DIV>=A0 nice quiz ... Not too = time intensive ;-)</DIV><DIV><BR><DIV><DIV>On Dec 29, 2006, at 5:06 PM, = Ruby Quiz wrote:</DIV><BLOCKQUOTE type=3D"cite"><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Today's = quiz would've been most useful in elementary school, where over half = of</DIV><DIV style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: = 0px; margin-left: 0px; ">the homework assignments were word search = puzzles. The concept of these puzzles</DIV><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">is = simple enough that an elementary school student could understand = it:<SPAN class=3D"Apple-converted-space">=A0 </SPAN>given a</DIV><DIV = style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; = margin-left: 0px; ">box of letters, find a line containing the letters = of a specified word in order.</DIV></BLOCKQUOTE><DIV><BR = class=3D"khtml-block-placeholder"></DIV><DIV>I attached my solution. See = test_ruby_quiz.=A0Please be gentle ;-)</DIV><BR><BLOCKQUOTE = type=3D"cite"><DIV style=3D"margin-top: 0px; margin-right: 0px; = margin-bottom: 0px; margin-left: 0px; "><SPAN class=3D"Apple-tab-span" = style=3D"white-space:pre"> </SPAN>* An output format superior to = the one given. The output format given</DIV><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN = class=3D"Apple-tab-span" style=3D"white-space:pre"> </SPAN><SPAN = class=3D"Apple-converted-space">=A0 </SPAN>should remain the default = unless both formats don't differ on a</DIV><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN = class=3D"Apple-tab-span" style=3D"white-space:pre"> </SPAN><SPAN = class=3D"Apple-converted-space">=A0 </SPAN>textual basis. That should = sound cryptic until pondered, I can't</DIV><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN = class=3D"Apple-tab-span" style=3D"white-space:pre"> </SPAN><SPAN = class=3D"Apple-converted-space">=A0 </SPAN>give too much = away!</DIV></BLOCKQUOTE>I like the current = format.</DIV><DIV><BR><BLOCKQUOTE type=3D"cite"><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN = class=3D"Apple-tab-span" style=3D"white-space:pre"> </SPAN>* Allow = for "snaking" of answers, in other words, the letters</DIV><DIV = style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; = margin-left: 0px; "><SPAN class=3D"Apple-tab-span" = style=3D"white-space:pre"> </SPAN><SPAN = class=3D"Apple-converted-space">=A0 </SPAN>composing a word don't have = to be in a straight line.</DIV></BLOCKQUOTE><DIV>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.</DIV><BR><BLOCKQUOTE type=3D"cite"><DIV = style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; = margin-left: 0px; "><SPAN class=3D"Apple-tab-span" = style=3D"white-space:pre"> </SPAN>* An option to give a hint, i.e., = "The word ruby traverses the bottom</DIV><DIV style=3D"margin-top: 0px; = margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN = class=3D"Apple-tab-span" style=3D"white-space:pre"> </SPAN><SPAN = class=3D"Apple-converted-space">=A0 </SPAN>left and bottom right = quadrants."</DIV></BLOCKQUOTE>nah.</DIV><DIV><BR><BLOCKQUOTE = type=3D"cite"><DIV style=3D"margin-top: 0px; margin-right: 0px; = margin-bottom: 0px; margin-left: 0px; "><SPAN class=3D"Apple-tab-span" = style=3D"white-space:pre"> </SPAN>* Decide what to do with accented = letters.</DIV></BLOCKQUOTE>Didn't implement that = either.</DIV><DIV><BR><BLOCKQUOTE type=3D"cite"><DIV style=3D"margin-top: = 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><SPAN = class=3D"Apple-tab-span" style=3D"white-space:pre; color: rgb(0, 0, = 221); "> </SPAN>* Allow for wildcard letters.</DIV> = </BLOCKQUOTE></DIV>Didn't go all the way like using regexp, but=A0 "*" = is allowed as a wild card character.<BR></DIV><DIV><BR = class=3D"khtml-block-placeholder"></DIV><DIV>Funny enough, my Sudoku = solution took less lines than this one ...</DIV><DIV><BR = class=3D"khtml-block-placeholder"></DIV><DIV>Cheers,</DIV><DIV>Mariano</DI= V><DIV><BR = class=3D"khtml-block-placeholder"></DIV><DIV><SPAN></SPAN></DIV></BODY></H= TML>= --Apple-Mail-4-380631163 Content-Transfer-Encoding: 7bit Content-Type: text/x-ruby-script; x-unix-mode=0644; name=word_search_test.rb Content-Disposition: attachment; filename=word_search_test.rb require 'test/unit' require 'word_search' class WordSearchTest < Test::Unit::TestCase def test_parse input = <<-INPUT XXXRXXX XXXUXXX XXXBXXX XXXYXXX RUBY INPUT word_search = WordSearch.new input assert_equal 1, word_search.words.size assert_equal 4, word_search.rows.size assert_equal 7, word_search.row_length end def test_multiple_words_and_case_insensitivity_of_words word_search = WordSearch.new <<-INPUT XXXXX one, TWO, ThrEe INPUT assert_equal ["one", "two", "three"], word_search.words end def test_unused_char input = <<-INPUT RUBY RUBY RUBY a INPUT begin WordSearch.new(input).solve fail rescue RuntimeError => e assert_equal "Word a not found", e.message end end def test_ruby_quiz input = <<-INPUT UEWRTRBHCD CXGZUWRYER ROCKSBAUCU SFKFMTYSGE YSOOUNMZIM TCGPRTIDAN HZGHQGWTUV HQMNDXZBST NTCLATNBCE YBURPZUXMS Ruby, rocks, DAN, matZ INPUT # If any word isn't found an exception will be raised WordSearch.new(input).solve end def test_snake input = <<-INPUT SxExxx xNxKxx xxAxxx Snake INPUT output = <<-OUTPUT S+E+++ +N+K++ ++A+++ OUTPUT assert_equal output.gsub(' ',''), WordSearch.new(input).solve end def test_overflow input = [] input << "BYRU\n" input << "YRUB\n" input << <<-INPUT U B Y R INPUT input << <<-INPUT xxxx xxRX xxxU Bxxx xYxx INPUT input << <<-INPUT Bxxxxx xYxxxx xxxxRx xxxxxU INPUT begin input.each do |tc_input| @tc_input = tc_input assert WordSearch.new(tc_input + "\nruby\n").solve end rescue puts "\n#{@tc_input} failed." fail end end def test_find input = <<-INPUT xxxRxxx xxxUxxx xxxBxxx xxxYxxx RUBY INPUT output = <<-OUTPUT +++R+++ +++U+++ +++B+++ +++Y+++ OUTPUT word_search = WordSearch.new input assert_equal output.gsub(/ /, ''), word_search.solve end def test_find_with_wildcard input = <<-INPUT xxxRxxx xxxUxxx xxxBxxx xxxYxxx R*BY INPUT assert WordSearch.new(input) end def test_neighbours word_search = WordSearch.new <<-INPUT ABCD EFGH IJKL MNOP foo, bar INPUT assert_equal "abc"+"eg"+"ijk", neighbour_values(word_search.field(1,1)) assert_equal ("bd"+"efh"+"mnp").sort.join, neighbour_values(word_search.field(0,0)) end private def neighbour_values(field) field.neighbours.collect{|f|f.value}.sort.join end end --Apple-Mail-4-380631163 Content-Transfer-Encoding: 7bit Content-Type: text/html; charset=US-ASCII <HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><DIV><SPAN></SPAN><SPAN></SPAN></DIV></BODY></HTML> --Apple-Mail-4-380631163 Content-Transfer-Encoding: 7bit Content-Type: text/x-ruby-script; x-unix-mode=0644; name=word_search.rb Content-Disposition: attachment; filename=word_search.rb class WordSearch attr_reader :rows, :row_length, :words def initialize(input) input_lines = input.to_a raise "At least three lines must be entered" if input_lines.size < 3 @words = input_lines.pop.downcase.gsub(/\s/, '').split(',') raise "Words need to be specified" if @words.empty? input_lines.pop # remove empty line raise "No rows provided" if input_lines.empty? @chars = {} # starting points row_index = -1 @rows = Array.new(input_lines.size) do row_index += 1 col_index = -1 input_lines.shift.strip.downcase.scan(/./).map do |char| col_index += 1 field = Field.new char, row_index, col_index, self (@chars[char] ||= []) << field field end end @row_length= rows.first.size raise "All rows need to have the same number of columns" if @rows.any? {|r| r.size != @row_length} end def field(row_idx, col_idx) @rows[row_idx][col_idx] end def solve fields = @words.collect do |word| result = find_word(word) || find_word(word.reverse) raise "Word #{word} not found" unless result result end.flatten.uniq all_fields = Array.new(rows.size) {"+"*row_length} fields.each do |field| all_fields[field.row_idx][field.col_idx] = field.value end (all_fields.join("\n")+"\n").upcase end private def find_word(word, try_field = nil, visited_fields = []) visited_fields = visited_fields.dup # Iter over the hash associated with characters to find starting points if try_field.nil? first_char = word[0..0] starting_points = @chars[first_char] return false unless starting_points starting_points.each do |field| result = find_word(word, field) return result if result end return false else # find_word with a starting point called visited_fields << try_field found_word = visited_fields.collect{|f|f.value}.join # check partial match wrt wildcards search_word = word[0..found_word.length-1] search_word.scan(/./).each_with_index do |char, index| if char == '*' found_char = found_word[index..index] search_word[index..index] = found_char end end if found_word == search_word && found_word.length == word.length # match? return visited_fields end if visited_fields.length < word.length # Stop deepening? # Deepening # Recursively try neighbouring fields next_char = word[visited_fields.length..visited_fields.length] try_field.neighbours.select do |neighbour| (next_char == '*' || neighbour.value == next_char) && (!visited_fields.include? neighbour) end.each do |neighbour| # Broadening result = find_word(word, neighbour, visited_fields) return result if result end end return false end end end class Field attr_reader :value, :row_idx, :col_idx, :word_search NEIGHBOUR_COORDINATES = [-1, -1], [-1, 0],[0, -1], [+1, +1], [+1, 0],[0, +1], [+1, -1], [-1, +1] def initialize(value, row_idx, col_idx, word_search) @value, @row_idx, @col_idx, @word_search = value, row_idx, col_idx, word_search end def neighbours @neighbours ||= NEIGHBOUR_COORDINATES.map do |row_mod,col_mod| # Using mod to handle overflowing and negative coordinates row = (@row_idx + row_mod) % @word_search.rows.size col = (@col_idx + col_mod) % @word_search.row_length @word_search.field(row, col) end end end if __FILE__ == $0 puts "Enter text (empty line when finished):" input = [] loop do input << line = readline break if line.gsub(/\s/, '').empty? end puts "Enter words now (comma separated): " input << readline puts "Here is the result:" puts WordSearch.new(input).solve end --Apple-Mail-4-380631163 Content-Transfer-Encoding: 7bit Content-Type: text/html; charset=US-ASCII <HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><DIV><SPAN></SPAN></DIV></BODY></HTML> --Apple-Mail-4-380631163-- --Apple-Mail-3-380631163--