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.


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.

  • \$\begingroup\$ Will the words have hyphens? \$\endgroup\$
    – Leaky Nun
    May 22 '16 at 6:41
  • \$\begingroup\$ @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. \$\endgroup\$
    – hallo
    May 22 '16 at 6:45
  • \$\begingroup\$ Could you define "word" in your challenge? \$\endgroup\$
    – Leaky Nun
    May 22 '16 at 6:46
  • \$\begingroup\$ Related: 1, 2, 3 \$\endgroup\$
    – Sp3000
    May 22 '16 at 6:48
  • 2
    \$\begingroup\$ {Why do / Do} we need to use delimiters rather than input and/or output as arrays (ordered tuples)? \$\endgroup\$
    – msh210
    May 22 '16 at 7:10

Pyth, 51 48 bytes



Test suite.


Pyth - 42 bytes

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


Test Suite.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.