ruby - Ruby 字谜求解器

Question

我想在 Ruby 中编写一个字谜类型求解器，但它会针对单词列表工作，就像这样。

单词列表是：

the
these
one
owner

我将允许用户输入一些字母，例如 noe，它会在单词列表中搜索它可以使用用户输入的字母并带回的单词one，如果他们输入了“eth”甚至“the”它会带回来the。我一直在想一种有效的方法来做到这一点，但我一直在循环每个单词，匹配单词中的一个字母，检查每个字母的单词并且两个长度都匹配。任何人都可以提供更好，更有效的方法来做到这一点的建议吗？

Answer 1

最大的想法是所有字谜在排序时都是相同的。因此，如果您构建列表的哈希（不知道 Ruby 怎么称呼这些），其中键是排序的单词，值是排序到给定键的单词列表，那么您可以通过排序快速找到字谜单词并在您的哈希中查找。

Answer 2

rrenaud 的回答很棒，下面是一个如何在 ruby​​ 中构造这样一个哈希的示例，给定一个名为 " words" 的数组，其中包含字典中的所有单词：

@words_hash = words.each_with_object(Hash.new []) do |word, hash|
  hash[word.chars.sort] += [word]
end

上面的代码假设 ruby​​ 1.9.2。如果您使用的是旧版本，chars则不存在，但您可以使用.split('').sort.

哈希的默认对象设置为空数组，这在某些情况下使编码更容易，因为您不必担心哈希会给您 nil。

来源：https ://github.com/DavidEGrayson/anagram/blob/master/david.rb

Answer 3

一种解决方案可能是：

def combine_anagrams(words)
  output_array = Array.new(0)
  words.each do |w1|
    temp_array = []
    words.each do |w2|
      if (w2.downcase.split(//).sort == w1.downcase.split(//).sort)
        temp_array.push(w2)
      end
    end
    output_array.push(temp_array)
  end
  return output_array.uniq
end

Answer 4

我忍不住要解决这个红宝石测验:)

class String

  def permutation(&block)
    arr = split(//)
    arr.permutation { |i| yield i.join }
  end
end


wordlist = ["one", "two"]

"noe".permutation do |i|
  puts "match found: #{i}" if wordlist.include?(i)
end

基本思想是它创建和排列并使用它的置换函数来得出结果。它可能效率不高，但我觉得它很优雅。:D

Answer 5

这可能是您正在寻找的内容：在 Ruby 中解决字谜

这是另一种方法（这是最高响应）：Anagram Solver In Python

Answer 6

这里和我的很相似。从字典文件中读取并将排序的字符作为数组进行比较。对预选的候选人进行排序。

def anagrams(n)
  text = File.open('dict.txt').read

  candidates = []
  text.each_line do |line|
    if (line.length - 1) == n.length
      candidates << line.gsub("\n",'')
    end
  end

  result = []

  candidates.each do |word|
    if word.chars.sort == n.chars.sort
      result << word
    end
  end

  result

end

Answer 7

def combine_anagrams(words)
  cp = 0
  hash = Hash.new []
  words.each do |word|
    cp += 1
    (cp..words.count).each do |i|
      hash[word.to_s.chars.sort.join] += [word]
    end
    hash[word.to_s.chars.sort.join] = hash[word.to_s.chars.sort.join].uniq
  end
  return hash
end