Dos embajadores en una conferencia de la ONU quieren hablar entre ellos, pero desafortunadamente cada uno solo habla un idioma, y no son el mismo idioma. Afortunadamente, tienen acceso a varios traductores, cada uno de los cuales entiende y habla algunos idiomas. Su tarea es determinar la cadena más corta de traductores (ya que desea que se pierda lo menos posible en la traducción) que permita a los dos embajadores hablar entre ellos.
Codificación
Entrada: dos idiomas como cadenas minúsculas de 2 letras (idioma de cada embajador) y una lista de listas de idiomas (una lista por traductor disponible)
Alternativamente, puede tomar enteros en lugar de códigos de 2 letras.
Salida: una secuencia de traductores, ya sea por índice o por valor, que es una de las cadenas de traductores más cortas que permite que los dos embajadores se comuniquen. Si no hay una cadena válida de traductores, el comportamiento es indefinido. (Puede bloquearse, generar un valor arbitrario o indicar un error)
Una cadena válida de traductores es aquella en la que el primer traductor habla el idioma de un embajador, el segundo y los siguientes traductores comparten al menos un idioma con el traductor anterior, y el último traductor habla el idioma del otro embajador.
Ejemplos
Usando indexación basada en cero:
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]
Reglas y Suposiciones
- Se aplican las reglas estándar de E / S (use cualquier formato de E / S conveniente) y las lagunas prohibidas.
- Puede suponer que hablar y comprender idiomas es perfectamente simétrico y que todas las traducciones posibles entre idiomas son igualmente eficientes.
- No existe un concepto de lenguajes "lo suficientemente cercanos". No es suficiente usar portugués en un extremo donde se requiere español, por ejemplo.
- Si hay varias cadenas de traductores más cortas, cualquiera de ellas funcionará.
- Si los embajadores hablan el mismo idioma, la lista de traductores debe estar vacía.
- Cuál de los embajadores es el primero no importa; La lista de traductores puede ser directa o inversa.
- Los embajadores solo hablan un idioma en aras de este desafío
- Los traductores hablan al menos dos idiomas
- Los códigos de idioma de 2 letras no necesitan corresponder con idiomas reales
- Puede suponer que hay una secuencia válida de traductores
- Si genera la secuencia por valor, incluya el conjunto completo de idiomas disponibles, no solo los relevantes.
¡Feliz golf!
fuente
en,fr,sp;en,gr;gr,frRespuestas:
Python 2 ,
138126120117113 bytesPruébalo en línea!
3 bytes thx a ArBo
Devuelve una lista de longitud mínima de los traductores como
sets de idiomas, es decir, 'por valor', desde elTque permiteahablarb.fuente
if t not in U and a in tse puede cambiar aif(a in t)>U.count(t)para guardar 4 bytes.*argsnotaciónJalea ,
1917 bytesPruébalo en línea!
Un enlace diádico que toma la lista de traductores como argumento izquierdo y la lista de embajadores (cada uno doblemente envuelto en una lista) como argumento correcto. Devuelve una lista de traductores, cada uno de los cuales es una lista de los idiomas que hablan.
¡Gracias a @KevinCruijssen por guardar 2 bytes!
Explicación
fuente
LÞ, ya que el conjunto de potencia + permuraciones ya da como resultado una lista ordenada por longitud.05AB1E ,
1817 bytesInspirado por la respuesta Jelly de @NickKennedy , ¡así que asegúrate de votarlo!
Produce las listas en sí en lugar de sus índices.
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
fuente
JavaScript (ES6),
123121 bytesEspera números enteros en lugar de códigos de 2 letras.
Pruébalo en línea!
fuente