Ambassadors and Translators

Question

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.

Coding

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.

Examples

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!

Answer 1

Jelly, 19 17 bytes

ŒPŒ!€Ẏj@€fƝẠ$ƇḢḊṖ

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!

Explanation

Œ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

Answer 2

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.

Answer 3

05AB1E, 18 17 bytes

怜€`ʒ²š³ªüå€àP}н

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.

Explanation:

æ                # 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)

Answer 4

JavaScript (ES6),  123  121 bytes

Expects integers instead of 2-letter codes.

(a,b,l)=>((B=g=(m,s,i)=>m>>b&1?B<i||(o=s,B=i):l.map(a=>a.map(M=c=>M|=1<<c)|M&m&&m^(M|=m)&&g(M,[...s,a],-~i)))(1<<a,[]),o)

Try it online!