Iterating a string through an array, need help?

ruby-talk
1

I'm working on making a word game with my friend, but ran into this
problem I can't solve.

So say I have the string:

example = "stringy"

And the array:

ex_array = ['estrange', 'gingerly', 'stop', 'geek', 'dry', 'rad', 'ear',
'wrinkle', 'cringy', 'guy', 'stringwingy']

Now, I want to iterate each letter of "stringy" through this array.....
s-t-r-i-n-g-y....

The loop should return the words from the array that meet the following
conditions:

1) Contain more than 1 consonant (assuming y is a consonant)

2) Returns a match to any consecutive group of character in the
"stringy" (ex. 'st', 'str', 'stri'..etc)

3) Displays the groups of phrases that can be matched from inside of the
array, leaving no letter in the "string" unaccounted for.

4) Displays a count of total number of matches at the bottom.

Desired output from the example above: # text to the right of # is not
to be printed by the loop

estrange gingerly # str ingy MATCH
stop cringy # st ringy MATCH
stop wrinkle guy # st rin gy MATCH
stringywingy # stringy MATCH
Total: 4 matches

···

---
# geek, dry, rad, ear are not a match for any consecutive (min 2)
letters in 'stringy'
# 'ear' has too many consonants
# estrange cringy is not a match because the 'r' overlaps

Is there a way to get this done with nested for loops, or any other more
efficient way?

Thanks :wink:

--
Posted via http://www.ruby-forum.com/.

2

Why does "gingerly" -> "ingy" rather than "ing"?
Why does "guy" -> "gy" rather than nothing?

···

--
Posted via http://www.ruby-forum.com/.

3

You cannot do it in one shot. You have to come up with the perfect
algorithm. Although one can come up with a piece a code for you to start
but I'll leave a few hints so you get to practice, which is what you
definitely want. Assuming irb, start by doing this:

1. Construct an array out of each character

find = "stringy".each_char.map { |x| p x }

=> ["s", "t", "r", "i", "n", "g", "y"]

2. Make a consecutive array for each of the characters of "find".

continuous_array = (0...find.length).to_a.each { |x| p find[0..x] }

=> ["s"]
["s", "t"]
["s", "t", "r"]
["s", "t", "r", "i"]
["s", "t", "r", "i", "n"]
["s", "t", "r", "i", "n", "g"]
["s", "t", "r", "i", "n", "g", "y"]

3. Similarly, do it for the reverse order:

reverse_continuous_array = (-find.length..-1).to_a.reverse.each { |x| p

find[x..-1] }
=> ["y"]
["g", "y"]
["n", "g", "y"]
["i", "n", "g", "y"]
["r", "i", "n", "g", "y"]
["t", "r", "i", "n", "g", "y"]
["s", "t", "r", "i", "n", "g", "y"]

Now, you have got your building blocks. Now it is up to you to what you
want to do with them (mainly append them into a big array of arrays and
then loop through them using "loop" or whatever way you find easy and
search through your ex_array, find the matches with Array#include? and
construct your results).

···

On Thu, Dec 19, 2013 at 12:13 AM, Jim Whittaker <lists@ruby-forum.com>wrote:

I'm working on making a word game with my friend, but ran into this
problem I can't solve.

So say I have the string:

example = "stringy"

And the array:

ex_array = ['estrange', 'gingerly', 'stop', 'geek', 'dry', 'rad', 'ear',
'wrinkle', 'cringy', 'guy', 'stringwingy']

Now, I want to iterate each letter of "stringy" through this array.....
s-t-r-i-n-g-y....

The loop should return the words from the array that meet the following
conditions:

1) Contain more than 1 consonant (assuming y is a consonant)

2) Returns a match to any consecutive group of character in the
"stringy" (ex. 'st', 'str', 'stri'..etc)

3) Displays the groups of phrases that can be matched from inside of the
array, leaving no letter in the "string" unaccounted for.

4) Displays a count of total number of matches at the bottom.

Desired output from the example above: # text to the right of # is not
to be printed by the loop

estrange gingerly # str ingy MATCH
stop cringy # st ringy MATCH
stop wrinkle guy # st rin gy MATCH
stringywingy # stringy MATCH
Total: 4 matches

---
# geek, dry, rad, ear are not a match for any consecutive (min 2)
letters in 'stringy'
# 'ear' has too many consonants
# estrange cringy is not a match because the 'r' overlaps

Is there a way to get this done with nested for loops, or any other more
efficient way?

Thanks :wink:

--
Posted via http://www.ruby-forum.com/\.

4

