From: "Brian Schröder" <ruby.brian@...>
Date: 2005-11-14T23:21:14+09:00
Subject: Re: Recursive functions

On 14/11/05, hans.sjunnesson@gmail.com <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? 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
>
>
>

Be carefull. Spoiler below

.
.
.
.
.
.
.
.
.
.
.
.
.

#!/usr/bin/ruby
#
# Solve letter combination puzzle.
#
# Loads a wordlist from /usr/share/dict/words and reads a tuple string from
# stdin. Outputs for each (empty line delimited) wordpuzzle in the input string
# a list of matching words.
#
#
# (c) 2005 Brian Schroeder
# http://ruby.brian-schroeder.de/
#

data = (ARGV.empty? ? DATA : ARGF).read

words = data.split(/\n(?:\s*\n)+/)

def combinations(possibilities)
  return [""] if possibilities.empty?
  first, *rest = *possibilities
  first.inject([]) { | r, p |
    combinations(rest).inject(r) { | r, combination |
      r << (p + combination)
    }
  }
end

wordlist = File.read("/usr/share/dict/words").
                downcase.
		split(/\n/).
		inject({}) { | r, w | r[w] = w; r }

words.each do | word |
  possibilities =  word.split(/\n/).map { | line | line.split(//) }
  combinations(possibilities).each do | combination |
    puts combination if wordlist[combination]
  end
  puts
end


__END__
rdl
uah
kcb
ykc

mht
yej
pul
ipd
ena
grn

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/