## Mar 14, 2010

### A Scenario to Ponder #16

During my school days, I used to play this game that I would call as "word mutation". The problem statement gives the starting and ending 4-letter words.

The game is to find the path from the starting to the ending word by changing one alphabet at a time and ,of course, each of the words in the path should be a valid word.

Given below is one example:

Start: WORD
End : COME

One solution is
WORD
WORE
CORE
COME

So, here is the SQL puzzle. Given the starting and ending 4-letter words, Can you write a query to find the shortest path, between these two words. If you have multiple shortest paths, just show one.

You need to have a table of words and you can build it using the list available here:
http://www.sil.org/linguistics/wordlists/english/wordlist/wordsEn.txt

Happy Querying!!!

Given below is my take at solving this puzzle. Not very proud of the solution. I feel I could have as well written it in C#.
All you SQL gurus... I am really looking forward to a see a better looking/performing solution.

``````/*
I created a view VW_WORD that will only
select 4 letter words from the Words table.
I am using that as my Word Dictionary for
this solution.
*/

SET NOCOUNT ON;

DECLARE        @StartWord        CHAR(4);
DECLARE        @EndWord        CHAR(4);

SET            @StartWord        = 'WORD';
SET            @EndWord        = 'COME';

DECLARE @WordsTable as TABLE
(
Word                char(4),
WordsBranch            varchar(max),
Closeness            tinyint,
IterationCounter    int
)

DECLARE    @IterationCounter        int;
SET        @IterationCounter        = 1;

;WITH Positions AS
(
SELECT 1 AS Pos
UNION ALL
SELECT 2
UNION ALL
SELECT 3
UNION ALL
SELECT 4
)
INSERT INTO @WordsTable (Word, WordsBranch, Closeness, IterationCounter)
SELECT
UPPER(Word),
CAST(UPPER(@StartWord) + '-->' + UPPER(Word) AS VARCHAR(MAX)) AS WordsBranch,
(SELECT COUNT(*) FROM Positions WHERE SUBSTRING(Word, Pos,1) = SUBSTRING(@EndWord,Pos,1)) as Closeness,
@IterationCounter as IterationCounter
FROM
VW_WORD
WHERE
DIFFERENCE(Word,@StartWord) >= 3
AND     (SELECT COUNT(*) FROM Positions WHERE SUBSTRING(Word, Pos,1) = SUBSTRING(@StartWord,Pos,1)) >= 3
AND    (SELECT COUNT(*) FROM Positions WHERE SUBSTRING(Word, Pos,1) = SUBSTRING(@EndWord,Pos,1)) >= 1

DELETE FROM @WordsTable WHERE Closeness <> (SELECT MAX(Closeness) FROM @WordsTable)

WHILE NOT EXISTS (SELECT 1 FROM @WordsTable WHERE Word = @EndWord)
BEGIN
SET @IterationCounter = @IterationCounter + 1

IF(@IterationCounter = 10)
BREAK; /* No solution Found */

;WITH Positions AS
(
SELECT 1 AS Pos
UNION ALL
SELECT 2
UNION ALL
SELECT 3
UNION ALL
SELECT 4
)
INSERT INTO @WordsTable (Word, WordsBranch, Closeness, IterationCounter)
SELECT
UPPER(A.Word),
WordsBranch + '-->' + UPPER(A.Word) AS WordsBranch,
(SELECT COUNT(*) FROM Positions WHERE SUBSTRING(A.Word, Pos,1) = SUBSTRING(@EndWord,Pos,1)),
@IterationCounter as IterationCounter
FROM
VW_WORD AS A,
(SELECT * FROM @WordsTable WHERE IterationCounter = @IterationCounter - 1) AS B
WHERE
DIFFERENCE(A.Word,B.Word) >= 3
AND    (SELECT COUNT(*) FROM Positions WHERE SUBSTRING(A.Word, Pos,1) = SUBSTRING(B.Word,Pos,1)) = 3
AND    (SELECT COUNT(*) FROM Positions WHERE SUBSTRING(A.Word, Pos,1) = SUBSTRING(@EndWord,Pos,1)) >= B.Closeness
AND    NOT EXISTS (SELECT 1 FROM @WordsTable C where C.Word = A.Word)

DELETE FROM @WordsTable WHERE IterationCounter < @IterationCounter - 1
END

IF EXISTS(SELECT 1 FROM @WordsTable WHERE Closeness = 4)
SELECT WordsBranch FROM @WordsTable WHERE Closeness = 4
ELSE
PRINT 'No solution found'

``````