Zwei Botschafter auf einer UN-Konferenz wollen miteinander sprechen, aber leider spricht jeder nur eine Sprache - und sie sprechen nicht dieselbe Sprache. Glücklicherweise haben sie Zugang zu mehreren Übersetzern, die jeweils einige Sprachen verstehen und sprechen. Ihre Aufgabe ist es, die kürzeste Kette von Übersetzern zu bestimmen (da Sie möchten, dass bei der Übersetzung so wenig wie möglich verloren geht), damit die beiden Botschafter miteinander sprechen können.

Codierung

Eingabe: zwei Sprachen als 2-Buchstaben-Kleinbuchstaben (Sprache jedes Botschafters) und eine Liste mit Sprachenlisten (eine Liste pro verfügbarem Übersetzer)

Sie können alternativ ganze Zahlen anstelle von 2-Buchstaben-Codes eingeben.

Ausgabe: Eine Folge von Übersetzern nach Index oder Wert, die eine der kürzesten Ketten von Übersetzern darstellt, mit denen die beiden Botschafter kommunizieren können. Wenn es keine gültige Übersetzerkette gibt, ist das Verhalten undefiniert. (Sie können abstürzen, einen beliebigen Wert ausgeben oder einen Fehler anzeigen.)

Eine gültige Übersetzerkette ist eine, bei der der erste Übersetzer die Sprache eines Botschafters spricht, der zweite und nachfolgende Übersetzer mindestens eine Sprache mit dem vorherigen Übersetzer teilen und der letzte Übersetzer die Sprache des anderen Botschafters spricht.

Beispiele

Nullbasierte Indizierung verwenden:

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]

Regeln und Annahmen

• Es gelten Standard-E / A-Regeln (verwenden Sie ein beliebiges praktisches E / A-Format) und verbotene Regelungslücken.
• Sie können davon ausgehen, dass das Sprechen und Verstehen von Sprachen perfekt symmetrisch ist und dass alle möglichen Übersetzungen zwischen Sprachen gleich effizient sind.
• Es gibt kein Konzept für "nahe genug" Sprachen. Es ist nicht gut genug, Portugiesisch an einem Ende zu verwenden, wenn beispielsweise Spanisch erforderlich ist.
• Wenn es mehrere kürzeste Übersetzerketten gibt, kann eine von ihnen verwendet werden.
• Wenn die Botschafter dieselbe Sprache sprechen, sollte die Übersetzerliste leer sein
• Welcher der Botschafter der erste ist, spielt keine Rolle; Die Übersetzerliste kann vorwärts oder rückwärts sein.
• Botschafter sprechen für diese Herausforderung nur eine Sprache
• Übersetzer sprechen mindestens zwei Sprachen
• Die 2-Buchstaben-Sprachcodes müssen nicht mit echten Sprachen übereinstimmen
• Sie können davon ausgehen, dass es eine gültige Folge von Übersetzern gibt
• Wenn Sie die Sequenz nach Wert ausgeben, müssen Sie den vollständigen Satz der verfügbaren Sprachen einbeziehen, nicht nur die relevanten.

Viel Spaß beim Golfen!

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

Probieren Sie es online!

3 Bytes danke an ArBo

Gibt eine minimale Länge Liste der Übersetzer als sets von Sprachen, dh ‚nach Wert‘ aus T, mit denen azu reden b.

Jelly , 19 17 Bytes

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

Probieren Sie es online!

Ein dyadischer Link, der die Liste der Übersetzer als linkes Argument und die Liste der Botschafter (jeweils doppelt in eine Liste eingeschlossen) als rechtes Argument verwendet. Gibt eine Liste von Übersetzern zurück, von denen jeder eine Liste der Sprachen ist, die sie sprechen.

Vielen Dank an @KevinCruijssen für das Speichern von 2 Bytes!

Erläuterung

Œ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 Bytes

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

Inspiriert von der Antwort von @NickKennedy 's Jelly , solltest du ihn also unbedingt unterstützen!

Gibt die Listen selbst anstelle ihrer Indizes aus.

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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

Erwartet ganze Zahlen anstelle von 2-Buchstaben-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)

Probieren Sie es online!