[SUMMARY] Word Chains (#44)

(James Edward Gray II) #1

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[i] = 0
              @steps[wdup] << sym
              wdup[i] = word[i]
          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[i] = 0
              if @steps.has_key?(wdup)
                  @steps[wdup].each { |step| yield step }
              end
              wdup[i] = word[i]
          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
          catch(:done) 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
                              throw(:done) 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. :wink: 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) #2

Ruby Quiz wrote:

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 :slight_smile:

(Jim Freeze) #3

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 => %w(--dictionary -d),
                :opt_description => "Alternate dictionary. Default is
in /usr/share/dict/words",
               :arg_description => "path_to_dictionary",
               :opt_found => get_arg,
               :opt_not_found => "/usr/share/dict/words"

      expected_args :word1, :word2
    end

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

Cheers

···

--
Jim Freeze

(Gavin Kistner) #4

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. :wink: 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!

···

On Sep 1, 2005, at 6:55 AM, Ruby Quiz wrote:

(James Edward Gray II) #5

Ruby Quiz wrote:

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.

Certainly any specification is open to interpretation. This time, you and I don't agree on the interpretation of the above. I really think that's fine. Your code works for you. It didn't work for me though, so I chose to skip it. That seemed to work out well for both 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 this isn't mentioned in the quiz. I guess we just thought it was a 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 find a chain where a "minor issue". You may even view your way as correct and my downcase() calls as wrong. That's fine too. You're 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 correct me as needed.

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.

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

Unfortunately, Ruby Quiz does eat a lot of time. This week I've written a quiz, a solution, a time trial script, and a summary. I've watched for the solutions to roll in and added all that code to the wed site. I've also tried to be an active participant in the community, by monitoring and responding to threads like this one. I estimate that it took about a single work day of time and I do it most every week.

Because of that, when I sat down to do the time trails, I was really burning free time I usually give to the summaries. I wrote the first version of the script, ran it, and saw a lot of problems. I handled the external dependancies to fix a couple of them, because I remembered that they needed them. Rinse, repeat. Still a lot of errors, unfortunately.

So, I started opening the solutions one by one and coding workarounds into the time trail script for them. I did two fairly quickly, but the third one was quite different and I struggled to figure out what 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 time. I decided that it would be better for me to use what I currently had and get on to summarizing. To help others who might want to finish the job, I made my work available and suggested how to 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 that at least a couple of people think I did. I sincerely apologize. I was trying to report objectively on what I was seeing, nothing more.

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

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

James Edward Gray II

···

On Sep 1, 2005, at 11:43 AM, Simon Kröger wrote:

(W. James) #6

Simon Kröger wrote:

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[i]=?.; dict[s] << w; s[i]=w[i]}
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[i]=?.; dict[s].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

(James Edward Gray II) #7

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

···

On Sep 2, 2005, at 6:52 AM, Jim Freeze wrote:

(James Edward Gray II) #8

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. :wink: 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. :wink:

Thanks as always for running the quiz!

Thank you for working the quiz and tolerating my mistakes.

James Edward Gray II

···

On Sep 2, 2005, at 9:23 AM, Gavin Kistner wrote:

On Sep 1, 2005, at 6:55 AM, Ruby Quiz wrote:

(Simon Kröger) #9

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) #10

To be clear, I used neither the word "dumb" nor the earlier implied word of "stupid" and I apologize again that you feel I painted it 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 corrected and I will trim some more.

James Edward Gray II

···

On Sep 1, 2005, at 6:29 PM, Simon Kröger wrote:

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).

(Simon Kröger) #11

James Edward Gray II wrote:

[...] 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 :slight_smile: )
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

(Benedikt Heinen) #12

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... :wink:

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

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)

(James Edward Gray II) #13

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

···

On Sep 2, 2005, at 8:07 AM, Benedikt Heinen wrote: