Re: Reg: tiny contest: who's faster? (add_a_gram)

Hi --

On Sat, 9 Feb 2002, Dave Thomas wrote:

> "Pit Capitain" <[e-mail]> writes:
>
> > * Should it only work with the given or with any word list?
> > * Should it only print the last word or the whole sequence?
>
> The challenge asks for the longest word, not the chain. However,
> adding reporting for the whole chain barely affects the run time. I've
> attached the new version.
>
> However I do think it should work with any list.
>
> > * Is it allowed to use C extensions or has it to be pure Ruby?
>
> Pure Ruby, I'd say.

I agree, though I'm happy to see the strbsrt extension getting some
publicity :-)

Attached is a RubyUnit-ified version of this challenge.  It's probably
sketchier than it should be, in terms of its tests, but feel free
to use it and change it if helpful.

I've included, as the implementation of class AAGFinder, a slightly
hacked version of Dave's solution.  If you want to start again (i.e.,
unit-test your own solution), just reimplement AAGFinder and make
sure that it has a #find_longest method that passes the test.

Code follows sig....


David

-- 
David Alan Black
home: [e-mail]
work: [e-mail]
Web:  http://pirate.shu.edu/~blackdav


#!/usr/local/bin/ruby -w
# addagram.rb

require "runit/testcase"
require "runit/cui/testrunner"
require "runit/testsuite"

class AAGFinder

## BEGIN adapation from Dave Thomas ##

  def initialize(fh)
    @known_failures = {}
    @words = {}
    @words_of_length = []
    @max_length = 0

    fh.read.split.each do |word|
      @words[w = word.unpack("c*").sort.pack("c*")] = word
      len = word.length
      if len > 11
	unless @words_of_length[len]
	  @words_of_length[len] = []
	  @max_length = len if len > @max_length
	end
	@words_of_length[len] << word
      end
    end
  end

  def test_word(the_word, res)
    res << the_word
    return res if the_word.length == 3

    unless @known_failures[the_word]
      word = the_word.dup
      ch = word.slice!(0)
      len = word.length
      (len+1).times do |i|
      return res if @words[word] && test_word(word, res)
      word[i], ch = ch, word[i] if i < len
      end
      @known_failures[the_word] = true
    end
    res.pop
    false
  end

  def find_longest
    @max_length.downto(3) do |l|
      (@words_of_length[l] || []).each do |word|
      res = []
	if test_word(word.unpack("c*").sort.pack("c*"), res)
	  return res.map {|r| @words[r]}.join ","
	end
      end
    end
    nil
  end

## END adaptation from Dave Thomas

end

class AAGTest < RUNIT::TestCase
  def setup
    @af = AAGFinder.new(DATA)
  end

  def test_longest
    aag = @af.find_longest
    assert_equal(aag, %w{alliterations alliteration retaliation
                         alteration,rationale relation retinal
                         rental later tear tar} .join ",")
  end
end

RUNIT::CUI::TestRunner.run(AAGTest.suite)

__END__
accelerating activates adsorbs aggrieves alliteration alliterations
allocators alteration amplifies answerers applied armies assertions
attitude avoid ball bask befall bespeak birthright blocs bookie
brambles broadcasters bumptiousness cached capitalizing catheter
chanter chirped clapping clumsy colonially compatibles concubine
conscript contour corkscrew courtyard crisis curious daunted dedicates
demandingly deserter diagramming directory disjunction distributions
doubter drunks economic elucidate enders envelopes evades exempted
extension fanatics ferried firsts flourishes forgeries frequent gadget
genuinely goaded gratitude guile harboring heifer hitchhiker hounded
ideas implants incompletely inexorably inlet integrate intimated
irrigate judgment knobs later lavishly lewdly litter lowest mallard
masterpiece memorandum midwives mist mooning multiprocessor nauseum
nobly numberer offensiveness ordering overflows palmed parties peers
personalized pierced plasters polloi pourer preparations probings
prophesy publisher quantile railroads rationale reading recognized
referenced rejoiced relation rental reparation resets retaliation
retinal retransmits right roughly sailors scarce seahorse sensed
shapers showy singing sleeper snatched sooner speeded spur statically
stomach structure substantive superbly swearer tail tar tear televise
thermometer timetable towering treasure tuned unconventional unison
unwitting varnishes vineyard wanting whales wised writhes