Iterating a string through an array, need help?

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:

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

Joel P. 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?

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”]

  1. 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”]

  1. 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 19/12/2013, at 8:13 am, Jim W. [email protected] wrote:

  1. 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’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?

On 19/12/2013, at 4:13 pm, Jim W. [email protected] wrote:

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

Array#uniq

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

Array#length

Show us what you have so far

Henry

Henry M. wrote in post #1131042:

On 19/12/2013, at 8:13 am, Jim W. [email protected] wrote:

  1. 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).

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]
https://github.com/phluid61/ruby-experiments/blob/master/substring_puzzle/substrings.rb

On Dec 19, 2013, at 5:30 AM, Matthew K. [email protected]
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

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

Dear Jim W.,

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.

I think part of the problem is your requirements are contradictory, but
heres 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

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs