From: James Koppel <jamesbkoppel@...>
Date: 2007-08-01T02:22:09+09:00
Subject: [QUIZ][SOLUTION]Crossword Solver (#132)

--0-1036921883-1185902128=:36260
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable

Sorry for the delay; ruby-talk-ctl suddenly decided to stop working for me.=
=0A=0AThis is another depth-first recursive search. Dictionary should be sa=
ved in wordlist.txt. It implements the first bonus, but not the second.=0A=
=0A$template =3D<<EOL=0A_ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _=0A=0A_ # _ # =
_ # _ # _ # _ # _ # _ # _ # _=0A=0A_ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _=0A=
=0A_ # _ # _ # _ # _ _ _ # _ # _ # _ # _=0A=0A# _ _ _ _ # _ # _ # _ # _ # _=
 _ _ _ #=0A=0A_ # _ # # # _ _ _ _ _ _ _ # # # _ # _=0A=0A_ _ _ _ _ _ # # _ =
# _ # # _ _ _ _ _ _=0A=0A_ # _ # # _ # _ _ _ _ _ # _ # # _ # _=0A=0A_ _ _ _=
 _ _ _ _ # _ # _ _ _ _ _ _ _ _=0A=0A_ # # _ # _ # _ _ _ _ _ # _ # _ # # _=
=0A=0A_ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _=0A=0A_ # _ # # _ # _ _ _ _ _ # =
_ # # _ # _=0A=0A_ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _=0A=0A_ # _ # # # _ _=
 _ _ _ _ _ # # # _ # _=0A=0A# _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #=0A=0A_ # =
_ # _ # _ # _ _ _ # _ # _ # _ # _=0A=0A_ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ =
_=0A=0A_ # _ # _ # _ # _ # _ # _ # _ # _ # _=0A=0A_ _ _ _ # _ _ _ _ _ _ _ _=
 _ # _ _ _ _=0AEOL=0A=0A$dict =3D File.open("wordlist.txt"){|f|f.read.upcas=
e.split(/\n/)}=0A=0Aclass Array=0A  ###This version only works for down and=
 left-to-right, but=0A  ###for this quiz I don't care.=0A  ###Also not real=
ly a line if not at a 0, -45, or -90 degree angle; again, it doesn't matter=
=0A  def each_in_line(y1,x1,y2,x2, &block)=0A    until x1=3D=3Dx2 and y1=3D=
=3Dy2=0A      block.call *([self[y1][x1],y1,x1][0...block.arity])=0A      x=
1 +=3D 1 unless x1=3D=3Dx2=0A      y1 +=3D 1 unless y1=3D=3Dy2=0A    end=0A=
  end=0A  =0A  def deep_dup=0A    self.dup.map do |el|=0A      if el.is_a? =
Array=0A        el.deep_dup=0A      else=0A        el.dup=0A      end=0A   =
 end=0A  end=0Aend=0A=0A###Assumes crossword is rectangular=0A###Returns an=
 array of arrays, each containing an array with the start and end y and x=
=0A###of a section of the crossword to be filled=0Adef word_queue(crossword=
)=0A  queue =3D []=0A  crossword.each_with_index do |row, y|=0A    #"|" is =
just a spacer; preserving hashes eases computing x index=0A    words =3D ro=
w.join.gsub('#','|#|').squeeze('|').split('|')=0A    words.each_with_index =
do |word, n|=0A      next if word.length =3D=3D 1=0A      next unless word.=
include? '_' #For EC 1=0A      queue << [[y,words[0...n].join.length],[y,wo=
rds[0..n].join.length]]=0A    end=0A  end=0A  =0A  crossword[0].each_index =
do |x|=0A    words =3D crossword.map{|row|row[x]}.=0A      join.gsub('#','|=
#|').squeeze('|').split('|')=0A    words.each_with_index do |word, n|=0A   =
   next if word.length =3D=3D 1=0A      next unless word.include? '_' #For =
EC 1=0A      queue << [[words[0...n].join.length, x],[words[0..n].join.leng=
th,x]]=0A    end=0A  end=0A  queue=0Aend=0A=0Adef crossword_solution(crossw=
ord, queue=3Dword_queue(crossword))=0A  return crossword if queue.empty?=0A=
  word_coords =3D queue.first=0A  word_space =3D ""=0A  crossword.each_in_l=
ine(*word_coords.flatten) {|c|word_space << c}=0A  regex =3D Regexp.new("^%=
s$" % word_space.gsub('_','\w'))=0A  possible_words =3D $dict.select{|w| w =
=3D~ regex}.sort_by{rand}=0A  until possible_words.empty?=0A    crossword_c=
opy =3D crossword.deep_dup=0A    word_arr =3D possible_words.shift.split(//=
)=0A    crossword_copy.each_in_line(*word_coords.flatten) do |el,y,x|=0A   =
   crossword_copy[y][x] =3D word_arr.shift=0A    end=0A    solved=3Dcrosswo=
rd_solution(crossword_copy,queue-[word_coords])=0A    return solved if solv=
ed=0A  end=0A  nil=0Aend=0A=0Aputs crossword_solution($template.chomp.gsub(=
' ','').=0A  gsub("\n\n","\n").split(/\n/).map{|s|s.split(//)}).=0A    map{=
|r|r.join}.join("\n").tr('#',' ')=0A                =0A=0A=0A=0A       =0A_=
___________________________________________________________________________=
________=0AGot a little couch potato? =0ACheck out fun summer activities fo=
r kids.=0Ahttp://search.yahoo.com/search?fr=3Doni_on_mail&p=3Dsummer+activi=
ties+for+kids&cs=3Dbz 
--0-1036921883-1185902128=:36260--