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, 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
#
# 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
On Mon, 14 Nov 2005, 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?
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.
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
···
hans.sjunnesson@gmail.com wrote:
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?
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
···
On Nov 14, 2005, at 8:21 AM, Brian Schröder 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) }
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
···
hans.sjunnesson@gmail.com wrote:
--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com
>
>>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) }
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
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, hans.sjunnesson@gmail.com 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.
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.
On Nov 14, 2005, at 9:52 AM, hans.sjunnesson@gmail.com 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 ".".
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.
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.
···
On Nov 14, 2005, at 9:52 AM, hans.sjunnesson@gmail.com wrote:
--
John W. Kennedy
"But now is a new thing which is very old--
that the rich make themselves richer and not poorer,
which is the true Gospel, for the poor's sake."
-- Charles Williams. "Judgement at Chelmsford"
On Nov 14, 2005, at 10:12 AM, Robert Klemme wrote:
James Edward Gray 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 ".".
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
···
On 11/14/05, Robert Klemme <bob.news@gmx.net> 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 ".".
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.
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.
.... Interesting. Either my client (Thunderbird 1.5 RC1) or my ISP's server seems to have a /different/ problem.
···
On Nov 14, 2005, at 9:52 AM, hans.sjunnesson@gmail.com wrote:
--
John W. Kennedy
"But now is a new thing which is very old--
that the rich make themselves richer and not poorer,
which is the true Gospel, for the poor's sake."
-- Charles Williams. "Judgement at Chelmsford"
On 11/14/05, Robert Klemme <bob.news@gmx.net> 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?
Quoting James Edward Gray II <james@grayproductions.net>:
> 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.
