A word ladder game solver.

word_ladder.cr

wordlist = Set{"cat", "cot", "cog", "dog", "dat", "bat", "bar"}
from = "cat"
to = "dog"

path_map ={"dog" => "cog", "cog" => "cot", "cot" => "cat"}

def get_neighbors(word : String, dictionary : Set(String)) : Set(String)
  az = 'a'..'z'
  neighbors = Set(String).new
  word.size.times do |i|
    original_char = word[i]
    az.each do |char|
      next if char == original_char
      candidate = word[0...i] + char + word[(i + 1)..]
      if dictionary.includes? candidate
        neighbors.add candidate
      end
    end
  end
  neighbors
end

puts "get_neighbors wrong" if get_neighbors(from, Set{"cat", "cot", "cog", "dog", "dat", "bat", "bar"}) != Set{"bat", "dat", "cot"}

def build_path(from_word : String, to_word : String, path_map : Hash(String, String)) : Array(String)
  path = [to_word]
  current = to_word
  while current != from_word && (parent = path_map.fetch(current, nil))
    path << parent
    current = parent
  end

  path.reverse
end

puts "build_path wrong" if build_path(from, to, path_map) != ["cat", "cot", "cog", "dog"]

def run(from, to, dictionary) : Array(String)?
  q = Deque(String).new
  visited = Set(String).new
  parent = Hash(String, String).new

  q.push(from)
  visited.add(from)
  while ! q.empty?
    current = q.shift()
    if current == to
      return build_path(from, to, parent)
    end
    neighbors = get_neighbors(current, dictionary)

    neighbors.each do | neighbor |
      if ! visited.includes? neighbor
        visited.add(neighbor)
        parent[neighbor] = current
        q.push(neighbor)
      end
    end
  end
  nil
end

puts "build_path wrong" if run(from, to, wordlist) != ["cat", "cot", "cog", "dog"]

if ARGV.size < 2
  STDERR.puts "Need 2 arguments. e.g. 'cat dog'"
  exit 1
end

if ARGV.size == 3
  if File.exists? ARGV[2]
    STDOUT.puts "Use user dict"
    dict_path = ARGV[2]
  else
    STDERR.puts "Can't find the user's dictionary, use default Merriam-Webster"
    dict_path = "mw_dict.txt"
  end
else
  dict_path = "mw_dict.txt"
end

begin
  dict = File.read_lines(dict_path).to_set
rescue ex
  STDERR.puts "Can't load dict: #{ex}"
  exit 1
end
STDOUT.puts run(ARGV[0], ARGV[1], dict)

# Usage:
# crystal word_ladder.cr cat dog
# crystal word_ladder.cr cat dog my_dict.txt