From: Tobias Reif <tobiasreif@...>
Date: 2002-02-09T02:43:52+09:00
Subject: tiny contest: who's faster? (add_a_gram)

Hi;

Better than Superbowl, bigger than the Olympics;
the Add-A-Gram contest :)

http://www.itasoftware.com/careers/programmers.php

(I'm already last: They asked me to fetch the largest apple,
and I'm still driving around ten truckloads.)

My current solution works correctly with various inputs.
It might have bugs, but most importantly, it takes forever.
Short sample input is no problem; but as soon as I feed it
the 1.5 MB word list from the website, my computer
is overwhelmed, and starts to smell heated after 2 hours :|

So all you wizards, Ruby miners, speed freaks:
do the magic, spread the bliss, and enlighten us newbies.

I propose to compare complete programs featuring
faster concepts, and faster code (pure Ruby).

find.rb
----------8<----------

# tobiasreif@pinkjuice.com
# trying to solve
# http://www.itasoftware.com/careers/programmers.php
#   ruby find.rb word.lst.short
# write all add-a-grams:
#   ruby find.rb word.lst.short d


@file_name = ARGV[0]

@debug == false

if ARGV[1] == 'd'
   @debug = true
end

@word_list = open(@file_name, 'r') do |file|
   file.readlines
end

@word_list = @word_list.map do |word|
   word.chomp
end

class String
   def consists_of? (other)
     a = self.split(//)
     b = other.split(//)
     a.sort == b.sort
   end
end

class Array
   def get_words_consisting_of word
     word_consists_of = word.split(//).to_a.uniq
     start_words_characters = []

     word_consists_of.each do |char|
       each do |dict_word|
         if dict_word[0].chr == char
           start_words_characters.push dict_word
         end
       end
     end

     start_words_characters.select do |item|
       item.consists_of? word
     end

   end
end


def insert_list candidate
   @candidates.push(candidate) unless candidate.empty?
end

def get_next_words candidate, word_list
#p candidate
   word =  candidate
   next_words = []
   ('a'..'z').each do |letter|
      words = word_list.get_words_consisting_of(word+letter)
      words.each do |next_word|
        next_words.push([letter,next_word])
      end
   end
   next_words
end

def make_list candidate, word_list
   word = candidate.last.last.to_s
   next_words = get_next_words candidate.last.last.to_s, word_list
   if next_words.length == 1
     next_words.each do |letter,next_word|
       if not next_word == word
         line =  [word,letter,next_word]
         candidate.push line
         #puts candidate
         #puts line
         word_list.delete word
         word_list.delete next_word
         make_list candidate, word_list
       end
     end
   elsif  next_words.length > 1
     next_words.each do |letter,next_word|
       if not next_word == word
         new_candidate = candidate.dup
         word_list.delete word
         word_list.delete next_word
         candidate.push([word, letter,next_word])
         make_list new_candidate, word_list
       end
     end
   elsif next_words.length == 0
     insert_list candidate
   end
   candidate
end

@candidates = []

def walk
   @word_list.each do |word|
     puts "processing "+word
     make_list [[word]],@word_list.dup
   end
end

walk

@longest = @candidates.select do |array|
   bools = []
   @candidates.each do |a|
     bools.push(array.length >= a.length)
   end
   not(bools.include? false)
   #p bools
end

def format_candidate cand
   if cand.length >=3
     ary = cand.dup
     out = ary[0]+' + '+ary[1]+' = '+ary[2]+"\n"
     else
     ''
   end
end

@longest[0].each do |it|
   print format_candidate(it)
end

open('output.txt', 'w+') do |file|
   #file.write @candidates.inspect
   #file.write @candidates.join "\n\n"
   file.write "one of the longest add-a-grams from #{@file_name}: 
\nlength: "+
    ((@longest[0].length) -1).to_s
   file.write "\n\n"
   @longest[0].each do |it|
     file.write format_candidate(it)
   end
   if @debug == true
      file.write "\n- - - - - - - - - - - - - - - - - \nrest:\n\n"
     @candidates.each do |c|
      if not c.empty?
       c.each do |item|
       #file.write c.inspect
       file.write(format_candidate(item))
       end
       file.write "\n"
      end
     end
   end
end

----------8<----------

word.lst.short
----------8<----------
ail
sail
cram
nails
amarcy
interlaces
charms
chromas
aliens
entrails
clarinets
maraschino
maraschinob
monarchs
harmonics
march
marcy
cails
salient
----------8<----------

output.txt:
----------8<----------
one of the longest add-a-grams from word.lst.short:
length: 7

ail + s = sail
sail + n = nails
nails + e = aliens
aliens + t = salient
salient + r = entrails
entrails + c = clarinets
clarinets + e = interlaces
----------8<----------

Have fun,
Tobi

-- 

* peace&love.
* http://www.pinkjuice.com/