Dwóch ambasadorów na konferencji ONZ chce ze sobą rozmawiać, ale niestety każdy z nich mówi tylko jednym językiem - i to nie jest ten sam język. Na szczęście mają dostęp do kilku tłumaczy, którzy rozumieją i mówią w kilku językach. Twoim zadaniem jest określenie najkrótszego łańcucha tłumaczy (ponieważ chcesz, aby jak najmniej zagubić się w tłumaczeniu), który pozwoli dwóm ambasadorom rozmawiać ze sobą.

Kodowanie

Dane wejściowe: dwa języki jako dwuliterowe ciągi małych liter (język każdego ambasadora) i lista list języków (jedna lista na jednego tłumacza)

Alternatywnie możesz przyjmować liczby całkowite zamiast kodów dwuliterowych.

Wynik: sekwencja tłumaczy według indeksu lub wartości, która jest jednym z najkrótszych łańcuchów tłumaczy, który pozwala dwóm ambasadorom na komunikację. Jeśli nie ma prawidłowego łańcucha tłumaczy, zachowanie jest niezdefiniowane. (Możesz zawiesić się, wypisać dowolną wartość lub wskazać błąd)

Prawidłowy łańcuch tłumaczy to taki, w którym pierwszy tłumacz mówi jednym językiem ambasadora, drugi i późniejsi tłumacze dzielą co najmniej jeden język z poprzednim tłumaczem, a ostatni tłumacz mówi językiem drugiego ambasadora.

Przykłady

Korzystanie z indeksowania zerowego:

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]

Zasady i założenia

• Obowiązują standardowe zasady We / Wy (użyj dowolnego wygodnego formatu We / Wy) i zabronione luki.
• Możesz założyć, że mówienie i rozumienie języków jest idealnie symetryczne i że wszystkie możliwe tłumaczenia między językami są równie wydajne.
• Nie ma koncepcji języków „wystarczająco blisko”. Na przykład używanie języka portugalskiego na jednym końcu, gdzie wymagany jest hiszpański, nie jest wystarczające.
• Jeśli istnieje wiele najkrótszych łańcuchów tłumacza, wystarczy jeden z nich.
• Jeśli ambasadorowie mówią tym samym językiem, lista tłumaczy powinna być pusta
• Który z ambasadorów jest pierwszy, nie ma znaczenia; lista tłumaczy może być do przodu lub do tyłu.
• Ambasadorowie mówią tylko jednym językiem ze względu na to wyzwanie
• Tłumacze mówią co najmniej dwoma językami
• Dwuliterowe kody języków nie muszą odpowiadać rzeczywistym językom
• Możesz założyć, że istnieje poprawna sekwencja tłumaczy
• W przypadku wyświetlania sekwencji według wartości należy uwzględnić pełny zestaw dostępnych języków, a nie tylko odpowiednie.

Wesołego golfa!

Python 2 , 138 126 120 117 113 bajtów

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

Wypróbuj online!

3 bajty dzięki ArBo

Zwraca listę tłumaczy o minimalnej długości jako sets języków, tzn. „Według wartości”, z Tktórych pozwalają arozmawiać b.

Galaretka , 19 17 bajtów

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

Wypróbuj online!

Dyadyczny link przyjmujący listę tłumaczy jako lewy argument i listę ambasadorów (każdy podwójnie zawinięty na liście) jako prawy argument. Zwraca listę tłumaczy, z których każdy jest listą języków, którymi mówią.

Dzięki @KevinCruijssen za oszczędność 2 bajtów!

Wyjaśnienie

Œ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 bajtów

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

Zainspirowany @NickKennedy „s Jelly odpowiedzi , więc upewnij się, aby go upvote!

Generuje same listy zamiast ich indeksów.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

æ                # 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 bajtów

Oczekuje liczb całkowitych zamiast kodów dwuliterowych.

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

Wypróbuj online!