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?
On 14/11/05, [email protected] [email protected]
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.
(c) 2005 Brian Schroeder
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/
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
Hi –
On Mon, 14 Nov 2005, [email protected] 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
I’m not entirely sure what happened here. Did I transgress some
unspoken rule?
On Nov 14, 2005, at 9:12 AM, [email protected] 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
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.
On Nov 14, 2005, at 9:52 AM, [email protected] 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
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.
James Edward G. II wrote:
On Nov 14, 2005, at 9:52 AM, [email protected] 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
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.
James Edward G. II
On 11/14/05, Robert K. [email protected] 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
Ryan L. wrote:
On 11/14/05, Robert K. [email protected] 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
Quoting James Edward G. II [email protected]:
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.
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
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
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.
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.
[email protected] 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 34-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
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
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