From: James Edward Gray II Date: 2007-07-11T21:25:06+09:00 Subject: Fwd: Please Forward: Ruby Quiz Submission --Apple-Mail-1--308978481 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Begin forwarded message: > From: "Paul Prestidge" > Date: July 10, 2007 9:57:22 PM CDT > To: submission@rubyquiz.com > Subject: Please Forward: Ruby Quiz Submission > > Hi there, > > Please find attached my submission for rubyquiz 130 - it's a simple > Hangman guesser using a dictionary (not included). It takes a word > on the command-line and will guess letters at it until a solution > is found or the six-fail limit is reached. > > There's documentation and sample output in the comments. > > Thanks, > > Paul Prestidge > > -- > Haikus are easy > But sometimes they don't make sense > Refrigerator --Apple-Mail-1--308978481 Content-Transfer-Encoding: quoted-printable Content-Type: application/octet-stream; x-unix-mode=0666; name=hangman.rb Content-Disposition: attachment; filename=hangman.rb #=0D=0A#=20hangman.rb=20-=20rq130=0D=0A#=20Paul=20Prestidge=20= =0D=0A#=202007-07-11=0D=0A#=0D=0A=0D=0Arequire=20= 'enumerator'=0D=0A=0D=0Amodule=20Hangman=0D=0A=09#=20The=20Guesser=20= class=20represents=20an=20agent=20that,=20given=20a=20Word=20instance,=20= will=20try=0D=0A=09#=20and=20figure=20it=20out=20using=20the=20minimum=20= number=20of=20steps.=20=20It=20uses=20a=20dictionary,=0D=0A=09#=20which=20= is=20passed=20in=20to=20the=20constructor=20along=20with=20the=20word=20= to=20solve.=0D=0A=09class=20Guesser=0D=0A=09=09#=20Create=20a=20new=20= Guesser=20instance=20for=20the=20given=20Word.=20=20You=20can=20also=20= pass=20in=20a=0D=0A=09=09#=20relative=20or=20absolute=20path=20to=20a=20= dictionary,=20which=20must=20be=20a=20file=20containing=0D=0A=09=09#=20= one=20word=20per=20line.=0D=0A=09=09def=20initialize(word,=20= dict=3D'word.list')=0D=0A=09=09=09raise=20'Dictionary=20file=20"%s"=20= does=20not=20exist.'=20%=20[dict]=20unless=20File.exist?(dict)=0D=0A=09=09= =09=0D=0A=09=09=09@word=20=3D=20word=0D=0A=09=09=09@dictionary=20=3D=20= File.readlines(dict).map{|w|=20w.chomp}.select{|w|=20= w.length=3D=3Dword.length}=0D=0A=09=09=09@letters=20=3D=20= ('a'..'z').to_a=0D=0A=09=09end=0D=0A=0D=0A=09=09#=20Choose=20a=20letter=20= and=20check=20if=20it=20exists=20in=20the=20word.=20=20If=20we're=20= certain=20we=0D=0A=09=09#=20know=20what=20the=20word=20is=20now,=20= confirm=20it.=0D=0A=09=09#=0D=0A=09=09#=20This=20method=20also=20= displays=20a=20description=20of=20the=20action=20on=20stdout=20along=20= with=0D=0A=09=09#=20the=20number=20of=20remaining=20possibilities=20(or=20= a=20list=20of=20them,=20if=20there=20are=0D=0A=09=09#=20only=20a=20few).=0D= =0A=09=09def=20go!=0D=0A=09=09=09next_letter=20=3D=20check_next_letter=0D= =0A=09=09=09=0D=0A=09=09=09raise=20'Unknown=20word'=20if=20= @dictionary.size=20=3D=3D=200=20#=20TODO:=20guess=20randomly?=0D=0A=09=09= =09remaining_options=20=3D=20@dictionary.size=20>=2010=20?=20= "#{@dictionary.size}=20possibilities"=20:=20@dictionary.join(',=20')=0D=0A= =09=09=09puts=20'%2i:=20%1s=20=3D>=20%*s=20=3D>=20%s'=20%=20= [@word.turns,=20next_letter,=20@word.length,=20@word,=20= remaining_options]=0D=0A=09=09=09=0D=0A=09=09=09= @word.guess(@dictionary.first)=20if=20@dictionary.size=20=3D=3D=201=0D=0A= =09=09end=0D=0A=0D=0A=09=09#=20Reorder=20the=20letters=20array,=20then=20= take=20the=20first=20letter=20and=20check=20it=20against=0D=0A=09=09#=20= the=20sample=20word.=20=20If=20the=20letter=20appeared=20in=20our=20= word,=20filter=20the=0D=0A=09=09#=20dictionary,=20removing=20words=20= that=20are=20no=20longer=20consistent=20with=20our=20current=0D=0A=09=09= #=20information.=0D=0A=09=09#=0D=0A=09=09#=20Returns=20the=20letter=20= checked.=0D=0A=09=09def=20check_next_letter=0D=0A=09=09=09= recalculate_letter_frequencies=0D=0A=09=09=09letter=20=3D=20= @letters.shift=0D=0A=09=09=09@word.check_letter(letter)=0D=0A=09=09=09= prune_dictionary=0D=0A=09=09=09=0D=0A=09=09=09letter=0D=0A=09=09end=0D=0A= =09=09=0D=0A=09=09#=20This=20is=20the=20core=20of=20the=20Guesser's=20= decision-making.=20=20It=20reorders=20the=0D=0A=09=09#=20letters=20array=20= from=20most=20likely=20to=20least=20likely,=20using=20some=20simple=0D=0A= =09=09#=20heuristics.=20=20The=20Guesser=20then=20uses=20this=20to=20= decide=20which=20letter=20to=0D=0A=09=09#=20guess=20next.=0D=0A=09=09#=0D= =0A=09=09#=20The=20aim=20is=20to=20select=20the=20letter=20which=20would=20= eliminate=20as=20close=20to=20half=0D=0A=09=09#=20the=20remaining=20= words=20as=20possible=20whether=20it=20is=20actually=20in=20the=20word=20= or=20not.=0D=0A=09=09#=20It's=20not=20optimal=20but=20it=20works=20= pretty=20well.=0D=0A=09=09def=20recalculate_letter_frequencies=0D=0A=09=09= =09#=20Calculate,=20for=20each=20letter=20and=20position,=20how=20many=20= words=20in=20the=20list=0D=0A=09=09=09#=20would=20remain=20if=20that=20= combination=20was=20extant.=0D=0A=09=09=09totals=20=3D=20= @dictionary.inject(Hash.new{|h,k|=20h[k]=20=3D=20[0]*@word.size})=20do=20= |hash,word|=20=0D=0A=09=09=09=09word.split('').each_with_index=20do=20= |letter,idx|=0D=0A=09=09=09=09=09hash[letter][idx]=20+=3D=201=20if=20= @word[idx]=20=3D=3D=20?.=0D=0A=09=09=09=09end=0D=0A=09=09=09=09=0D=0A=09=09= =09=09hash=0D=0A=09=09=09end=0D=0A=09=09=09=0D=0A=09=09=09proportions=20= =3D=20Hash[*totals.map=20{=20|k,v|=20[k,=20= v.inject(0){|s,c|s+(0.5-(c.to_f=20/=20@dictionary.size)).abs}=20/=20= v.size]}.flatten]=0D=0A=09=09=09=0D=0A=09=09=09#=20Delete=20letters=20= that=20don't=20appear=20in=20any=20remaining=20dictionary=20words=0D=0A=09= =09=09@letters.delete_if=20{=20|l|=20!proportions.include?(l)=20}=0D=0A=09= =09=09=0D=0A=09=09=09#=20Reorder=20the=20array=20based=20on=20the=20= proportions=20array=0D=0A=09=09=09@letters=20=3D=20@letters.sort_by=20{=20= |l|=20proportions[l]=20}=0D=0A=09=09end=0D=0A=09=09=0D=0A=09=09#=20= Removes=20all=20items=20from=20our=20dictionary=20that=20don't=20fit=20= with=20what=0D=0A=09=09#=20we=20know=20about=20the=20word.=0D=0A=09=09= def=20prune_dictionary=0D=0A=09=09=09@dictionary.delete_if=20{=20|w|=20w=20= !~=20pattern=20}=0D=0A=09=09end=0D=0A=09=09=0D=0A=09=09#=20Returns=20a=20= regular=20expression=20encapsulating=20the=20criteria=20that=20the=20= word=0D=0A=09=09#=20must=20meet,=20given=20what=20we=20currently=20know=20= about=20it.=0D=0A=09=09def=20pattern=0D=0A=09=09=09= Regexp.new('^'+@word.gsub('.',"[#{@letters.join}]")+'$')=0D=0A=09=09end=0D= =0A=09end=0D=0A=0D=0A=09#=20The=20Word=20class=20represents=20a=20= Hangman=20word.=20=20It=20starts=20out=20initially=20as=20a=0D=0A=09#=20= series=20of=20periods,=20and=20each=20time=20a=20successful=20= check_letter=20is=20performed=20more=0D=0A=09#=20letters=20are=20made=20= visible.=0D=0A=09#=0D=0A=09#=20The=20number=20of=20total=20letters=20and=20= failed=20letters=20are=20available=20using=20=0D=0A=09#=20Word#turns=20= and=20Word#fails,=20respectively.=0D=0A=09class=20Word=20<=20String=0D=0A= =09=09attr_reader=20:turns,=20:fails=0D=0A=09=09=0D=0A=09=09def=20= initialize(word)=0D=0A=09=09=09raise=20'Word=20must=20contain=20only=20= alphabetic=20characters'=20unless=20word=20=3D~=20/^[a-z]+$/i=0D=0A=09=09= =09=0D=0A=09=09=09@word=20=3D=20word.downcase=0D=0A=09=09=09@turns,=20= @fails=20=3D=200,=200=0D=0A=09=09=09super=20'.'=20*=20word.length=0D=0A=09= =09end=0D=0A=09=09=0D=0A=09=09#=20Reveal=20all=20instances=20of=20the=20= given=20letter.=20=20Counts=20as=20a=20failed=20guess=0D=0A=09=09#=20if=20= the=20word=20does=20not=20contain=20any=20of=20that=20letter.=0D=0A=09=09= #=0D=0A=09=09#=20Returns=20the=20total=20number=20of=20letters=20= revealed.=0D=0A=09=09def=20check_letter(letter)=0D=0A=09=09=09total=20=3D=20= @word.split('').enum_with_index.inject(0)=20do=20|t,(l,i)|=20=0D=0A=09=09= =09=09if=20l=20=3D=3D=20letter=0D=0A=09=09=09=09=09self[i,1]=20=3D=20l=20= =0D=0A=09=09=09=09=09t=20+=3D=201=0D=0A=09=09=09=09end=0D=0A=09=09=09=09=0D= =0A=09=09=09=09t=0D=0A=09=09=09end=0D=0A=09=09=09=0D=0A=09=09=09@turns=20= +=3D=201=0D=0A=09=09=09@fails=20+=3D=201=20if=20total=20=3D=3D=200=0D=0A=09= =09=09=0D=0A=09=09=09total=0D=0A=09=09end=0D=0A=09=09=0D=0A=09=09#=20= Make=20a=20guess=20at=20the=20complete=20word.=0D=0A=09=09#=0D=0A=09=09#=20= Currently=20does=20not=20impose=20any=20penalties=20for=20incorrect=20= guesses,=20but=20perhaps=0D=0A=09=09#=20they=20should=20exhaust=20a=20= turn=20or=20something=20similar.=0D=0A=09=09def=20guess(word)=0D=0A=09=09= =09replace(word)=20if=20word=20=3D=3D=20@word=0D=0A=09=09end=0D=0A=09=09=0D= =0A=09=09#=20Returns=20true=20if=20the=20word=20has=20been=20solved=20= completely.=0D=0A=09=09def=20solved?=0D=0A=09=09=09self=20=3D=3D=20@word=0D= =0A=09=09end=0D=0A=09end=0D=0Aend=0D=0A=0D=0A#=20If=20this=20file=20is=20= called=20directly,=20it=20will=20create=20an=20agent=20that=20guesses=20= the=20word=0D=0A#=20passed=20in=20ARGV[0].=20=20It=20will=20continue=20= until=20it=20has=20solved=20the=20word=20or=20until=20it=0D=0A#=20has=20= six=20incorrect=20guesses.=0D=0A#=0D=0A#=20Here's=20some=20examples=20of=20= execution=20on=20my=20work=20PC=20(2.7ghz,=20768mb=20RAM)=20with=20a=0D=0A= #=20dictionary=20containing=20264k=20words=20(total=20size=202.59mb):=0D=0A= #=0D=0A#=20=201:=20i=20=3D>=20..........i..=20=3D>=201411=20= possibilities=0D=0A#=20=202:=20e=20=3D>=20.e........i..=20=3D>=2059=20= possibilities=0D=0A#=20=203:=20a=20=3D>=20.e......a.i..=20=3D>=2011=20= possibilities=0D=0A#=20=204:=20r=20=3D>=20.e.....ra.i..=20=3D>=20= demonstrating,=20demonstration=0D=0A#=20=205:=20n=20=3D>=20.e..n..ra.i.n=20= =3D>=20demonstration=0D=0A#=20Solved=20the=20word=20in=205=20turns=20= with=200=20wrong=20guesses.=20=20The=20word=20was=20"demonstration".=0D=0A= #=20Execution=20time:=203.8=20seconds.=0D=0A#=0D=0A#=20=201:=20e=20=3D>=20= ......e=20=3D>=202180=20possibilities=0D=0A#=20=202:=20a=20=3D>=20= .a....e=20=3D>=20271=20possibilities=0D=0A#=20=203:=20i=20=3D>=20.a....e=20= =3D>=20104=20possibilities=0D=0A#=20=204:=20o=20=3D>=20.a.o..e=20=3D>=20= 18=20possibilities=0D=0A#=20=205:=20c=20=3D>=20.a.o..e=20=3D>=20baronne,=20= baroque,=20galoshe,=20garotte,=20gavotte,=20jalouse,=20kagoule,=20= zamouse=0D=0A#=20=206:=20t=20=3D>=20.a.otte=20=3D>=20garotte,=20gavotte=0D= =0A#=20=207:=20v=20=3D>=20.a.otte=20=3D>=20garotte=0D=0A#=20Solved=20the=20= word=20in=207=20turns=20with=203=20wrong=20guesses.=20=20The=20word=20= was=20"garotte".=0D=0A#=20Execution=20time:=206.1=20seconds.=0D=0A#=0D=0A= #=20It=20reports=20to=20stdout.=0D=0Aif=20$0=20=3D=3D=20__FILE__=0D=0A=09= word=20=3D=20Hangman::Word.new($*.shift=20||=20'zeitgeist')=0D=0A=09ai=20= =3D=20Hangman::Guesser.new(word)=0D=0A=09start_time=20=3D=20Time.now=0D=0A= =09=0D=0A=09ai.go!=20until=20word.fails=20>=3D=206=20or=20word.solved?=0D= =0A=09=0D=0A=09if=20word.solved?=0D=0A=09=09puts=20'Solved=20the=20word=20= in=20%i=20turns=20with=20%i=20wrong=20guesses.=20=20The=20word=20was=20= "%s".'=20%=20[word.turns,=20word.fails,=20word]=0D=0A=09else=0D=0A=09=09= puts=20'Could=20not=20solve=20the=20word=20in=20%i=20turns=20with=20%i=20= wrong=20guesses.'=20%=20[word.turns,=20word.fails]=0D=0A=09end=0D=0A=09=0D= =0A=09puts=20'Execution=20time:=20%.1f=20seconds.'=20%=20= [Time.now-start_time]=0D=0Aend= --Apple-Mail-1--308978481 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed --Apple-Mail-1--308978481--