I'm not even sure where to begin. I want to iterate every letter of
stringy through ex_array. I'd first iterate pairs, 'st', 'ri', 'ngy'.
Then another combination 'st' 'rin' 'gy'. Then 'str' 'in' 'gy'. And on
and on, until finally testing 'stringy' itself, every sequential
possible pair, three, four, etc, of chars in stringy. (assuming stringy
or whatever could be 100+ chars long). As well, I'd like to keep a
running total of the amount of results--with no repeats!

There must be a simple way to do it?

···

--
Posted via http://www.ruby-forum.com/.

5

I just have to say, this is quite a complicated little task you've set
yourself. I spent a couple of hours getting something[1] to even
vaguely do what you want, and it's neither very clever (detecting
redundancy) nor very optimal. It also doesn't do the extra stuff, like
detecting dupes or keeping tallies.

Oh and the section from lines 84-106 is an indulgence on my part, but it
really helps understand what's going on.

[1]

···

--
Posted via http://www.ruby-forum.com/.

6

This is how you do it.

henry

···

On 19/12/2013, at 8:13 am, Jim Whittaker <lists@ruby-forum.com> wrote:

2) Returns a match to any consecutive group of character in the
"stringy" (ex. 'st', 'str', 'stri'..etc)

7

Very clever Regexp building! I like that one :smiley:

···

--
Posted via http://www.ruby-forum.com/.

8

Joel Pearson wrote in post #1131012:

Why does "gingerly" -> "ingy" rather than "ing"?
Why does "guy" -> "gy" rather than nothing?

Both of these contain consecutive characters in the word "stringy"
within the word itself, if you take out the letters not found in
"stringy".

With guy, you'd take out the u, and you are left with 'gy'. "gray"
would not work, because you would take out the character not in
stringy--a--and you'd be left with 'gry', which is not a match because
while 'gry' are in stringy, they are not in stringy successively.

Same thing for gingerly. Take out the non-stringy characters and you
are left with ingy, which is valid since it's a part of stringy.

Thanks for the question, hope that clears it up a bit?

···

--
Posted via http://www.ruby-forum.com/\.

9

Henry Maddocks wrote in post #1131042:

···

On 19/12/2013, at 8:13 am, Jim Whittaker <lists@ruby-forum.com> wrote:

2) Returns a match to any consecutive group of character in the
"stringy" (ex. 'st', 'str', 'stri'..etc)

This is how you do it.

henry

I think I may be able to figure this part out. But I can't figure out
how to exclude dup's or keep a running count of that total (non-dup's).

--
Posted via http://www.ruby-forum.com/\.

10

Yes, this is a complicated problem. You can come close to a reasonable solution with brute force techniques (i.e many nested loops) but it will very likely be inefficient and quite limited. There are specialized algorithms for dealing with such problems, like n-gram and approximate string matching algorithms.

Regards,
Ammar

···

On Dec 19, 2013, at 5:30 AM, Matthew Kerwin <lists@ruby-forum.com> wrote:

I just have to say, this is quite a complicated little task you've set
yourself. I spent a couple of hours getting something[1] to even

11

Henry Maddocks wrote in post #1131042:

2) Returns a match to any consecutive group of character in the
"stringy" (ex. 'st', 'str', 'stri'..etc)

This is how you do it.

henry

I think I may be able to figure this part out. But I can't figure out
how to exclude dup’s

Array#uniq

or keep a running count of that total (non-dup's).

Array#length

Show us what you have so far

Henry

···

On 19/12/2013, at 4:13 pm, Jim Whittaker <lists@ruby-forum.com> wrote:

On 19/12/2013, at 8:13 am, Jim Whittaker <lists@ruby-forum.com> wrote:

12

Dear Jim Whittaker,

Do you know the coin partition problem?

http://projecteuler.net/problem=78

Can you tell me if the way you are willing to iterate through the
pairs, triples (partitions) has any similarities with the "coin
partition" problem?

def partitions(str)
  ary = [[str]]
  0.upto(str.size-2) do |first_slice_index| # don't recurse at the
last element (so size-2)
    first_slice = str[0..first_slice_index]
    second_slice = str[(first_slice_index+1)..-1]
    other_slices = partitions(second_slice) # recursively
    other_slices.each do |slice|
      candidate = [first_slice] + slice
      ary.push candidate
    end
  end
  ary
end

This code returns an Array of Array of "partitions" of the str.

I think these are the "candidates" you want to test for a match, am I right?

partitions("a")
# => [["a"]]

partitions("ab")
# => [["ab"], ["a", "b"]]

partitions("abc")
# => [["abc"], ["a", "bc"], ["a", "b", "c"], ["ab", "c"]]

partitions("abcd")
# => [["abcd"], ["a", "bcd"], ["a", "b", "cd"], ["a", "b", "c", "d"],
["a", "bc", "d"], ["ab", "cd"], ["ab", "c", "d"], ["abc", "d"]]

For "stringy" it gives me this. A 64 elements Array of Arrays.

