Lors d'une conférence des Nations Unies, deux ambassadeurs veulent se parler, mais malheureusement chacun ne parle qu'une seule langue et ce n'est pas la même langue. Heureusement, ils ont accès à plusieurs traducteurs, qui comprennent et parlent chacun quelques langues. Votre tâche consiste à déterminer la chaîne de traducteurs la plus courte (car vous voulez que le moins possible soit perdu dans la traduction) qui permette aux deux ambassadeurs de se parler.

Codage

Entrée: deux langues sous forme de chaînes minuscules à 2 lettres (chaque langue d'ambassadeur) et une liste de listes de langues (une liste par traducteur disponible)

Vous pouvez également accepter des entiers au lieu de codes à 2 lettres.

Sortie: une séquence de traducteurs, soit par index, soit par valeur, qui est l'une des chaînes de traducteurs les plus courtes permettant aux deux ambassadeurs de communiquer. S'il n'y a pas de chaîne de traducteurs valide, le comportement n'est pas défini. (Vous pouvez planter, afficher n'importe quelle valeur arbitraire ou indiquer une erreur)

Une chaîne de traducteurs valide est celle où le premier traducteur parle la langue d'un ambassadeur, le deuxième et les traducteurs suivants partagent au moins une langue avec le traducteur précédent et le dernier traducteur parle la langue de l'autre ambassadeur.

Exemples

Utilisation de l'indexation basée sur zéro:

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]

Règles et hypothèses

• Les règles d'E / S standard (utilisez n'importe quel format d'E / S pratique) et les failles interdites s'appliquent.
• Vous pouvez supposer que parler et comprendre les langues est parfaitement symétrique et que toutes les traductions possibles entre les langues sont tout aussi efficaces.
• Il n'y a pas de concept de langues "assez proches". Il n'est pas suffisant d'utiliser le portugais à une extrémité où l'espagnol est requis, par exemple.
• S'il existe plusieurs chaînes de traducteurs les plus courtes, l'une d'entre elles fera l'affaire.
• Si les ambassadeurs parlent la même langue, la liste des traducteurs doit être vide
• Lequel des ambassadeurs est le premier n'a pas d'importance; la liste des traducteurs peut être en avant ou en arrière.
• Les ambassadeurs ne parlent qu'une seule langue pour relever ce défi
• Les traducteurs parlent au moins deux langues
• Les codes de langue à 2 lettres n'ont pas besoin de correspondre aux langues réelles
• Vous pouvez supposer qu'il existe une séquence valide de traducteurs
• Si vous affichez la séquence par valeur, incluez l'ensemble complet des langues disponibles, pas seulement les langues pertinentes.

Bon golf!

Python 2 , 138 126 120 120 117 113 octets

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[]

Essayez-le en ligne!

3 octets de thx à ArBo

Renvoie une liste de longueur minimale des traducteurs en sets de langues, c'est-à-dire «par valeur», à partir de Tlaquelle permettent ade parler b.

Gelée , 19 17 octets

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

Essayez-le en ligne!

Un lien dyadique prenant la liste des traducteurs comme argument de gauche et la liste des ambassadeurs (chacun double dans une liste) comme argument de droite. Renvoie une liste de traducteurs, dont chacun est une liste des langues qu'ils parlent.

Merci à @KevinCruijssen d'avoir économisé 2 octets!

Explication

Œ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

05AB1E , 18 17 octets

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

Inspiré par la réponse Jelly de @NickKennedy , alors assurez-vous de voter pour lui!

Affiche les listes elles-mêmes au lieu de leurs indices.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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

Attend des entiers au lieu de codes à 2 lettres.

(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)

Essayez-le en ligne!