Recursive functions


#1

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?


#2

On 14/11/05, removed_email_address@domain.invalid removed_email_address@domain.invalid
wrote:

pyq
Combining a letter from each triplet, you can form words which will
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.

© 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, 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/


#3

On Nov 14, 2005, at 8:21 AM, Brian Schröder wrote:

Be carefull. Spoiler below

Brian was faster than me. My own attempt follows, again, a spoiler…

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

James Edward G. II

def combine( triplets, combinations = [""] )
chrs = triplets.shift.split("")
combos = combinations.map { |combo| chrs.map { |chr| combo +
chr } }.flatten

combos.delete_if do |start|
!$dict[start.length + triplets.length].any? { |word| word =~ /^#
{start}/ }
end

if triplets.empty?
combos
else
combine(triplets, combos)
end
end

warn “Loading dictionary…” if $DEBUG
$dict = Hash.new { |words, len| words[len] = Array.new }
File.foreach("/usr/share/dict/words") do |line|
word = line.downcase.delete("^a-z")
$dict[word.length] << word
end
warn “Loaded.” if $DEBUG

warn “Building word list:” if $DEBUG
puts
DATA.each_line("") do |line|
puts combine(line.strip.downcase.split)
puts
end

END
ubc
deg
lap
pyq

ved
run
pac
ken
alm
mli
rnt
alg


#4

Hi –

On Mon, 14 Nov 2005, removed_email_address@domain.invalid wrote:

pyq
Combining a letter from each triplet, you can form words which will
problem having nested loops, because the words are of variable length.
Any ideas on this?

Several years ago I wrote a Boggle program in Ruby (actually networked
Boggle), which did something similar. I don’t remember exactly
what I did, and I’m afraid I don’t have time to remind myself and
comment on it, but I can send it to you if you’re interested.

David


#5

I’m not entirely sure what happened here. Did I transgress some
unspoken rule?


#6

On Nov 14, 2005, at 9:12 AM, removed_email_address@domain.invalid wrote:

I’m not entirely sure what happened here. Did I transgress some
unspoken rule?

Not at all. Us geeks just decided to answer your question in code.
We don’t get out much. :wink:

Did it help?

James Edward G. II


#7

There must be something wrong with reading this newsgroup via
groups.google.com then, because all I see from both you and Brian
Schröder is a warning of spoilers, then nothing more.


#8

On Nov 14, 2005, at 9:52 AM, removed_email_address@domain.invalid wrote:

There must be something wrong with reading this newsgroup via
groups.google.com then, because all I see from both you and Brian
Schröder is a warning of spoilers, then nothing more.

Naughty Google. Try these links instead:

http://ruby-talk.org/cgi-bin/scat.rb/ruby/ruby-talk/165659

and

http://ruby-talk.org/cgi-bin/scat.rb/ruby/ruby-talk/165662

Hope that helps.

James Edward G. II


#9

They do indeed. I think the dots might confuzzle google. Anyway, it
works, and I’m grateful for your help, both to you and Brian.
And they do indeed help with my problem.


#10

James Edward G. II wrote:

On Nov 14, 2005, at 9:52 AM, removed_email_address@domain.invalid wrote:

There must be something wrong with reading this newsgroup via
groups.google.com then, because all I see from both you and Brian
Schröder is a warning of spoilers, then nothing more.

Naughty Google.

I don’t think Google is to blame. The gateway software is more likely
to
be the culprit: When reading via NNTP these lines are missing, too. I
guess it has something to do with lines that consist only of “.”.

Kind regards

robert

#11

On Nov 14, 2005, at 10:12 AM, Robert K. wrote:

James Edward G. II wrote:

Naughty Google.

I don’t think Google is to blame. The gateway software is more
likely to
be the culprit: When reading via NNTP these lines are missing, too. I
guess it has something to do with lines that consist only of “.”.

Ick. That’s not good.

