HackThisSite 编程挑战 1 算法（解扰）

最近有人向我推荐了 hackthissite.org — 玩起来真的很有趣，即使我认为一些挑战不再那么现实。

我认为在这里发布一些我对编程挑战的解决方案同样有趣。如果不是理解底层算法绝对必要，我不会发布任何关于如何使用程序的信息，因为这些文章的目的是理解它，而不是为了解决 HTS 挑战而使用它。

我对挑战 1（解扰）的解决方案基于这样的观察：如果解扰的字符串是唯一的，包含要解扰字符串的排序字符的字符串也是唯一的。

我能想到的最新手的解决方案是对于每个要解扰的字符串遍历单词列表，检查要解扰字符串中的所有字符是否也存在于原始字符串中（当然长度也要相等）。

为了更高效地做到这一点（我的算法是 $\mathcal{O}(n)$ 索引和理论上 $\mathcal{O}(log\ n)$ 查找），我们可以将字符排序的表示保存在关联数据结构中。对此数据结构排序后，我们可以使用二分查找来找到单词的解扰版本。

为了查找，我们只需计算要解扰字符串的字符排序版本并返回它。

这是我在 Ruby 中的实现：

data = Hash.new # 键 = 字符串的排序字符
#读取单词列表并排序字符
File.open('wordlist.txt').each do |line|
 line.strip!
 sorted = line.chars.sort.join
 data [sorted] = line
end
#读取要解扰的单词
#输出扰码单词的逗号分隔列表
File.open('words.txt').each do |line|
 line.strip!
 print data[line.chars.sort.join]+","
end
#打印最终换行以使复制粘贴更快
print "\n"

脚本在你需要粘贴到 HTS 网站的行末打印一个额外的逗号，但这不应该是个问题。

我从此 Stackoverflow 帖子找到了字符排序的 ruby 实现。