Um pangram é uma sequência que contém todas as letras a
- z
do alfabeto inglês, sem distinção entre maiúsculas e minúsculas. (Tudo bem se o pangram contiver mais de uma cópia de uma carta ou se não houver caracteres além das letras.)
Escreva um programa ou função cuja entrada seja uma lista de cadeias e que produza uma ou mais cadeias que possuam as seguintes propriedades:
- Cada sequência de saída deve ser um pangram.
- Cada sequência de saída deve ser formada concatenando uma ou mais sequências da lista de entrada, separadas por espaços.
- Cada sequência de saída deve ser a mais curta ou vinculada ao menor entre todas as seqüências com essas propriedades.
Muitos programas escolhem produzir apenas uma string; você só desejaria gerar mais de uma sequência se, caso contrário, tivesse que escrever um código extra para limitar a saída.
Você pode supor que a entrada não contenha caracteres ou espaços não imprimíveis e que nenhuma palavra contenha mais do que (26 vezes o logaritmo natural do comprimento da lista) caracteres. (Você não pode supor, no entanto, que a entrada contenha apenas letras ou minúsculas; sinais de pontuação e maiúsculas são totalmente possíveis.)
Entrada e saída podem ser fornecidas em qualquer formato razoável. Para testar seu programa, recomendo o uso de dois casos de teste: um dicionário de palavras em inglês (a maioria dos computadores possui um) e o seguinte (para o qual um pangram perfeito (26 letras) é impossível, você deve encontrar um contendo letras duplicadas):
abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz
Você deve incluir uma amostra da saída do seu programa junto com o envio. (Isso pode ser diferente para pessoas diferentes, como resultado do uso de listas de palavras diferentes.)
Condição de vitória
Este é um desafio de código-golfe de complexidade restrita . O vencedor é o programa mais curto (em bytes) executado em tempo polinomial . (Um resumo para pessoas que não sabem o que isso significa: se você dobrar o tamanho da lista de palavras, o programa deverá ficar mais lento em não mais que um fator constante. No entanto, o fator constante em questão pode ser tão grande quanto você Por exemplo, é válido que ele se torne quatro vezes mais lento ou oito vezes mais lento, mas não se torne menor por um fator do comprimento da lista de palavras; o fator pelo qual se torna mais lento deve ser delimitado.)
Respostas:
Ruby 159 (iterativo)
Rubi
227220229227221 (recursiva)Nova solução iterativa (com base no algoritmo descrito por @Niel):
Solução recursiva antiga:
A medição de bytes baseia-se em deixar de fora a nova linha final no arquivo, o que não importa
ruby 2.3.1p112
. A contagem de bytes voltou após a correção de um pequeno bug (adicionando.downcase
.upcase
insensibilidade a maiúsculas e minúsculas, conforme exigido pela declaração do problema).Aqui está uma versão anterior de antes de encurtar identificadores e tal:
Como funciona? Basicamente, mantém um conjunto de caracteres ainda a cobrir e só se repete em uma palavra se isso reduzir o conjunto descoberto. Além disso, os resultados da recursão são memorizados. Cada subconjunto de 2 ^ 26 corresponde a uma entrada da tabela de memorização. Cada entrada é calculada em tempo proporcional ao tamanho do arquivo de entrada. Então, a coisa toda é
O(N)
(ondeN
está o tamanho do arquivo de entrada), embora com uma constante enorme.fonte
JavaScript (ES6),
249248 bytes, possivelmente competindoExplicação: Transforma a matriz convertendo as letras em uma máscara de bit, salvando apenas a palavra mais curta para cada máscara de bit em um mapa. Em seguida, iterando sobre uma cópia do mapa, aumente o mapa adicionando cada máscara de bits combinada se a sequência resultante for menor. Finalmente, retorne a string salva para o bitmap correspondente a um pangram. (Retorna
undefined
se essa string não existir.)fonte
Python 3,
98,94, 92 bytesRepete a representação ASCII do alfabeto e adiciona 1 a uma lista se a letra for encontrada na sequência. Se a soma da lista for maior que 25, ela conterá todas as letras do alfabeto e será impressa.
fonte
(' ')
eif
. Você também pode mudarord(i) in range(65,91)
para91>x>=65
. Além disso, qual é a complexidade?