Two ambassadors at a UN conference want to speak to each other, but unfortunately each one only speaks one language- and they're not the same language. Fortunately, they have access to several translators, who each understand and speak a few languages. Your task is to determine the shortest chain of translators (since you want as little to be lost in translation as possible) that allows the two ambassadors to speak with each other.


Input: two languages as 2-letter lowercase strings (each ambassador's language) and a list of lists of languages (one list per available translator)

You may alternatively take in integers instead of 2-letter codes.

Output: A sequence of translators either by index or value that is any one of the shortest chains of translators that allows the two ambassadors to communicate. If there is no valid chain of translators, the behavior is undefined. (You may crash, output any arbitrary value, or indicate an error)

A valid chain of translators is one where the first translator speaks one ambassador's language, the second and subsequent translators share at least one language with the previous translator, and the last translator speaks the other ambassador's language.


Using zero-based indexing:

es, en, [
    [es, en]
] ==> [0]

en, en, [] ==> []

en, jp, [
    [en, zh, ko, de],
    [jp, ko]
] ==> [0, 1]

es, ru, [
    [gu, en, py],
    [po, py, ru],
    [po, es]
] ==> [2, 1]

fr, gu, [
    [it, fr, de, es, po, jp],
    [en, ru, zh, ko],
    [jp, th, en],
    [th, gu]
] ==> [0, 2, 3]

fr, ru, [
    [fr, en],
    [en, ko, jp],
    [en, ru]
] ==> [0, 2]

de, jp, [
    [en, fr],
    [ko, jp, zh],
    [fr, po],
    [es, ko, zh],
    [de, en, th],
    [en, es],
    [de, fr]
] ==> [4, 5, 3, 1]

Rules and Assumptions

  • Standard IO rules (use any convenient I/O format) and banned loopholes apply.
  • You may assume that speaking and understanding languages is perfectly symmetric and that all possible translations between languages are equally efficient.
  • There is no concept of "close enough" languages. It is not good enough to use Portuguese on one end where Spanish is required, for instance.
  • If there are multiple shortest translator chains, any one of them will do.
  • If the ambassadors happen to speak the same language, the translator list should be empty
  • Which of the ambassadors is the first one doesn't matter; the translator list can be forward or reverse.
  • Ambassadors only speak one language for the sake of this challenge
  • Translators speak at least two languages
  • The 2-letter language codes do not need to correspond with real languages
  • You may assume there is a valid sequence of translators
  • If outputting the sequence by value, include the full set of available languages, not just the relevant ones.

Happy Golfing!

  • 2
    \$\begingroup\$ Why the I/O restriction to two-character strings, wouldn't integers do just as well? \$\endgroup\$ May 13, 2019 at 18:47
  • \$\begingroup\$ can the list of list of translators be in csv form like: en,fr,sp;en,gr;gr,fr \$\endgroup\$
    – Quinn
    May 13, 2019 at 19:49
  • \$\begingroup\$ @Quinn standard IO rules say yes. \$\endgroup\$
    – Beefster
    May 13, 2019 at 20:13
  • \$\begingroup\$ Can the ambassadors be included in the output at the beginning and end? \$\endgroup\$ May 13, 2019 at 20:29
  • \$\begingroup\$ @NickKennedy I'm gonna say no on that one. \$\endgroup\$
    – Beefster
    May 13, 2019 at 20:44

4 Answers 4


Python 2, 138 126 120 117 113 bytes

F=lambda a,b,T,*U:a!=b and min([[t]+F(l,b,T,t,*U)for t in T if(t in U)<(a in t)for l in t-{a}]+[2*T],key=len)or[]

Try it online!

3 bytes thx to ArBo

Returns a minimal length list of the translators as sets of languages, i.e. 'by value', from T that allow a to talk to b.

  • \$\begingroup\$ if t not in U and a in t can be changed to if(a in t)>U.count(t) to save 4 bytes. \$\endgroup\$
    – mypetlion
    May 13, 2019 at 21:06
  • \$\begingroup\$ @mypetition - I had a similar thought and squeezed out another 2. \$\endgroup\$
    – Chas Brown
    May 13, 2019 at 21:08
  • \$\begingroup\$ 117 by using *args notation \$\endgroup\$
    – ArBo
    May 13, 2019 at 21:40
  • \$\begingroup\$ @ArBo: Nice; thx for 3 bytes. \$\endgroup\$
    – Chas Brown
    May 14, 2019 at 0:46

Jelly, 19 17 bytes


Try it online!

A dyadic link taking the list of translators as the left argument and list of ambassadors (each double-wrapped in a list) as the right argument. Returns a list of translators, each of which is a list of the languages they speak.

Thanks to @KevinCruijssen for saving 2 bytes!


ŒPŒ!€Ẏj@€fƝẠ$ƇḢḊṖ | A dyadic link taking a list of translators as left argument and a list of ambassadors (double-wrapped in lists) as right argument

ŒP                | Power set of translators
  Œ!€             | Permutations of each
     Ẏ            | Tighten, i.e. create a single list of all permutations of any length
      j@€         | Join the ambassadors with each set of translators
            $Ƈ    | Filter those where:
           Ạ      |   all
         fƝ       |   the neighbouring pairs have at least one in common
              Ḣ   | Take the first
               Ḋ  | Drop the first ambassador from the start
                Ṗ | Drop the second ambassador from the end
  • \$\begingroup\$ You can save 2 bytes by removing the sort by length , since the powerset + permurations already results in a list sorted by length. \$\endgroup\$ May 14, 2019 at 13:58
  • \$\begingroup\$ @KevinCruijssen thanks, good point! \$\endgroup\$ May 14, 2019 at 17:45

05AB1E, 18 17 bytes


Inspired by @NickKennedy's Jelly answer, so make sure to upvote him!

Outputs the lists themselves instead of their indices.

Try it online or verify all test cases.


æ                # Get the powerset of the (implicit) input-list of translators
                 #  i.e. [["ef","gh","bc"],["bc","ab"],["ef","cd","de"]]
                 #   → [[],[["ef","gh","bc"]],[["bc","ab"]],[["ef","gh","bc"],["bc","ab"]],[["ef","cd","de"]],[["ef","gh","bc"],["ef","cd","de"]],[["bc","ab"],["ef","cd","de"]],[["ef","gh","bc"],["bc","ab"],["ef","cd","de"]]]
 €œ              # Get the permutations of each
                 #  → [[[]],[[["ef","gh","bc"]]],[[["bc","ab"]]],[[["ef","gh","bc"],["bc","ab"]],[["bc","ab"],["ef","gh","bc"]]],[[["ef","cd","de"]]],[[["ef","gh","bc"],["ef","cd","de"]],[["ef","cd","de"],["ef","gh","bc"]]],[[["bc","ab"],["ef","cd","de"]],[["ef","cd","de"],["bc","ab"]]],[[["ef","gh","bc"],["bc","ab"],["ef","cd","de"]],[["ef","gh","bc"],["ef","cd","de"],["bc","ab"]],[["bc","ab"],["ef","gh","bc"],["ef","cd","de"]],[["bc","ab"],["ef","cd","de"],["ef","gh","bc"]],[["ef","cd","de"],["ef","gh","bc"],["bc","ab"]],[["ef","cd","de"],["bc","ab"],["ef","gh","bc"]]]]
   €`            # Flatten each one level down (4D list becomes 3D list)
                 #  → [[],[["ef","gh","bc"]],[["bc","ab"]],[["bc","ab"],["ef","gh","bc"]],[["ef","gh","bc"],["bc","ab"]],[["ef","cd","de"]],[["ef","cd","de"],["ef","gh","bc"]],[["ef","gh","bc"],["ef","cd","de"]],[["ef","cd","de"],["bc","ab"]],[["bc","ab"],["ef","cd","de"]],[["ef","cd","de"],["bc","ab"],["ef","gh","bc"]],[["ef","cd","de"],["ef","gh","bc"],["bc","ab"]],[["bc","ab"],["ef","cd","de"],["ef","gh","bc"]],[["bc","ab"],["ef","gh","bc"],["ef","cd","de"]],[["ef","gh","bc"],["ef","cd","de"],["bc","ab"]],[["ef","gh","bc"],["bc","ab"],["ef","cd","de"]]]
     ʒ           # Filter this 3D list by:
      ²š         #  Prepend the second input ambassador
                 #   i.e. [["bc","ab"],["ef","gh","bc"]] and "ab"
                 #    → ["ab",["bc","ab"],["ef","gh","bc"]]
        ³ª       #  Append the third input ambassador
                 #   i.e. ["ab",["bc","ab"],["ef","gh","bc"]] and "ef"
                 #    → ["ab",["bc","ab"],["ef","gh","bc"],"ef"]
          ü      #  For each adjacent pair of translator-lists:
           å     #   Check for each item in the second list, if it's in the first list
                 #    i.e. ["bc","ab"] and ["ef","gh","bc"] → [0,0,1]
            ۈ   #   Then check if any are truthy by leaving the maximum
                 #    → 1
              P  #  And then take the product to check if it's truthy for all pairs
                 #   i.e. ["ab",["bc","ab"],["ef","gh","bc"],"ef"] → [1,1,1] → 1
     }н          # After the filter: only leave the first list of translator-lists
                 #  i.e. [[["bc","ab"],["ef","gh","bc"]],[["bc","ab"],["ef","gh","bc"],["ef","cd","de"]]]
                 #   → [["bc","ab"],["ef","gh","bc"]]
                 # (which is output implicitly as result)

JavaScript (ES6),  123  121 bytes

Expects integers instead of 2-letter codes.


Try it online!


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.