Dois embaixadores em uma conferência da ONU querem falar um com o outro, mas infelizmente cada um fala apenas um idioma - e eles não são o mesmo idioma. Felizmente, eles têm acesso a vários tradutores, que cada um entende e fala alguns idiomas. Sua tarefa é determinar a menor cadeia de tradutores (já que você deseja que o mínimo seja perdido na tradução) que permita que os dois embaixadores falem um com o outro.
Codificação
Entrada: dois idiomas como sequências de duas letras em minúsculas (idioma de cada embaixador) e uma lista de listas de idiomas (uma lista por tradutor disponível)
Como alternativa, você pode inserir números inteiros em vez de códigos de duas letras.
Saída: uma sequência de tradutores, por índice ou valor, que é uma das cadeias mais curtas de tradutores que permite que os dois embaixadores se comuniquem. Se não houver uma cadeia válida de tradutores, o comportamento será indefinido. (Você pode travar, gerar qualquer valor arbitrário ou indicar um erro)
Uma cadeia de tradutores válida é aquela em que o primeiro tradutor fala o idioma de um embaixador, o segundo e os tradutores subsequentes compartilham pelo menos um idioma com o tradutor anterior, e o último tradutor fala o idioma do outro embaixador.
Exemplos
Usando indexação baseada em zero:
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]
Regras e premissas
- Regras padrão de E / S (use qualquer formato de E / S conveniente) e brechas proibidas se aplicam.
- Você pode assumir que falar e entender idiomas é perfeitamente simétrico e que todas as traduções possíveis entre idiomas são igualmente eficientes.
- Não há conceito de linguagens "suficientemente próximas". Não é bom o suficiente usar o português em uma extremidade onde o espanhol é necessário, por exemplo.
- Se houver várias cadeias de tradutores mais curtas, qualquer uma delas funcionará.
- Se os embaixadores falam o mesmo idioma, a lista de tradutores deve estar vazia
- Qual dos embaixadores é o primeiro, não importa; a lista de tradutores pode ser encaminhada ou revertida.
- Os embaixadores falam apenas um idioma para o desafio
- Os tradutores falam pelo menos dois idiomas
- Os códigos de idioma de duas letras não precisam corresponder a idiomas reais
- Você pode assumir que há uma sequência válida de tradutores
- Se estiver produzindo a sequência por valor, inclua o conjunto completo de idiomas disponíveis, não apenas os relevantes.
Golfe feliz!
fonte
en,fr,sp;en,gr;gr,frRespostas:
Python 2 ,
138126120117113 bytesExperimente online!
3 bytes de thx para ArBo
Retorna uma lista de tamanho mínimo dos tradutores como
sets de idiomas, ou seja, 'por valor', a partir daTqual vocêapode conversarb.fonte
if t not in U and a in tpode ser alteradoif(a in t)>U.count(t)para salvar 4 bytes.*argsnotaçãoGeléia ,
1917 bytesExperimente online!
Um link diádico que toma a lista de tradutores como o argumento da esquerda e a lista de embaixadores (cada uma envolvida em uma lista) como o argumento da direita. Retorna uma lista de tradutores, cada um dos quais é uma lista dos idiomas que eles falam.
Obrigado a @KevinCruijssen por salvar 2 bytes!
Explicação
fonte
LÞ, pois as permissões do powerset + já resultam em uma lista classificada por comprimento.05AB1E ,
1817 bytesInspirado na resposta de @NickKennedy 's Jelly , por isso não deixe de votar nele!
Produz as próprias listas em vez de seus índices.
Experimente online ou verifique todos os casos de teste .
Explicação:
fonte
JavaScript (ES6),
123121 bytesEspera números inteiros em vez de códigos de duas letras.
Experimente online!
fonte