Problem 45463. Word Ladder

Created by Asif Newaz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given a set of words, and two other words - start and destination,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Find the smallest chain from start to the destination such that adjacent words in the chain only differ by one character and each word in the chain exists in the set.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>All the words are of the same length. The starting word is not in the set but destination word would be.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Start = 'COLD'\n Destination = 'WARM'\n set ={ CORD CARD DART FORT WARM FARM WARD}\n\n COLD → CORD → CARD → WARD → WARM]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

31 Solutions
5 Solvers

Last Solution submitted on Nov 29, 2022

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Murat Yildirim on 13 Apr 2022

Hi Asif Newaz,

thx for the problem. I enjoyed to solve it. But in the task i found a missing information. Second Test case provides in the set follwing words 'can','fan','pat'.

In the second iteration when function found pan, all three cases match and i do not see any rule in the description, why it has to be pat. When i follow in the Test Cases the solution, it seems words which differ a single character only at the end of the pattern will get preferred. For my understanding, the current description is not limiting any solution when multiple Hits are detected.

Maybe add an additional requirement, clarifying the rank of matches.

Thx :-).

Rafael S.T. Vieira on 29 Nov 2022

Multiple solutions may exist for this problem, but the test suite only considers one correct. For instance, in test #2, y = {'mat' 'pat' 'put' 'aut' 'apt' 'ape'}; is a valid path from the word man to the word ape. This means we must use words in the order we find them as a priority queue.

Problem Recent Solvers5

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 45463. Word Ladder

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Problem 45463. Word Ladder

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Players