[SUMMARY] Word Chains (#44)

[Ruby Quiz]

Gavin Kistner asked that I try timing the quiz solutions this week. I did
indeed "try" that very thing and the results shocked me. Let's take a look,
shall we:

=== Timing ./Adam Shelly/wordchain ===
Wordchain Finder
Connecting duck -> ruby
nil
=== ./Adam Shelly/wordchain: 0.950922 seconds ===

=== Timing ./Brian Schroeder/wordchain.rb ===
Loading database
Searching connection between duck and ruby
duck
dusk
rusk
ruse
rube
ruby

=== ./Brian Schroeder/wordchain.rb: 3.722559 seconds ===

=== Timing ./Daniel Sheppard/word_chain.rb ===
./Daniel Sheppard/word_chain.rb:42:in `find_distances': undefined local
variable or method `distances' for #<Word:0x1c70ac> (NameError)
from ./Daniel Sheppard/word_chain.rb:46:in `shortest_path'
from ./Daniel Sheppard/word_chain.rb:135
=== ./Daniel Sheppard/word_chain.rb: 0.019652 seconds ===

=== Timing ./David Tran/word_chain.rb ===
Loading dictionary...
Building chain...
No solution.
=== ./David Tran/word_chain.rb: 314.369476 seconds ===

=== Timing ./David Tran/word_chain2.rb ===
Loading dictionary...
Building chain...
No solution.
=== ./David Tran/word_chain2.rb: 1.184791 seconds ===

=== Timing ./Dominik Bathon/word_chain.rb ===
duck
luck
luce
lube
rube
ruby
=== ./Dominik Bathon/word_chain.rb: 1.472335 seconds ===

=== Timing ./Gavin Kistner/word_chain.rb ===
./Gavin Kistner/word_chain.rb:65:in `Integer': invalid value for Integer:
"duck" (ArgumentError)
from ./Gavin Kistner/word_chain.rb:65
=== ./Gavin Kistner/word_chain.rb: 0.020758 seconds ===

=== Timing ./horndude77/wordchain.rb ===
Two words required
=== ./horndude77/wordchain.rb: 0.014078 seconds ===

=== Timing ./James Edward Gray II/word_chain.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./James Edward Gray II/word_chain.rb: 27.577392 seconds ===

=== Timing ./Levin Alexander/word_chains.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./Levin Alexander/word_chains.rb: 2.795315 seconds ===

=== Timing ./Paolo Capriotti/chain.rb ===
no chain could be found
=== ./Paolo Capriotti/chain.rb: 65.236484 seconds ===

=== Timing ./Simon Kroeger/word_chain.rb ===
now way!
=== ./Simon Kroeger/word_chain.rb: 2.981419 seconds ===

=== Timing ./Simon Kroeger/word_chain2.rb ===
./Simon Kroeger/word_chain2.rb:2:in `foreach': No such file or directory -
duck (Errno::ENOENT)
from ./Simon Kroeger/word_chain2.rb:2
=== ./Simon Kroeger/word_chain2.rb: 0.017581 seconds ===

=== Timing ./Will Thimbleby/word_chain.rb ===
duck
dunk
dune
rune
rube
ruby
=== ./Will Thimbleby/word_chain.rb: 63.026336 seconds ===

=== Timing ./William James/word_chain.rb ===
./William James/word_chain.rb:1:in `read': No such file or directory - dict
(Errno::ENOENT)
from ./William James/word_chain.rb:1
=== ./William James/word_chain.rb: 0.024691 seconds ===

=== Timing ./William James/word_chain2.rb ===
./William James/word_chain2.rb:2:in `foreach': No such file or directory -
duck (Errno::ENOENT)
from ./William James/word_chain2.rb:2
=== ./William James/word_chain2.rb: 0.01695 seconds ===

I just ran sixteen programs there all with exactly the same command, outlined in
the quiz. Five of the sixteen programs died with an exception. Six more
printed only an error message or couldn't find a chain. That leaves us with
five chains out of sixteen attempts, about a 31% accuracy ratio. Yikes!

Obviously, the biggest problem are the exceptions and the error messages. These
programs refused to try and build a chain. (Yes, I looked into all of them to
see why and no, I didn't try to fix any of them.) The main issue here was that
people changed my proposed command-line arguments. Some of them moved the
dictionary to an optional third argument and others added new options.

I think new options are great, but was it really that hard to support the quiz
format? Will Thimberly parsed the quiz described arguments in seven lines, so I
think it was reasonable.

Of course, you are always welcome to submit whatever you like as a Ruby Quiz
solution. Along the same lines, I consider myself free to ignore anything that
creates more work for me.

The one exception is that I do try to resolve external dependancies, especially
if you make it easy on me. Paulo Capriotti gave me a link right to the library
needed and Brian included a README that showed how to build a required (and
included!) C extension. Thank you both.

Anyway, if someone would like to resolve all of the above issues and rerun time
trials, please be my guest. If you download the solutions from the Ruby Quiz
site, my time_trial.rb script is in the root directory and hopefully that will
get you started.

The minor issue this time around is that some solutions obviously had trouble
finding chains, at least with my dictionary. Not much to say here except that
unit tests probably could have helped. Several test cases were posted to Ruby
Talk. Hope everyone was trying those as they came in.

Okay, let's clean up those time trials and have another look at them:

=== Timing ./Brian Schroeder/wordchain.rb ===
Loading database
Searching connection between duck and ruby
duck
dusk
rusk
ruse
rube
ruby

=== ./Brian Schroeder/wordchain.rb: 3.722559 seconds ===

=== Timing ./Dominik Bathon/word_chain.rb ===
duck
luck
luce
lube
rube
ruby
=== ./Dominik Bathon/word_chain.rb: 1.472335 seconds ===

=== Timing ./James Edward Gray II/word_chain.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./James Edward Gray II/word_chain.rb: 27.577392 seconds ===

=== Timing ./Levin Alexander/word_chains.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./Levin Alexander/word_chains.rb: 2.795315 seconds ===

=== Timing ./Will Thimbleby/word_chain.rb ===
duck
dunk
dune
rune
rube
ruby
=== ./Will Thimbleby/word_chain.rb: 63.026336 seconds ===

I actually expected Brian's to be the fastest, just from what I had read about
them as they came in. Under the hood, Brian is using a priority queue written
in C. As the saying goes though, the speed is in the algorithm, and Dominik and
Levin prove the truth of it.

For an interesting comparison, Levin is using a plain Ruby priority queue.
Let's take a look at that class:

# inefficient implementation of a priority queue
#
class SimpleQueue
def initialize
@storage = Hash.new { [] }
end
def insert(priority, data)
@storage[priority] = @storage[priority] << data
end
def extract_min
return nil if @storage.empty?
key, val = *@storage.min
result = val.shift
@storage.delete(key) if val.empty?
return result
end
end

If you look at that insert() method, you might find the calls a bit odd. The
code does work, but only because of the awkward assignment that shouldn't be
needed. This is a gotcha that bit me early in learning Ruby so I'll explain it
here in the hope of helping others.

Array.new() can take a number and a block. It will invoke the block the
indicated number of times to generate an Array, using the return value of the
block as each member.

Because Hash.new() also takes a block and will call it when a key is first
accessed without an assignment, the natural assumption is that it uses the
return value, and in truth it does, but it does not set the key to that value!
That's why the extra assignment is needed above.

The fix is to use the passed in Hash and key String objects to set it yourself.
Using that, we can write the above a little more naturally:

# inefficient implementation of a priority queue
#
class SimpleQueue
def initialize
@storage = Hash.new { |hash, key| hash[key] = [] }
end
def insert(priority, data)
@storage[priority] << data
end
def extract_min
return nil if @storage.empty?
key, val = *@storage.min
result = val.shift
@storage.delete(key) if val.empty?
return result
end
end

I just think that's more natural and easy to follow. They work the same.

Looking at the code itself, there's nothing too fancy here. It stores items by
priority in a Hash. The real work is done in extract_min() which just locates
the minimum value, shifts some data off of that Array, and returns it. The
comment warns that it's inefficient, but it sure is easy to setup and use. Hard
to beat that for just fifteen lines of code. Nice work Levin.

Now I want to examine Dominik's lightning fast solution. Here's how it starts:

DEFAULT_DICTIONARY = "/usr/share/dict/words"

# Data structure that efficiently stores words from a dictionary in a way,
# that it is easy to find all words that differ from a given word only at
# one letter (words that could be the next step in a word chain).
# Example: when adding the word "dog", add_word will register "dog" as
# step for "\0og", "d\0g" and "do\0", later each_possible_step("cat")
# will yield all words registered for "\0at", "c\0t" or "ca\0".
class WordSteps
def initialize
@steps = Hash.new { |h, k| h[k] = [] }
@words = {}
end

# yields all words (as strings) that were added with add_word
def each_word(&block)
@words.each_key(&block)
end

# add all steps for word (a string) to the steps
def add_word(word)
sym = word.to_sym
wdup = word.dup
for i in 0...word.length
wdup = 0
@steps[wdup] << sym
wdup = word
end
@words[word] = sym # for allow_shorter and each_word
end

# yields each possible next step for word (a string) as symbol, some
# possible steps might be yielded multiple times
# if allow_shorter is true, word[0..-2].to_sym will also be yielded
# if available
# if allow_longer is true, all words that match /#{word}./ will be
# yielded
def each_possible_step(word, allow_shorter = false,
allow_longer = false)
wdup = word.dup
for i in 0...word.length
wdup = 0
if @steps.has_key?(wdup)
@steps[wdup].each { |step| yield step }
end
wdup = word
end
if allow_shorter && @words.has_key?(tmp = word[0..-2])
yield @words[tmp]
end
if allow_longer && @steps.has_key?(tmp = word + "\0")
@steps[tmp].each { |step| yield step }
end
end

# ...

The comments are just great in this code. If you read them, you'll understand
how the code moves so darn fast. Here's the mini-summary: When called
add_word() maps a word to all possible variations with exactly one letter
changed to a null character. Later, each_possible_step() can use the same
mapping to quickly look up all possibilities for the current word in question.

This can also handle searches where words aren't the same size, though that
wasn't part of the quiz.

# ...

# tries to find a word chain between word1 and word2 (strings) using
# all available steps
# returns the chain as array of symbols or nil, if no chain is found
# shorter/longer determines if shorter or longer words are allowed in
# the chain
def build_word_chain(word1, word2, shorter = false, longer = false)
# build chain with simple breadth first search
current = [word1.to_sym]
pre = { current[0] => nil } # will contain the predecessors
target = word2.to_sym
catchdone) do
until current.empty?
next_step = []
current.each do |csym|
each_possible_step(csym.to_s, shorter, longer) do |ssym|
# have we seen this word before?
unless pre.has_key? ssym
pre[ssym] = csym
throwdone) if ssym == target
next_step << ssym
end
end
end
current = next_step
end
return nil # no chain found
end
# build the chain (in reverse order)
chain = [target]
chain << target while target = pre[target]
chain.reverse
end

# ...

This is the search for a chain. Believe it or not, it's a rather boring
unidirectional breadth-first search. Most people implemented much fancier
searches, but thanks to Domink's dictionary storage this code doesn't need to be
clever.

This code just uses each_possible_step() to walk level-by-level of like words,
until it finds the end word. The pre Hash is used to keep the code from
retracing its steps and to walk the previous word chain to build the final
answer at the bottom of the method.

This method has a nice use of catch() and throw() to create the equivalent of a
labeled goto call in many other languages.

There's one more piece to this class:

# ...

# builds and returns a WordSteps instance "containing" all words with
# length in length_range from the file file_name
def self.load_from_file(file_name, length_range)
word_steps = new
IO.foreach(file_name) do |line|
# only load words with correct length
if length_range === (word = line.strip).length
word_steps.add_word(word.downcase)
end
end
word_steps
end
end

# ...

Here's the simple dictionary reading method. Note the clever use of a Range
argument here, to support word chains of differing sizes. The === check ensures
that the current dictionary word is in the Range we care about, before it's
added to the memory mappings.

Finally, here's the interface code:

# ...

if $0 == __FILE__
dictionary = DEFAULT_DICTIONARY

# parse arguments
if ARGV[0] == "-d"
ARGV.shift
dictionary = ARGV.shift
end
unless ARGV.size == 2
puts "usage: #$0 [-d path/to/dictionary] word1 word2"
exit 1
end
word1, word2 = ARGV[0].strip.downcase, ARGV[1].strip.downcase

shorter = word1.length > word2.length
longer = word1.length < word2.length
length_range = if longer
word1.length..word2.length
else
word2.length..word1.length
end

# read dictionary
warn "Loading dictionary..." if $DEBUG
word_steps = WordSteps.load_from_file(dictionary, length_range)
word_steps.add_word(word2) # if it is not in dictionary

# build chain
warn "Building chain..." if $DEBUG
chain = word_steps.build_word_chain(word1, word2, shorter, longer)

# print result
puts chain || "No chain found!"
end

Most of that is just the code to support the arguments from the quiz. Note the
clever building of the length Range that allows the program to switch behavior
when different sized words are given. All around great code Domink. Thanks for
the lesson!

My thanks to all who were able to understand my command-line argument
instructions this week. Seriously, thanks to all submitters. Many great
solutions this week.

If you don't know what tomorrow's quiz is yet, you're not reading Redhanded
closely enough...

 

[Simon Kröger]

I just ran sixteen programs there all with exactly the same command, outlined in
the quiz. Five of the sixteen programs died with an exception. Six more
printed only an error message or couldn't find a chain. That leaves us with
five chains out of sixteen attempts, about a 31% accuracy ratio. Yikes!

From your original posting:

"Each word in the chain must be in the dictionary and every step along
the chain changes exactly one letter from the previous word."

So i would say printing no chain is exactly correct if there is no
suitable word in the dictionary (and there is no hint saying you can
alter the words in the dictionary).
Maybe it is a hint that 6 programs did actually refused to find a non
existing chain but only 5 did. Its the problem description thats weak,
at least it was misleading for me.

I realy wouldn't write this if you didn't stressed on it.

One of the programs that crashed was my second submission (it wasn't
even labeled as solution) that was just a try to make it as short as
possible (while still being kind of fast) and the change in interface
was clearly mentioned: "the dictionary is the optional third parameter,
no -d"

So, while i think you are in fact "free to ignore anything that creates
more work" i would like to ask you to realy _ignore_ it and stop making
us look stupid on your website.

Again, i realy appreciate this quiz - i wouldn't invest time otherwise -
but if your time (and i would without a doubt understand this) doesn't
allow you to look a bit closer, please make this beweekly or whatever.

with kind regards

Simon

p.s.: yes i'm a bit pissed off, but i will calm down soon

 

[James Edward Gray II]

Ruby Quiz wrote:



=46rom your original posting:

"Each word in the chain must be in the dictionary and every step =20
along the chain changes exactly one letter from the previous word."

So i would say printing no chain is exactly correct if there is no =20
suitable word in the dictionary (and there is no hint saying you =20
can alter the words in the dictionary).
Maybe it is a hint that 6 programs did actually refused to find a =20
non existing chain but only 5 did. Its the problem description =20
thats weak, at least it was misleading for me.

Certainly any specification is open to interpretation. This time, =20
you and I don't agree on the interpretation of the above. I really =20
think that's fine. Your code works for you. It didn't work for me =20
though, so I chose to skip it. That seemed to work out well for both =20=

of us, excepting of course that you are now upset with me.

Note that most people chose to strip whitespace off of the words, but =20=

this isn't mentioned in the quiz. I guess we just thought it was a =20
good idea.

I realy wouldn't write this if you didn't stressed on it.

Well, I'm pretty sure I also wrote that the solutions that couldn't =20
find a chain where a "minor issue". You may even view your way as =20
correct and my downcase() calls as wrong. That's fine too. You're =20
also welcome to write up your own summary from that perspective.

That's why we do all this Ruby Quiz stuff in public, so you can =20
correct me as needed.

So, while i think you are in fact "free to ignore anything that =20
creates more work" i would like to ask you to realy _ignore_ it and =20=

stop making us look stupid on your website.

Most of the time, I don't even do time trials, because I don't think =20
it tells us much. However, I did mention speed in the quiz itself =20
and then one of the quiz workers asked me to time them. Because of =20
that, I decided to make an exception this week.

Unfortunately, Ruby Quiz does eat a lot of time. This week I've =20
written a quiz, a solution, a time trial script, and a summary. I've =20=

watched for the solutions to roll in and added all that code to the =20
wed site. I've also tried to be an active participant in the =20
community, by monitoring and responding to threads like this one. I =20
estimate that it took about a single work day of time and I do it =20
most every week.

Because of that, when I sat down to do the time trails, I was really =20
burning free time I usually give to the summaries. I wrote the first =20=

version of the script, ran it, and saw a lot of problems. I handled =20
the external dependancies to fix a couple of them, because I =20
remembered that they needed them. Rinse, repeat. Still a lot of =20
errors, unfortunately.

So, I started opening the solutions one by one and coding workarounds =20=

into the time trail script for them. I did two fairly quickly, but =20
the third one was quite different and I struggled to figure out what =20
I needed to do to make it happy.

By this point, I'm not having fun and I've used up about an hour of =20
time. I decided that it would be better for me to use what I =20
currently had and get on to summarizing. To help others who might =20
want to finish the job, I made my work available and suggested how to =20=

finish it in the summary. That was as helpful as I could think to be.

Still, I NEVER intended to make ANYONE "look stupid" and it's clear =20
that at least a couple of people think I did. I sincerely =20
apologize. I was trying to report objectively on what I was seeing, =20
nothing more.

A lot of times in a summary I'll point out a minor bug, or offer an =20
alternate chunk of code. I do these things so that readers can add =20
to their mental map of gotchas, and hopefully skip a problem area in =20
the future. I never mean to insult those who's code I'm altering, =20
I'm just making suggestions and drawing attention for the sake of =20
learning. Last week it was even pointed out that my suggested fix =20
was broken and we got to discuss that here on Ruby Talk. I'm very =20
grateful that was brought to my attention so the quiz could be =20
corrected, even if it did make me look dumb.

So again, I'm very sorry for everyone I offended and I strongly =20
encourage you all to follow up anything I post with all the needed =20
corrections. Ruby Quiz is definitely meant to be a group effort.

James Edward Gray II

 

[William James]

One of the programs that crashed was my second submission (it wasn't
even labeled as solution) that was just a try to make it as short as
possible (while still being kind of fast) and the change in interface
was clearly mentioned: "the dictionary is the optional third parameter,
no -d"

Added a line to your program that lets it accept -d.
Since this program is so short compared to the others, I
consider it quite noteworthy.

p=$*.index('-d') and $* << $*[p+1] and $*[p,2]=[]
dict, len = Hash.new{|h,k|h[k] = []}, ARGV[0].size
IO.foreach(ARGV[2] || 'words.txt') do |w| w.chomp!
if w.size != len then next else s = w.dup end
(0...w.size).each{|i|s=?.; dict << w; s=w}
end
t, known = {ARGV[1] => 0}, {}
while !known.merge!(t).include?(ARGV[0])
t = t.keys.inject({}){|h, w|(0...w.size).each{|i|
s=w.dup; s=?.; dict.each{|l|h[l] = w if !known[l]}};h}
warn 'no way!' or exit if t.empty?
end
puts w = ARGV[0]; puts w while (w = known[w]) != 0

 

[Simon Kröger]

Hi James,

i was about to write a lengthy answer.... i will compress it to the
point that is still bothering me:

There is a well known website (for a good reason and especialy for all
ruby users) with my name on it. This website, which might well be the
first hit if you google for ruby and my name, states that i'm to dumb to
create a simple script looking up some words from a dictionary. I realy
hate explaining my next customer why (and perhaps i will never get the
chance to tell him).

I would accept that, but not without beeing able to defend myself. You
may argue i'm doing that already but whatever i write here will be
invisible to anyone who looks at your website. (and i won't argue here
if it has been less subjective whats right and whats wrong)

Maybe this is exaggerated but i hope you got my point, there comes some
responsibility with publicity.

enough, to be a more constructiv:

=== Timing ./Adam Shelly/wordchain ===
Wordchain Finder
Connecting duck -> ruby
duck
ruck
rusk
ruse
rube
ruby
=== ./Adam Shelly/wordchain: 0.703 seconds ===

=== Timing ./Brian Schroeder/wordchain.rb ===
duck
dusk
rusk
ruse
rube
ruby

Loading database
Searching connection between duck and ruby
=== ./Brian Schroeder/wordchain.rb: 2.297 seconds ===

=== Timing ./Daniel Sheppard/word_chain.rb ===
duck
dunk
duns
dubs
rubs
ruby
=== ./Daniel Sheppard/word_chain.rb: 9.328 seconds ===

=== Timing ./David Tran/word_chain.rb ===
Loading dictionary...
Building chain...
duck
ruck
rusk
ruse
rube
ruby
=== ./David Tran/word_chain.rb: 43.89 seconds ===

=== Timing ./David Tran/word_chain2.rb ===
Loading dictionary...
Building chain...
duck
ruck
rusk
ruse
rube
ruby
=== ./David Tran/word_chain2.rb: 7.36 seconds ===

=== Timing ./Dominik Bathon/word_chain.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./Dominik Bathon/word_chain.rb: 1.031 seconds ===

=== Timing ./Gavin Kistner/word_chain.rb ===
Searching in 2634 words with 4 letters
Chain between 'duck' and 'ruby', no longer than 12 links:
duck
dunk
duns
runs
rubs
ruby
--> 9.66s (after loading dictionary)

=== ./Gavin Kistner/word_chain.rb: 10.047 seconds ===

=== Timing ./horndude77/wordchain.rb ===
duck
dunk
dune
rune
rube
ruby
=== ./horndude77/wordchain.rb: 0.156 seconds ===

=== Timing ./James Edward Gray II/word_chain.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./James Edward Gray II/word_chain.rb: 9.266 seconds ===

=== Timing ./Levin Alexander/word_chains.rb ===
duck
ruck
rusk
ruse
rube
ruby
=== ./Levin Alexander/word_chains.rb: 1.438 seconds ===

=== Timing ./Paolo Capriotti/chain.rb ===
duck
dunk
dune
rune
rube
ruby
=== ./Paolo Capriotti/chain.rb: 13.515 seconds ===

=== Timing ./Simon Kroeger/word_chain.rb ===
duck
dunk
duns
runs
rubs
ruby
=== ./Simon Kroeger/word_chain.rb: 1.125 seconds ===

=== Timing ./Simon Kroeger/word_chain2.rb ===
duck
dusk
rusk
ruse
rube
ruby
=== ./Simon Kroeger/word_chain2.rb: 0.829 seconds ===

=== Timing ./Will Thimbleby/word_chain.rb ===
duck
dunk
duns
runs
rubs
ruby
=== ./Will Thimbleby/word_chain.rb: 16.453 seconds ===

=== Timing ./William James/word_chain.rb ===
["duck", "ruck", "rusk", "rust", "rush", "ruse", "rube", "ruby"]
=== ./William James/word_chain.rb: 0.687 seconds ===

=== Timing ./William James/word_chain2.rb ===
duck
dusk
rusk
ruse
rube
ruby
=== ./William James/word_chain2.rb: 0.953 seconds ===

Of course this brings up the whole Benchmark problem, e.g. horndude77's
blazingly fast algorithm uses precalculated files that take an hour to
build.... see recent 'Performance Ruby' thread.

(for me the hardest part was compiling Brian Schroeder's extension on
Windows - "your milage may vary")

cheers

Simon

 

[James Edward Gray II]

There is a well known website (for a good reason and especialy for =20
all ruby users) with my name on it. This website, which might well =20
be the first hit if you google for ruby and my name, states that =20
i'm to dumb to create a simple script looking up some words from a =20
dictionary. I realy hate explaining my next customer why (and =20
perhaps i will never get the chance to tell him).

To be clear, I used neither the word "dumb" nor the earlier implied =20
word of "stupid" and I apologize again that you feel I painted it =20
this way.

The page as been edited:

http://www.rubyquiz.com/quiz44.html

Please let me know if you do not yet feel the problem has been =20
corrected and I will trim some more.

James Edward Gray II

 

[Simon Kröger]

[...]
Please let me know if you do not yet feel the problem has been
corrected and I will trim some more.

James Edward Gray II

No, thats fine, thank you.

I hate spoiling the fun and so i would like to finish this thread, but i
have to be sure some things come across the way i wanted them to be
understood:

1) I realy think you are doing a great job (in general )
1a) I got your point that you didn't want to show someone up.
1b) These Quizes are a major time sink for you and it's awesome that you
keep them comming.

2) I have no problem whatsoever if you find a bug/problem with my code
(or even proof it completely wrong) and post that on your website.
But: If you find my program broken please try to elaborate what went
wrong or just ignore it. (you did that in all summaries i came across
until #44)

3) I should have jumped in writing a profiling script as i was
interested in the results myself. Blame on me and the others who didn't.

4) If you see a similar problem on one of your next quizes i will try to
help where i can. (I'm no native speaker so writing a complete Summary
isn't the best option i guess)

Let's return to the fun of ruby

cheers

Simon

 

[Jim Freeze]

Nice write-up James.

I'm sorry I didn't make a submission, but I had a drive failure
over the weekend and didn't get to complete my solution.

However, albeit a little late, I am posting my command line parsing
solution in the hopes that others will find it as convenient as I do.

require 'rubygems'
require 'commandline'

class App < CommandLine::Application
def initialize
synopsis "[-d] word1 word2"
option :names =3D> %w(--dictionary -d),
pt_description =3D> "Alternate dictionary. Default is
in /usr/share/dict/words",
:arg_description =3D> "path_to_dictionary",
pt_found =3D> get_arg,
pt_not_found =3D> "/usr/share/dict/words"

expected_args :word1, :word2
end

def main
q =3D Quiz44.new(@option_data["--dictionary"])
puts q.find_shortest_path(@word1, @word2)
end
end

Cheers
--=20
Jim Freeze

 

[James Edward Gray II]

Nice write-up James.

Thank you.

I'm sorry I didn't make a submission, but I had a drive failure
over the weekend and didn't get to complete my solution.

Hope you didn't lose data.

However, albeit a little late, I am posting my command line parsing
solution in the hopes that others will find it as convenient as I do.

[snip pretty code]

Thanks for sharing. I see there's another library I need to look
into...

James Edward Gray II

 

[Benedikt Heinen]

Since the ruby quiz is about specific problems, not about the same kind of
basics that happen all over, how about also specifying a minimal
code skeleton and a short sentence about how the scripts will be tested?
e.g. for the word chains quiz, if the quiz itself would have provided:


Skeleton:
-
unless ARGV.size == 3
puts "usage: #$0 dictionary word1 word2"
exit 1
end

dictfile=ARGV[0];
fromword=ARGV[1];
toword=ARGV[2];


## INSERT YOUR CODE HERE

-
Code will be tested with the following command(s):


./yourscript.rb /usr/share/dict/words duck ruby


Especially, if, as in the case of wordchains, external resources are
needed, require their specification on the command line - having everyone
hardcode those will probably not be a smart move... ;-)




As for myself - I'll probably go back lurking... Maybe I'll join for the
next quiz: MUDs really just aren't my thing... ;-)





Benedikt

ALLIANCE, n. In international politics, the union of two thieves who
have their hands so deeply inserted in each other's pockets that
they cannot separately plunder a third.
(Ambrose Bierce, The Devil's Dictionary)

 

[Gavin Kistner]

--Apple-Mail-1--812587248
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

Gavin Kistner asked that I try timing the quiz solutions this
week. I did
indeed "try" that very thing and the results shocked me. Let's
take a look,
shall we: [...]
=== Timing ./Gavin Kistner/word_chain.rb ===
./Gavin Kistner/word_chain.rb:65:in `Integer': invalid value
for Integer:
"duck" (ArgumentError)
from ./Gavin Kistner/word_chain.rb:65
=== ./Gavin Kistner/word_chain.rb: 0.020758 seconds === [...]
My thanks to all who were able to understand my command-line argument
instructions this week. Seriously, thanks to all submitters.
Many great
solutions this week.

D'oh! Consider me well-and-duly admonished. I understood the
instructions you laid out in the quiz, and then ran out of time to
implement the proper interface. (I was thinking I needed to write a
whole nice usage bit, which would have taken more time than I was
willing to spend on that polish. I wish I had thought of just
throwing out "-d" like some others did.)

I selfishly assumed that you could account for the idiosyncratic
interface I provided; by extension I was placing the burden on you of
hand tailoring any such tests to whatever non-standard interface
anyone else may have chosen, also. This might have been doable (if
still selfish) had only 2 or 3 people responded to the quiz. I
certainly would agree, however, that when the quiz solutions poured
in as they did (like so much informational flooding) it is wholly
unreasonable.

If you were a teacher paid to instruct, I might expect (or at least
desire) a deeper level of investigation. ("You got the final answer
wrong, and will lose points for it, but let's look in-depth at your
work to see what mistake you may have made.") But Ruby Quiz is
entirely voluntary, and I believe that I should take the time to make
your job of running it as easy as possible. Especially if I make
additional requests of the analysis.

Zero sarcasm in the above. My sincere apologies for turning in code
that clearly didn't adhere to the interface requirements.

I think even the analysis of the failing solutions is a good lesson -
in the business world and many other areas of life, first impressions
and exterior polish can be more important than what's under the hood.

Thanks as always for running the quiz!

--Apple-Mail-1--812587248--

 

[James Edward Gray II]

Since the ruby quiz is about specific problems, not about the same
kind of basics that happen all over, how about also specifying a
minimal code skeleton and a short sentence about how the scripts
will be tested? e.g. for the word chains quiz, if the quiz itself
would have provided:


Skeleton:
-
unless ARGV.size == 3
puts "usage: #$0 dictionary word1 word2"
exit 1
end

dictfile=ARGV[0];
fromword=ARGV[1];
toword=ARGV[2];


## INSERT YOUR CODE HERE

I really don't want to tell anyone how to write their code. That
rules out interesting options like the CommandLine::Application
variant recently posted.

-
Code will be tested with the following command(s):


./yourscript.rb /usr/share/dict/words duck ruby

I will definitely be more careful with testing in the future.

Thanks for the suggestions!

James Edward Gray II

 

[James Edward Gray II]

Gavin Kistner asked that I try timing the quiz solutions this
week. I did
indeed "try" that very thing and the results shocked me. Let's
take a look,
shall we:
[...]

=== Timing ./Gavin Kistner/word_chain.rb ===
./Gavin Kistner/word_chain.rb:65:in `Integer': invalid value
for Integer:
"duck" (ArgumentError)
from ./Gavin Kistner/word_chain.rb:65
=== ./Gavin Kistner/word_chain.rb: 0.020758 seconds ===
[...]

My thanks to all who were able to understand my command-line argument
instructions this week. Seriously, thanks to all submitters.
Many great
solutions this week.

D'oh! Consider me well-and-duly admonished.

Sorry about that. Word on the street is that James was cranky when
he wrote this week's summary.
He's all better now though.

Thanks as always for running the quiz!

Thank you for working the quiz and tolerating my mistakes.

James Edward Gray II