Unscrambling a string given the number of splits and words that the sentence can be comprised of

Suppose the initial string

"hello my name is Sean"

with

splits = 2

yields

["hel", "lo my name ", "is Sean"]

and those three pieces are shuffled to form the following array:

["lo my name ", "hel", "is Sean"]

and then the elements of this array are joined to form:

scrambled = "lo my name helis Sean"

Also suppose:

dictionary = ["hello", "Sean", "the", "name", "of", "my", "cat", "is", "Sugar"]

First convert dictionary to a set to speed lookups.

require 'set'

dict_set = dictionary.to_set
  #=> #<Set: {"hello", "Sean", "the", "name", "of", "my", "cat", "is", "Sugar"}>

Next I will create a helper method.

def indices_to_ranges(indices, last_index)
  [-1, *indices, last_index].each_cons(2).map { |i,j| i+1..j }
end

Suppose we split scrambled twice (because splits #=> 2), specifically after the 'y' and the 'h':

indices = [scrambled.index('y'), scrambled.index('h')]
  #=> [4, 11]

The first element of indices will always be -1 and the last value will always be scrambled.size-1.

We may then use indices_to_ranges to convert these indices to ranges of indices of characters in scrambed:

ranges = indices_to_ranges(indices, scrambled.size-1)
  #=> [0..4, 5..11, 12..20]

a = ranges.map { |r| scrambled[r] }
  #=> ["lo my", " name h", "elis Sean"]

We could of course combine these two steps:

a = indices_to_ranges(indices, scrambled.size-1).map { |r| scrambled[r] }
  #=> ["lo my", " name h", "elis Sean"]

Next I will permute the values of a. For each permutation I will join the elements to form a string, then split the string on single spaces to form an array of words. If all of those words are in the dictionary we may claim success and are finished. Otherwise, a different array indices will be constructed and we try again, continuing until success is realized or all possible arrays indices have been considered. We can put all this in the following method.

def unscramble(scrambled, dict_set, splits)
  last_index = scrambled.size-1
  (0..scrambled.size-2).to_a.combination(splits).each do |indices|
    indices_to_ranges(indices, last_index).
    map { |r| scrambled[r] }.
    permutation.each do |arr|
      next if arr[0][0] == ' ' || arr[-1][-1] == ' '
      words = arr.join.split(' ')
      return words if words.all? { |word| dict_set.include?(word) }
    end
  end
end

Let's try it.

original string: "hello my name is Sean"
scrambled = "lo my name helis Sean"
splits = 4

unscramble(scrambled, dict_set, splits)
  #=> ["my", "name", "hello", "is", "Sean"]

See Array#combination and Array#permutation.

bonkers answer (not quite perfect yet ... trouble with single chars):

#
# spaces appear to be important!

@check = {}
@ordered = []

def previous_words (word)
  @check.select{|y,z| z[:previous] == word}.map do |nw,z|
    @ordered << nw
    previous_words(nw)
  end
end

def in_word(dictionary, string)
  # check each word in the dictionary to see if the string is container in one of them
  dictionary.each do |word|
    if word.include?(string)
      return word
    end
  end
  return nil
end

letters=scrambled.split("")
previous=nil
substr=""

letters.each do |l|
  if in_word(dictionary, substr+l)
    substr+= l
  elsif (l==" ")
    word=in_word(dictionary, substr)
    @check[word]={found: 1}
    @check[word][:previous] = previous if previous
    substr=""
    previous=word
  else
    word=in_word(dictionary, substr)
    @check[word]={found: 1}
    @check[word][:previous] = previous if previous
    substr=l
    previous=nil
  end
end
word=in_word(dictionary, substr)
@check[word]={found: 1}
@check[word][:previous] = previous if previous

@check.select{|y,z| z[:previous].nil?}.map do |w,z|
  @ordered << w
  previous_words(w)
end

pp @ordered

output:

dictionary = ["world", "hello"]
scrambled = "rldhello wo"

... my code here ...

2.5.8 :817 > @ordered
 => ["hello", "world"] 

dictionary = ["hello", "my", "name", "is", "Sean"]
scrambled = "me is Shelleano my na"

... my code here ...

2.5.8 :879 > @ordered
 => ["Sean", "hello", "my", "name", "is"]