From: William James <w_a_x_man@...>
Date: 2005-11-15T19:22:17+09:00
Subject: Re: Recursive functions

Michael Ulm wrote:
> William James wrote:
>
> > hans.sjunnesson@gmail.com wrote:
> >
> >>I know that this is a trivial problem, but I'm having a hard time
> >>solving it with tuby. I could use a little extra help with my
> >>programming in ruby skills.
> >>
> >>The problem I'm faced to solving (taken from a puzzle in a newspaper)
> >>is a series of alphabetical triplets like:
> >>
> >>ubc
> >>deg
> >>lap
> >>pyq
> >>
> >>ved
> >>run
> >>pac
> >>ken
> >>alm
> >>mli
> >>rnt
> >>alg
> >>
> >>Combining a letter from each triplet, you can form words which will
> >>form a sentence (in the above case: 'ugly duckling').
> >>What I want to do is go through all possible permutations of
> >>characters, in the triplets, and crossreference them with a dictionary
> >>to create all possible permutations of words in a sentence. I've put
> >>the above triplets into an array of arrays: [["ubc", "deg", "lap",
> >>"pyq"], ["ved", "run", "pac", "ken", "alm", "mli", "rnt", "alg"]]. Now
> >>here's my problem. How do I recurse the words in the best way? What I
> >>want to do is start to check "udlp", "udly", "udlq", then "udap",
> >>"uday", "udaq" and so on?
> >
> >
> > There are 3**4 combinations. Instead of using recursion, we can simply
> > count from 0 to 3**4-1:
> >
> > dict={}; IO.readlines(ARGV.pop||"words.txt").each{|w| dict[w.chomp]=""}
> > triplets = [ %w(ubc deg lap pyq), %w(ved run pac ken alm mli rnt alg) ]
> >
> > def num_to_str( n, base, ary )
> >   n.to_s(base).rjust(ary.size,"0").split('').zip( ary ).
> >   inject(""){|out,x| out << x.first.tr("012",x.last) }
>
> to keep the function usable for any base up to 36, change
> that line to
>
>    inject(""){|out,x| out << x.first.tr("0-9a-z",x.last) }

True.  Improvement to the reading of the word-list is also possible:

dict={}; IO.foreach(ARGV.pop||"words.txt"){|w| dict[w.chomp] = "" }
triplets = [ %w(ubc deg lap pyq), %w(ved run pac ken alm mli rnt alg) ]

def num_to_str( n, base, ary )
  n.to_s(base).rjust(ary.size,"0").split('').zip( ary ).
  inject(""){|out,x| out << x.first.tr("0-9a-z",x.last) }
end

triplets.each do |ary|   (3**ary.size).times{ |i|
  word = (num_to_str(i,3,ary)); p word if dict[word] }
end