Forum: Ruby Recursive functions

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
D6fca3e33a1112eae1c73c22c83c63d6?d=identicon&s=25 hans.sjunnesson (Guest)
on 2005-11-14 14:49
(Received via mailing list)
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?
6b4566518f6675477dab9b8ba813cf3c?d=identicon&s=25 ruby.brian (Guest)
on 2005-11-14 15:22
(Received via mailing list)
On 14/11/05, hans.sjunnesson@gmail.com <hans.sjunnesson@gmail.com>
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
# 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/
4299e35bacef054df40583da2d51edea?d=identicon&s=25 james (Guest)
on 2005-11-14 15:38
(Received via mailing list)
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 Gray 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
1fba4539b6cafe2e60a2916fa184fc2f?d=identicon&s=25 dblack (Guest)
on 2005-11-14 15:44
(Received via mailing list)
Hi --

On Mon, 14 Nov 2005, hans.sjunnesson@gmail.com 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
D6fca3e33a1112eae1c73c22c83c63d6?d=identicon&s=25 hans.sjunnesson (Guest)
on 2005-11-14 16:14
(Received via mailing list)
I'm not entirely sure what happened here. Did I transgress some
unspoken rule?
4299e35bacef054df40583da2d51edea?d=identicon&s=25 james (Guest)
on 2005-11-14 16:17
(Received via mailing list)
On Nov 14, 2005, at 9:12 AM, hans.sjunnesson@gmail.com 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 Gray II
D6fca3e33a1112eae1c73c22c83c63d6?d=identicon&s=25 hans.sjunnesson (Guest)
on 2005-11-14 16:53
(Received via mailing list)
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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 james (Guest)
on 2005-11-14 17:02
(Received via mailing list)
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.  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 Gray II
D6fca3e33a1112eae1c73c22c83c63d6?d=identicon&s=25 hans.sjunnesson (Guest)
on 2005-11-14 17:08
(Received via mailing list)
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.
5befe95e6648daec3dd5728cd36602d0?d=identicon&s=25 bob.news (Guest)
on 2005-11-14 17:14
(Received via mailing list)
James Edward Gray II wrote:
> 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 ".".

Kind regards

    robert
4299e35bacef054df40583da2d51edea?d=identicon&s=25 james (Guest)
on 2005-11-14 17:20
(Received via mailing list)
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 ".".

Ick.  That's not good.

Naughty gateway.  ;)

James Edward Gray II
4b174722d1b1a4bbd9672e1ab50c30a9?d=identicon&s=25 leavengood (Guest)
on 2005-11-14 17:29
(Received via mailing list)
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.

Ryan
5befe95e6648daec3dd5728cd36602d0?d=identicon&s=25 bob.news (Guest)
on 2005-11-14 17:44
(Received via mailing list)
Ryan Leavengood wrote:
> 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?

Kind regards

    robert
912c61d9da47754de7039f4271334a9f?d=identicon&s=25 mental (Guest)
on 2005-11-14 17:50
(Received via mailing list)
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.

-mental
Dce0999389d102f9a313af625375304c?d=identicon&s=25 dooby (Guest)
on 2005-11-14 19:40
(Received via mailing list)
Robert Klemme 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
4fea1ef11180adaaa299d503ca6010d0?d=identicon&s=25 jwkenne (Guest)
on 2005-11-15 03:18
(Received via mailing list)
James Edward Gray 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.
4fea1ef11180adaaa299d503ca6010d0?d=identicon&s=25 jwkenne (Guest)
on 2005-11-15 03:21
(Received via mailing list)
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.
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 w_a_x_man (Guest)
on 2005-11-15 10:43
(Received via mailing list)
hans.sjunnesson@gmail.com 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 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
F91f1034d620825594db83db92ca1711?d=identicon&s=25 michael.ulm (Guest)
on 2005-11-15 11:01
(Received via mailing list)
William James 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
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 w_a_x_man (Guest)
on 2005-11-15 11:22
(Received via mailing list)
Michael Ulm 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
93d566cc26b230c553c197c4cd8ac6e4?d=identicon&s=25 pit (Guest)
on 2005-11-15 11:40
(Received via mailing list)
William James schrieb:
> triplets.each do |ary|   (3**ary.size).times{ |i|
>   word = (num_to_str(i,3,ary)); p word if dict[word] }
> end

One more improvement:

   def num_to_str( n, base, ary )
     n.to_s(base).rjust(ary.size,"0").split('').zip( ary ).
     inject(""){|out,(i,s)| out << i.tr("0-9a-z",s) }
   end

Regards,
Pit
This topic is locked and can not be replied to.