-4

I am looking for a algorithm for below riddle:

Write a program that transforms the word "cat" into "dog" by changing 1 character at a time, and while doing that, all the interim words that are generated are also valid words. You are given a method, which tells you whether a word is valid or not when you pass the word as an input to it.

Any Idea?

Abhinav
  • 37,684
  • 43
  • 191
  • 309
  • 2
    Have you made an attempt at it? You won't get any help until you show us what you've tried. – Dylan Lawrence Nov 20 '13 at 00:07
  • 1
    Thank you for posting your requirements. Now please post your attempt... – Mitch Wheat Nov 20 '13 at 00:07
  • cat->cot->cog->dog There may be several other paths available but this is a minimal shortest path. – Shashank Nov 20 '13 at 00:08
  • Duplicate: http://stackoverflow.com/questions/1521958/shortest-path-to-transform-one-word-into-another – FogleBird Nov 20 '13 at 00:10
  • Yes you can use an open source spellchecker library like hunspell, GNU Aspell etc. as validator. Depending also in what Language you are planing to work. http://en.wikipedia.org/wiki/Hunspell Then, the riddle tells you to change one caracter at a time. So you need to get one character from dog to cat (lets naively start with d->c), trying to validate, if the word exists, go on, if not use the next character. If even the third does not work, you need to go back and undo the last change. und till you are done, or exit with failiure if the riddle isn't solveable. Good Luck! – Marcel Blanck Nov 20 '13 at 00:16

1 Answers1

4

This is a graph search problem. The nodes are valid words, the starting point is "cat", and the ending point is "dog". To find the neighbors of a node, you can try all possible 1-letter changes and check whether they produce valid words. You can apply any standard search algorithm to the problem; I recommend depth-first search or breadth-first search.

If the program only has to work for "cat" and "dog", you could also just hardcode the answer. As Shashank provided in the comments,

return ['cat', 'cot', 'cog', 'dog']

might be all you need.

user2357112
  • 260,549
  • 28
  • 431
  • 505