My take on Trustpilot's rabbithole

neo.rb

#!/usr/bin/env ruby

require 'digest'

phrase = 'poultryoutwitsants'
checksum = '4624d200580677270a54ccff86b9610e'

words = File.open('words', 'r').each_line
  .map(&:chomp).uniq # Discard line-endings & duplicates

# At this point there are ~100k entries. Since we only want a subset of three
# (assuming the resulting phrase has as many words as its anagram) we're looking
# at a complexity of O(n! / (n - 3)!), which leaves 10^15 permutations with the
# current set (too many)

# Next we remove all words that cannot be built using the letters present in the
# input set.
words = words 
  .select do |word|
    word.chars.all? { |char| word.count(char) <= phrase.count(char) }
  end

# This brings the set down to ~1700 entries which is more reasonable.

# Next we can start testing some anagrams:
words.combination(3) do |cmb|

  # Can't be anagrams if the lenghts don't match
  next unless cmb.join.length == phrase.length

  # In order to test if a given combination is an anagram to the given phrase we
  # check if all the same chars are present in both phrases. The order is
  # irrelevant, which brings the complexity down to O(n! / (r! (n - r)!)), or in
  # this instance somewhere around 8*10^8 combinations.
  next unless cmb.join.chars.sort.join == phrase.chars.sort.join

  # Now that we've established that the combination is an anagram we need to
  # check if one of the 3! permutations match the desired checksum:
  result = cmb.permutation
              .detect { |perm| Digest::MD5.hexdigest(perm.join(' ')) == checksum }

  if result
    puts "Found \"#{result.join(' ')}\""
    break
  end
end