Jump to content

The ultimate community for Ruby on Rails developers.


Photo

Tricky Ruby question, array of arrays and fibonacci

ruby

  • Please log in to reply
4 replies to this topic

#1 j.whittaker

j.whittaker

    Passenger

  • Members
  • 5 posts

Posted 21 December 2013 - 04:30 PM

I am trying to make an array of all different combinations of a string. The minimum amount of chars in the output string must be two.

    # Example string.  What if string is n chars long though?
    s = "string"

    s.flatten.select {|a| p a}

Expected output:

    [['st', 'ring',],['str', 'ing'],['stri', 'ng']['string'], ['st', 'ri', 'ng']]

I only need the consecutive forward groups of chars output. Each subarray should contain all the letters of `s` broken in different ways. I don't need `['gnirts']`, `['gn', irts']`, or something mixed up like `['stngri']`. When it's over seven chars, it is tricky. Here's a map of the different combinations, assuming the string `s` is a minimum length of two:

    For a 2-letter string: ['first 2 letters']
    3-letter string: ['first 3 letters']
    4-letter string: [['first 2', 'third and fourth'], ['first four']]
    5-letter string: [['first 2, 'thrid fourth and fifth'],['first 3, fourth and fifth'],['all five']]

    and etc.

I'm wondering if what I'm asking is possible.

There is a Fibonacci sequence in here.  There is only 1 solution for 2 or 3- letter strings.  2 solutions for 4-char.  3 for 5-char.  5 for 6-char, and 8 for 7-char.



#2 Ohm

Ohm

    Guard

  • Members
  • 184 posts
  • LocationCopenhagen

Posted 21 December 2013 - 06:01 PM

Just to clarify, I've written out the examples as I understand them. Say we have a method fibstring which does this. The result of each call is written as a comment in the section below

fibstring("ST") # => [["ST"]]

fibstring("STR") # => [["STR"]]

fibstring("STRI") # => [["ST", "RI"], ["STRI"]]

fibstring("STRIN") # => [["ST", "RIN"], ["STR", "IN"], ["STRIN"]]

fibstring("STRING") # => [["ST", "RI", "NG"], ["ST", "RING"], ["STR", "ING"], ["STRI", "NG"], ["STRING"]]

fibstring("STRINGS") # => [["ST", "RI", "NGS"], ["ST", "RIN", "GS"], ["ST", "RINGS"], ["STR", "IN", "GS"], ["STR", "INGS"], ["STRI", "NGS"], ["STRIN", "GS"], ["STRINGS"]]

When we look at the results, it's very clear that its a recursive method. We take the first 2 characters of the string, and then apply fibstring to the rest. Then we take the first 3 characters and apply fibstring to the rest. Then we take the first 4... up until the length of the string minus 2. If we get a string of length 2 we return it.

 

It should be fairly easy to construct this recursive method. My solution is as follows

def fibstring(s)
  result = [s]
  return result if s.length <= 2

  arr = s.split(//)
  (2..arr.size-2).each do |i|
    res = fibstring(arr[i..-1].join)

    res.each do |str|
      str = str.join if str.is_a?(Array)
      result << [arr[0..i-1].join, str]
    end
  end

  result
end

p fibstring("ST")      # => ["ST"]
p fibstring("STR")     # => ["STR"]
p fibstring("STRI")    # => ["STRI", ["ST", "RI"]]
p fibstring("STRIN")   # => ["STRIN", ["ST", "RIN"], ["STR", "IN"]]
p fibstring("STRING")  # => ["STRING", ["ST", "RING"], ["ST", "RING"], ["STR", "ING"], ["STRI", "NG"]]
p fibstring("STRINGS") # => ["STRINGS", ["ST", "RINGS"], ["ST", "RINGS"], ["ST", "RINGS"], ["STR", "INGS"], ["STR", "INGS"], ["STRI", "NGS"], ["STRIN", "GS"]]

It could probably be written a bit better or clearly, but I'm too lazy right now.  :blink:


  • james likes this

Blog: http://ohm.sh | Twitter: madsohm


#3 Ohm

Ohm

    Guard

  • Members
  • 184 posts
  • LocationCopenhagen

Posted 21 December 2013 - 06:04 PM

As j.whittaker writes, we can find the Fibonacci numbers from this method. Lets create a fib method

def fib(n)
  fibstring("A"*n).length
end

Calling it with 1 will yield fibstring("A") which has one solution. Calling it with 7 will yield fibstring("AAAAAAA"), which have got 8 solutions.

p fib(1) # => 1
p fib(2) # => 1
p fib(3) # => 1
p fib(4) # => 2
p fib(5) # => 3
p fib(6) # => 5
p fib(7) # => 8

Blog: http://ohm.sh | Twitter: madsohm


#4 j.whittaker

j.whittaker

    Passenger

  • Members
  • 5 posts

Posted 22 December 2013 - 07:58 PM

Hey, nice job with this method.  However it has a bug.  As you noted, I am looking for ["ST", "RI", "NG"] to show up in the case of s = 'string'.  But your method does not account for this combination.

 

Also, you have some duplicates. "st", "ring" repeated twice for instance.  By my calculations, 'string', as a 6-letter word, should have 5 unique solutions.  As you wrote in your post:

 

fibstring("STRING") # => [["ST", "RI", "NG"], ["ST", "RING"], ["STR", "ING"], ["STRI", "NG"], ["STRING"]]

 

 

Thanks for the help, and I'm wondering if there is an easy way to modify this method to incorporate the missing string combo's.



#5 Ohm

Ohm

    Guard

  • Members
  • 184 posts
  • LocationCopenhagen

Posted 22 December 2013 - 08:08 PM

I said it was a lazy solution  ;)

 

This solution will yield the correct 

fibstring("STRING").include?(["ST", "RI", "NG"]) # => true
def fibstring(s)
  result = [s]
  return result if s.length <= 2

  arr = s.split(//)
  (2..arr.size-2).each do |i|
    res = fibstring(arr[i..-1].join)

    res.each do |str|
      result << [arr[0..i-1].join, str].flatten
    end
  end

  result
end

This is an even better solution, which actually grants each solution in a separate array

def fibstring(s)
  result = [[s]]
  return result if s.length <= 2

  arr = s.split('')

  (2..arr.size-2).each do |i|
    rest = arr.drop(i).join
    sub_results = fibstring(rest)

    sub_results.each do |sub|
      result << [arr.take(i).join, sub].flatten
    end
  end

  result
end

p fibstring("STRING") # => [["STRING"], ["ST", "RING"], ["ST", "RI", "NG"], ["STR", "ING"], ["STRI", "NG"]]

Blog: http://ohm.sh | Twitter: madsohm






Also tagged with one or more of these keywords: ruby

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users