Dua duta besar di konferensi PBB ingin berbicara satu sama lain, tetapi sayangnya masing-masing hanya berbicara satu bahasa - dan mereka bukan bahasa yang sama. Untungnya, mereka memiliki akses ke beberapa penerjemah, yang masing-masing memahami dan berbicara beberapa bahasa. Tugas Anda adalah untuk menentukan rantai penerjemah terpendek (karena Anda ingin sesedikit mungkin hilang dalam terjemahan mungkin) yang memungkinkan kedua duta besar untuk berbicara satu sama lain.

Coding

Input: dua bahasa sebagai string huruf kecil 2 huruf (bahasa masing-masing duta besar) dan daftar bahasa (satu daftar per penerjemah yang tersedia)

Anda dapat mengambil bilangan bulat sebagai pengganti kode 2 huruf.

Keluaran: Urutan penerjemah baik berdasarkan indeks atau nilai yang merupakan salah satu rantai penerjemah terpendek yang memungkinkan kedua duta besar berkomunikasi. Jika tidak ada rantai penerjemah yang valid, perilaku tersebut tidak terdefinisi. (Anda mungkin macet, menampilkan nilai sembarang, atau menunjukkan kesalahan)

Rantai penerjemah yang valid adalah di mana penerjemah pertama berbicara bahasa satu duta besar, penerjemah kedua dan selanjutnya berbagi setidaknya satu bahasa dengan penerjemah sebelumnya, dan penerjemah terakhir berbicara bahasa duta besar lainnya.

Contohnya

Menggunakan pengindeksan berbasis nol:

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]

Aturan dan Asumsi

• Aturan IO standar (gunakan format I / O yang nyaman) dan celah terlarang berlaku.
• Anda dapat berasumsi bahwa berbicara dan memahami bahasa sangat simetris dan bahwa semua terjemahan yang mungkin antar bahasa sama-sama efisien.
• Tidak ada konsep bahasa "cukup dekat". Misalnya, tidak cukup baik menggunakan bahasa Portugis di satu sisi di mana bahasa Spanyol diperlukan, misalnya.
• Jika ada beberapa rantai penerjemah terpendek, salah satu dari mereka akan melakukannya.
• Jika para duta besar berbicara dengan bahasa yang sama, daftar penerjemah harus kosong
• Yang mana dari duta besar yang pertama tidak penting; daftar penerjemah dapat maju atau mundur.
• Duta besar hanya berbicara satu bahasa demi tantangan ini
• Penerjemah berbicara setidaknya dua bahasa
• Kode bahasa 2 huruf tidak perlu sesuai dengan bahasa asli
• Anda mungkin menganggap ada urutan penerjemah yang valid
• Jika mengeluarkan urutan berdasarkan nilai, sertakan set lengkap bahasa yang tersedia, bukan hanya yang relevan.

Selamat Golf!

Python 2 , 138 126 120 117 113 byte

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

Cobalah online!

3 byte thx ke ArBo

Mengembalikan daftar panjang minimal penerjemah sebagai setbahasa, yaitu 'berdasarkan nilai', dari Tyang memungkinkan auntuk diajak bicara b.

Jelly , 19 17 byte

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

Cobalah online!

Tautan diad yang menggunakan daftar penerjemah sebagai argumen kiri dan daftar duta besar (masing-masing terbungkus ganda dalam daftar) sebagai argumen yang tepat. Mengembalikan daftar penerjemah, yang masing-masing adalah daftar bahasa yang mereka gunakan.

Terima kasih kepada @KevinCruijssen karena telah menghemat 2 byte!

Penjelasan

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

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

Terinspirasi oleh jawaban Jelly @NickKennedy , jadi pastikan untuk mendukungnya!

Keluarkan daftar sendiri bukan indeksnya.

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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

Mengharapkan bilangan bulat alih-alih kode 2 huruf.

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

Cobalah online!