Naughty gateway. :wink:

James Edward G. II


#12

On 11/14/05, Robert K. removed_email_address@domain.invalid wrote:

I don’t think Google is to blame. The gateway software is more likely to
be the culprit: When reading via NNTP these lines are missing, too. I
guess it has something to do with lines that consist only of “.”.

I’ll venture a guess it has something to do with a single dot alone on
a line signaling the end of DATA in an SMTP session. Clearly other
mail agents can handle this, so the gateway needs some tweaking.

Ryan


#13

Ryan L. wrote:

On 11/14/05, Robert K. removed_email_address@domain.invalid wrote:

I don’t think Google is to blame. The gateway software is more
likely to be the culprit: When reading via NNTP these lines are
missing, too. I guess it has something to do with lines that
consist only of “.”.

I’ll venture a guess it has something to do with a single dot alone on
a line signaling the end of DATA in an SMTP session. Clearly other
mail agents can handle this, so the gateway needs some tweaking.

I’ll join you guessing. More precisely, I suspect the GW software
doesn’t
escape those dots when sending a posting from mail to the news side.
Dennis, can you chime in?

Kind regards

robert

#14

Quoting James Edward G. II removed_email_address@domain.invalid:

I don’t think Google is to blame. The gateway software is more
likely to be the culprit: When reading via NNTP these lines are
missing, too. I guess it has something to do with lines that
consist only of “.”.

Ick. That’s not good.

Naughty gateway. :wink:

It’s one of those little gotchas with these old-school messaging
protocols. In many cases, lines with single periods are
end-of-message markers.

It’s rather like having to avoid starting lines that start with
From as it is also an end-of-message (or rather,
beginning-of-message) marker in certain mailbox formats.

If you’re lucky, some of the software along the way will quote the
“special” strings, but everybody has slightly different rules and
nobody is consistent.

Some days I think it’s amazing that this stuff works as well as it
does.

-mental


#15

Robert K. wrote:

mail agents can handle this, so the gateway needs some tweaking.

I’ll join you guessing. More precisely, I suspect the GW software doesn’t
escape those dots when sending a posting from mail to the news side.

http://ruby-talk.org/ruby/ruby-talk/165659

X-MIME-Autoconverted: from quoted-printable to 8bit by
blade.nagaokaut.ac.jp id jAEELRZk017807

http://ruby-talk.org/ruby/ruby-talk/165662

X-MIME-Autoconverted: from quoted-printable to 8bit by
blade.nagaokaut.ac.jp id jAEEZkZk022188

My guess is that it’s the same problem that the newsgroup / google
sees with messages being truncated at ‘=’ signs in some other
“quoted-printable” posts.

I think it’s recommended to post to newsgroups in plain text
(uuencoded) but a growing number of the list members are
mailing MIME (quoted-printable). That’s not wrong and I guess
most wouldn’t care but, unless you selected “q-p” knowingly -
rather than it being the default in your mail agent, the problem
wouldn’t occur if it could be reset to something else.

daz


#16

John W. Kennedy wrote:



This line was preceded by three lines containing only a period.

… Interesting. Either my client (Thunderbird 1.5 RC1) or my ISP’s
server seems to have a /different/ problem.


#17

James Edward G. II wrote:

and

http://ruby-talk.org/cgi-bin/scat.rb/ruby/ruby-talk/165662

Hope that helps.

It’s not Google’s fault; I’m not seeing it, either, using Thunderbird.
The “.” you’re putting in column 1 for spoiler space is truncating the
message. That shouldn’t happen; e.g.,



This line was preceded by three lines containing only a period.


#18

removed_email_address@domain.invalid wrote:

pyq
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 34 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


#19

William J. wrote:

deg
alg
“uday”, “udaq” and so on?
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) }

end

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

Michael


#20

Michael U. wrote:

mli
here’s my problem. How do I recurse the words in the best way? What I
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