Two ambassadors at a UN conference want to speak to each other, but unfortunately each one only speaks one language- and they're not the same language. Fortunately, they have access to several translators, who each understand and speak a few languages. Your task is to determine the shortest chain of translators (since you want as little to be lost in translation as possible) that allows the two ambassadors to speak with each other.
Coding
Input: two languages as 2-letter lowercase strings (each ambassador's language) and a list of lists of languages (one list per available translator)
You may alternatively take in integers instead of 2-letter codes.
Output: A sequence of translators either by index or value that is any one of the shortest chains of translators that allows the two ambassadors to communicate. If there is no valid chain of translators, the behavior is undefined. (You may crash, output any arbitrary value, or indicate an error)
A valid chain of translators is one where the first translator speaks one ambassador's language, the second and subsequent translators share at least one language with the previous translator, and the last translator speaks the other ambassador's language.
Examples
Using zero-based indexing:
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]
Rules and Assumptions
- Standard IO rules (use any convenient I/O format) and banned loopholes apply.
- You may assume that speaking and understanding languages is perfectly symmetric and that all possible translations between languages are equally efficient.
- There is no concept of "close enough" languages. It is not good enough to use Portuguese on one end where Spanish is required, for instance.
- If there are multiple shortest translator chains, any one of them will do.
- If the ambassadors happen to speak the same language, the translator list should be empty
- Which of the ambassadors is the first one doesn't matter; the translator list can be forward or reverse.
- Ambassadors only speak one language for the sake of this challenge
- Translators speak at least two languages
- The 2-letter language codes do not need to correspond with real languages
- You may assume there is a valid sequence of translators
- If outputting the sequence by value, include the full set of available languages, not just the relevant ones.
Happy Golfing!
en,fr,sp;en,gr;gr,fr
\$\endgroup\$ – Quinn May 13 '19 at 19:49