Causes Puzzle

causes.rb

require 'text'

def compute_friends(word, words)
  words.reject{|potential_friend| Text::Levenshtein.distance(word, potential_friend) > 1}
end

def naive_word_social_network(word, non_friend_words)
  last_social_network_step = []
  new_friends = [word]
  current_social_network_step = [word]
  i = 0
  while last_social_network_step.size != current_social_network_step.size
    last_social_network_step = current_social_network_step.clone
    last_new_friends = new_friends
    new_friends = []
    last_new_friends.each do |word|
      friends = compute_friends(word, non_friend_words)
      non_friend_words -= friends
      current_social_network_step += friends
      new_friends += friends
    end
    i += 1
    puts "iteration #{i}, non friends #{non_friend_words.size}, social network #{current_social_network_step.size}"
  end
  current_social_network_step
end

#TODO: maybe optimize by pre computing along the way the friends groups

non_friend_words = []
word_file = File.new("word.list", "r")
word_file.each_line do |word|
  non_friend_words << word
end
naive_word_social_network("causes", non_friend_words).size