Два посла на конференции ООН хотят говорить друг с другом, но, к сожалению, каждый говорит только на одном языке - и они не на одном языке. К счастью, у них есть доступ к нескольким переводчикам, каждый из которых понимает и говорит на нескольких языках. Ваша задача - определить самую короткую цепочку переводчиков (поскольку вы хотите, чтобы при переводе было как можно меньше потерь), чтобы два посла могли говорить друг с другом.

кодирование

Ввод: два языка в виде двухбуквенных строчных букв (язык каждого посла) и список списков языков (один список для каждого доступного переводчика)

Вы также можете взять целые числа вместо двухбуквенных кодов.

Вывод: Последовательность переводчиков по индексу или значению, представляющая собой одну из самых коротких цепочек переводчиков, которая позволяет двум послам общаться. Если нет допустимой цепочки переводчиков, поведение не определено. (Вы можете потерпеть крах, вывести любое произвольное значение или указать ошибку)

Действительная цепочка переводчиков - это та, в которой первый переводчик говорит на языке одного посла, второй и последующие переводчики говорят по крайней мере на одном языке с предыдущим переводчиком, а последний переводчик говорит на языке другого посла.

Примеры

Использование индексации с нуля:

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]

Правила и предположения

• Применяются стандартные правила ввода-вывода (используйте любой удобный формат ввода-вывода) и запрещенные лазейки.
• Вы можете предположить, что говорение и понимание языков абсолютно симметричны и что все возможные переводы между языками одинаково эффективны.
• Не существует понятия «достаточно близких» языков. Например, недостаточно хорошо использовать португальский на одном конце, где требуется испанский.
• Если существует несколько кратчайших цепочек переводчиков, подойдет любая из них.
• Если послы говорят на одном языке, список переводчиков должен быть пустым
• Кто из послов первый, не имеет значения; список переводчиков может быть прямым или обратным.
• Послы говорят только на одном языке ради этого вызова
• Переводчики говорят как минимум на двух языках
• Двухбуквенные языковые коды не должны соответствовать реальным языкам
• Вы можете предположить, что существует правильная последовательность переводчиков
• Если вы выводите последовательность по значению, включите полный набор доступных языков, а не только соответствующие.

Счастливого гольфа!

Python 2 , 138 126 120 117 113 байтов

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

Попробуйте онлайн!

3 байта спасибо ArBo

Возвращает список минимальной длины переводчиков как sets языков, т. Е. «По значению», из Tкоторого можно aразговаривать b.

Желе , 19 17 байт

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

Попробуйте онлайн!

Диадическая ссылка, принимающая список переводчиков в качестве левого аргумента и список послов (каждый в двойном списке) в качестве правого аргумента. Возвращает список переводчиков, каждый из которых представляет собой список языков, на которых они говорят.

Спасибо @KevinCruijssen за сохранение 2 байта!

объяснение

Œ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 байт

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

Вдохновленный ответом Jelly @NickKennedy , так что обязательно проголосуйте за него!

Выводит сами списки вместо их индексов.

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

æ                # 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 байт

Ожидаются целые числа вместо 2-буквенных кодов.

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

Попробуйте онлайн!