# 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

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

from

string

# 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

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

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

\$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 “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.

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.

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.

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:

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.

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.

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.

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

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

X-MIME-Autoconverted: from quoted-printable to 8bit by

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

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:

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