Given two words and a list as input, your program must (in as few characters as possible, of course) find the shortest way to "chain" the first word to the last using the ones in the list. Two words are "chained" if their first and last letters are the same, e.g. "Food" and "Door".
Your program will take input as a string with words separated by spaces, and output a list (in whatever format is most convenient: string, array/list type, etc) of the completed chain.
Examples:
Input: joke corn tan disc need eat
Output: joke eat tan need disc corn
The first two words in the input list are the first and last words in the chain, and the rest are the constituent words.
Input: best fry easy elf mean tame yam nice
Output: best tame elf fry
NOT: best tame easy yam mean nice elf fry
Input: rug gunned orange purple gains pore soup emo ending
Output: rug gunned
Input: %3gioxl? 6699-4 !f!!&+ ?4; ;78! +6
Output: %3gioxl? ?4; ;78! !f!!&+ +6 6699-4
The "words" don't have to be real words; for the purpose of the challenge, any ASCII character except the space will count as part of a word.
Input: mouth rich frame inspire item sold
Output when the first and last word are impossible to chain is undefined, so handle it however's shortest.
