Problem 787. Path Optimization thru N words : Time Optimization

Created by Richard Zapor

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>This is an extension of</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/196-love-is-an-n-letter-word\"><w:r><w:t>Cody 196 love</w:t></w:r></w:hyperlink><w:r><w:t> with a more stressing test set and scoring based upon time.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Greater than 10 words induces time issues with brute force combinatorics.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Description is copy of Alfonso Nieto-Castanon's problem statement for Cody 196.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given a list of N words, return the N-letter word (choosing one letter from each word) with the property of having the least distance between each pair of two consecutive letters (if there are multiple optimal solutions return any one of them). Letters may repeat inside words.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example: s1 = {'abcd','bcde','cdef','defg'}; should return s2 = 'dddd'; (with total letter-distance = 0)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example: s1={'aldfejk','czoa','vwy','abcde'}; should return s2='love'; (with total letter-distance = 27: 'l'-'o'=3 + 'o'-'v'=7 + 'v'-'e'=17 ; compare for example to the possible word 'aave' which has a total letter-distance of 38)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Passing:</w:t></w:r><w:r><w:t> All problems correct and time &lt; 2 seconds</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output chart:</w:t></w:r><w:r><w:t> Time in milliseconds with a max of 100 ms.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: Did consider logarithmic scale but keeping it simple for now.</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>"}]}

This is an extension of <a href="http://www.mathworks.com/matlabcentral/cody/problems/196-love-is-an-n-letter-word">Cody 196 love</a> with a more stressing test set and scoring based upon time.Greater than 10 words induces time issues with brute force combinatorics.Description is copy of Alfonso Nieto-Castanon's problem statement for Cody 196.Given a list of N words, return the N-letter word (choosing one letter from each word) with the property of having the least distance between each pair of two consecutive letters (if there are multiple optimal solutions return any one of them). Letters may repeat inside words.Example: s1 = {'abcd','bcde','cdef','defg'}; should return s2 = 'dddd'; (with total letter-distance = 0)Example: s1={'aldfejk','czoa','vwy','abcde'}; should return s2='love'; (with total letter-distance = 27: 'l'-'o'=3 + 'o'-'v'=7 + 'v'-'e'=17 ; compare for example to the possible word 'aave' which has a total letter-distance of 38)Passing: All problems correct and time &lt; 2 secondsOutput chart: Time in milliseconds with a max of 100 ms.Note: Did consider logarithmic scale but keeping it simple for now.

This is an extension of
<http://www.mathworks.com/matlabcentral/cody/problems/196-love-is-an-n-letter-word Cody 196 love> with a more stressing test set and scoring based upon time.

Greater than 10 words induces time issues with brute force combinatorics.

Description is copy of Alfonso Nieto-Castanon's problem statement for Cody 196.

Given a list of N words, return the N-letter word (choosing one letter from each word) with the property of having the least distance between each pair of two consecutive letters (if there are multiple optimal solutions return any one of them). Letters may repeat inside words.

Example: s1 = {'abcd','bcde','cdef','defg'}; should return s2 = 'dddd'; (with total letter-distance = 0)

Example: s1={'aldfejk','czoa','vwy','abcde'}; should return s2='love'; (with total letter-distance = 27: 'l'-'o'=3 + 'o'-'v'=7 + 'v'-'e'=17 ; compare for example to the possible word 'aave' which has a total letter-distance of 38)

*Passing:* All problems correct and time < 2 seconds

*Output chart:* Time in milliseconds with a max of 100 ms.

Note: Did consider logarithmic scale but keeping it simple for now.

Solve

Solution Stats

30 Solutions
8 Solvers

Last Solution submitted on Jun 09, 2019

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

William on 9 Jun 2019

I think test suite problem 11 has more correct solutions than are tested for.

Problem Recent Solvers8

Problem Tags

Community Treasure Hunt

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

Start Hunting!