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

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) }
end

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


>    I know it's a computer practise to have a
> function call itself. Is that needed here? Because I'm running into a
> problem having nested loops, because the words are of variable length.
> Any ideas on this?
> 
> -- 
> Hans