Problem 787. Path Optimization thru N words : Time Optimization
This is an extension of 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.
Solution Stats
Problem Comments
-
1 Comment
I think test suite problem 11 has more correct solutions than are tested for.
Solution Comments
Show commentsProblem Recent Solvers8
Suggested Problems
-
Check to see if a Sudoku Puzzle is Solved
320 Solvers
-
Project Euler: Problem 8, Find largest product in a large string of numbers
1082 Solvers
-
Matrix indexing with two vectors of indices
717 Solvers
-
54 Solvers
-
Compute the dilation of a binary image
50 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!