ruby to unjumble words [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

I am trying to write a ruby script that unscrambles permuted words, generates all the permutations, and searches for the word in a txt directory. I'm running into problems.

This is a simple outline of what I have.

print "Enter Permuted Word:"
words = STDIN.gets.chomp


a = to_array(s)
print a, "\n"


perms = a.permutation(3).to_a.collect do |perm|
perm.join
end
print perms, "\n"

file = file.open("words.txt", "r")
file.read.each_line do |line|
fields = line.chomp.split(",")
words_un = fields[1]
end
file.close

the txt file looks something like this

words_un
Aarhus
Aaron
Ababa
aback
abaft
abandon
abandoned
abandoning
abandonment
abandons
abase
...
Zulus
Zurich

Answer 1

Suppose dict is an array of strings that your dictionary and scrambled is a scrambled word (a string). Considering all permutations of scrambled or (far worse) the elements of dist would be highly inefficient. Suppose, for example, the first two letters of one scrambled permutation were qz. If there were no element (word) in dict that begins qz, there would be no point in considering any of the permutations of scrambled that begin qz.

Data Structures

Suppose this were our dictionary.

dict = ["dog", "cat", "cow", "emu", "cod", "cobra"]

If we just want to see if a few scrambled words were in the dictionary, we could do this for each:

   r = 'mue'.split('').permutation(3).find { |w| dict.include?(w.join) }     
     #=> ["e", "m", "u"]
   r.any? ? r.join('') : nil
     #=> "emu"

   r = 'nvwls'.split('').permutation(3).find { |w| dict.include?(w.join) }     
     #=> nil

The more interesting question is how to do this in a more efficient way, for checking large numbers of posssilby-longish words that have many permutations.

The first step is to reorganize the dictionary to make lookups for efficient. I am not the best person to suggest how that be done, as I am not familiar with that (or any other) branch of computer science. Here is one way, using a multi-level hash:

dh = { "c"=>{ "a"=>{ "t"=>nil },
              "o"=>{ "b"=>{ "r"=>{ "a"=>nil } }, "w"=>nil, "d"=>nil } },
       "d"=>{ "o"=>{ "g"=>nil } },
       "e"=>{ "m"=>{ "u"=>nil } } }  

dh["c"] "contains" all words that begin with "c"; dh["c"]["a"] contains all words that begin with "ca", and so on. dh["c"]["a"]["t"] => nil signifies that dh["c"]["a"]["t"].join('') => 'cat' is one of the words in the dictionary. I will assume that you have dh. If you would like suggestions on how to construct dh from dict, perhaps you could ask that as a separate question.

Code

Here is a (recursive) method that could be used to see if any of the unscramblings of scrambled are contained in dict. (It would not be difficult to modify this to compile a list of all permutations that are found in dict, but that is not the problem I've addressed.) This method is called with look_up(dh, scrambled).

def look_up(dh, left, used = '')
  left.size.times do |i|
    left_copy = left.dup
    e = left_copy[i]
    left_copy[i] = ''
    v = dh[e]
    case v
    when nil
      (return used + e) if left_copy.empty?
    when Hash
      word = look_up(v, left_copy, used + e)
      return word if word
    end
  end
  nil
end

Example

look_up(dh, "owc")         #=> "cow"
look_up(dh, "mue")         #=> "emu"
look_up(dh, "bocar")       #=> "cobra"
look_up(dh, "esuomhcruhc") #=> nil

Explanation

Suppose dh is as above and scrambled => "owc". Then

left = "owc"
used = ''

left.size              #=> 3
enum = left.size.times #=> #<Enumerator: 3:times>

We can convert enum to an array to see what it will be passing to its block:

enum.to_a              #=> [0, 1, 2]

Initially, the block variable i is set to 0 and

left_copy = left.dup  #=> "owc"
e = left_copy[i]      #=> left_copy[0] => "o"
left_copy[i] = ''     #left_copy[i] = '' 
left_copy             #=> "wc"
v = dh[e]             #=> v = dh[0] => nil

dh[0] => nil, combined with left_copy.empty? => false, means there are no words in the dictionary beginning with 'o', so we return to the top of the loop and set i => 1 and consider words beginning with 'o':

left_copy = left.dup  #=> "owc"
e = left_copy[i]      #=> left_copy[1] => "w"
left_copy[i] = ''     #=> left_copy[1] = ''
left_copy             #=> "oc"
v = dh[e]             #=> v = dh[1] => nil

There are no words in the dictionary beginning with 'w', so we loop again with i => 2,

searching for words in the dictionary beginning with `'c'`:

e = left_copy[2]      #=> "c"
left_copy[2] = ''     #=> left_copy[2] = ''
left_copy             #=> "ow"
v = dh[2]             #=> {"a"=>{"t"=>nil},
                      #    "o"=>{"b"=>{"r"=>{"a"=>nil}}, "w"=>nil, "d"=>nil}}

This shows that there are words in the dictionary beginning 'ca`` and'co'`.

As v is a hash, we call the method recursively

word = look_up(v, left_copy, used + e)
  #    look_up({"a"=>{"t"=>nil},
  #             "o"=>{"b"=>{"r"=>{"a"=>nil}}, "w"=>nil, "d"=>nil}},
  #             "ow",
  #             "c")

Calculations proceed similarly for additional letters. When it is found that there are words in the dictionary for the string "co" represented by:

{ "b"=>{ "r"=>{ "a"=>nil } }, "w"=>nil, "d"=>nil }

we conclude that, since this hash contains "w"=>nil, that "cow" is in the dictionary, so we return 'cow' up the recursive chain and are finished.