[["stringy"], ["s", "tringy"], ["s", "t", "ringy"], ["s", "t", "r",
"ingy"], ["s", "t", "r", "i", "ngy"], ["s", "t", "r", "i", "n", "gy"],
["s", "t", "r", "i", "n", "g", "y"], ["s", "t", "r", "i", "ng", "y"],
["s", "t", "r", "in", "gy"], ["s", "t", "r", "in", "g", "y"], ["s",
"t", "r", "ing", "y"], ["s", "t", "ri", "ngy"], ["s", "t", "ri", "n",
"gy"], ["s", "t", "ri", "n", "g", "y"], ["s", "t", "ri", "ng", "y"],
["s", "t", "rin", "gy"], ["s", "t", "rin", "g", "y"], ["s", "t",
"ring", "y"], ["s", "tr", "ingy"], ["s", "tr", "i", "ngy"], ["s",
"tr", "i", "n", "gy"], ["s", "tr", "i", "n", "g", "y"], ["s", "tr",
"i", "ng", "y"], ["s", "tr", "in", "gy"], ["s", "tr", "in", "g", "y"],
["s", "tr", "ing", "y"], ["s", "tri", "ngy"], ["s", "tri", "n", "gy"],
["s", "tri", "n", "g", "y"], ["s", "tri", "ng", "y"], ["s", "trin",
"gy"], ["s", "trin", "g", "y"], ["s", "tring", "y"], ["st", "ringy"],
["st", "r", "ingy"], ["st", "r", "i", "ngy"], ["st", "r", "i", "n",
"gy"], ["st", "r", "i", "n", "g", "y"], ["st", "r", "i", "ng", "y"],
["st", "r", "in", "gy"], ["st", "r", "in", "g", "y"], ["st", "r",
"ing", "y"], ["st", "ri", "ngy"], ["st", "ri", "n", "gy"], ["st",
"ri", "n", "g", "y"], ["st", "ri", "ng", "y"], ["st", "rin", "gy"],
["st", "rin", "g", "y"], ["st", "ring", "y"], ["str", "ingy"], ["str",
"i", "ngy"], ["str", "i", "n", "gy"], ["str", "i", "n", "g", "y"],
["str", "i", "ng", "y"], ["str", "in", "gy"], ["str", "in", "g", "y"],
["str", "ing", "y"], ["stri", "ngy"], ["stri", "n", "gy"], ["stri",
"n", "g", "y"], ["stri", "ng", "y"], ["strin", "gy"], ["strin", "g",
"y"], ["string", "y"]]

Let us know if this is the issue.
And if this is not the issue, just sorry for misunderstanding the point.

I saw you saying that you wanted to iterate through "pairs" first. So I ask:
Does not single letters be allowed? (note that this partitions above
iterate through single letters combination also).
When iterating through pairs, if the str is "abcde", the "ab", "cd",
"e" will be allowed? (the "e" is a single letter).
The same above and "ab", "cde" will be allowed ? ("cde" is triple and
we began with a pair "ab").

Best regards,
Abinoam Jr.

···

On Thu, Dec 19, 2013 at 4:34 AM, Ammar Ali <ammarabuali@gmail.com> wrote:

On Dec 19, 2013, at 5:30 AM, Matthew Kerwin <lists@ruby-forum.com> wrote:

I just have to say, this is quite a complicated little task you've set
yourself. I spent a couple of hours getting something[1] to even

Yes, this is a complicated problem. You can come close to a reasonable solution with brute force techniques (i.e many nested loops) but it will very likely be inefficient and quite limited. There are specialized algorithms for dealing with such problems, like n-gram and approximate string matching algorithms.

Regards,
Ammar

13

When iterating through pairs, if the str is "abcde", the "ab", "cd",
"e" will be allowed? (the "e" is a single letter).
The same above and "ab", "cde" will be allowed ? ("cde" is triple and
we began with a pair "ab").

Best regards,
Abinoam Jr.

Dear Abinoam,

You are correct in saying singles will not be allowed. For 'abcde' your
combinations will be ab, cde, or abc, de, and nothing else.

Regards

···

--
Posted via http://www.ruby-forum.com/\.

14

I think part of the problem is your requirements are contradictory, but here’s a first cut.

Henry

target = 'stringy'
test_words = ['estrange', 'gingerly', 'stop', 'geek', 'dry', 'rad', 'ear', 'wrinkle', 'cringy', 'guy', 'stringwingy']

target_sub_regexps = (2..target.length).collect {|l| target.split(//).each_cons(l).to_a}.flatten(1).collect{|s| s.join('.*')}

matches = test_words.collect do |word|
  [word, target_sub_regexps.collect do |sub_string|
    begin
      word.match(sub_string)[0]
    rescue
      nil
    end
  end.compact
  ]
end