# Chaining Words Together

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.

• Will the words have hyphens? – Leaky Nun May 22 '16 at 6:41
• @LeakyNun Count hyphenated words as one word. I forgot to address "words" with symbols in them, however - I'll add a usage example for it. – M. I. Wright May 22 '16 at 6:45
• Could you define "word" in your challenge? – Leaky Nun May 22 '16 at 6:46
• Related: 1, 2, 3 – Sp3000 May 22 '16 at 6:48
• {Why do / Do} we need to use delimiters rather than input and/or output as arrays (ordered tuples)? – msh210 May 22 '16 at 7:10

# Pyth - 42 bytes

Complete brute force. Surprisingly fast, finishes all possible the test cases in seconds. Will run forever with impossible inputs.

Acczd]2.VZIJf.Amqhedehd,VTtTm++hGdeG^HbhJB

• Impoosible Is that like a mongoose? – Rɪᴋᴇʀ May 22 '16 at 18:50
• @EᴀsᴛᴇʀʟʏIʀᴋ :/ – Maltysen May 22 '16 at 18:54
• "Imøøsible" is the only valid choice here. – beaker May 23 '16 at 17:44

# Pyth, 51 48 bytes

FGITW.

=cQdMqeGhHL++hQb@Q1holN{+Fmf.AgVTtTyM+]Y._d.p>Q2


Test suite.