Encontre os pangrams mais curtos de uma lista de palavras

10

Um pangram é uma sequência que contém todas as letras a- zdo 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 . 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.)


fonte
Ao determinar a complexidade, podemos usar o fato de que cada palavra tem no máximo 26 letras? Que o tamanho do alfabeto é uma constante de 26?
Xnor
Sim. Coloquei essa restrição na entrada parcialmente para facilitar a definição / cálculo da complexidade.
Eu acho que isso é um detalhe técnico. Se você ignorar palavras de entrada repetidas, existem no máximo 27 ^ 26 palavras de entrada possíveis e, no máximo, 2 ^ (27 ^ 26) possíveis subconjuntos delas como possíveis entradas. Isso é enorme, mas uma constante. Portanto, qualquer programa nesse conjunto finito é de tempo constante, sendo a constante o número máximo de etapas executadas em todas as entradas possíveis.
Xnor
Eu não disse que não há palavras duplicadas na entrada. Eu acho que você pode executar o programa em um tempo O (n) "técnico" filtrando sinais de pontuação e deduplicando a entrada primeiro, embora (ou mais provavelmente O (n log n), que usaria muito menos memória que um radical deduplicado). Você precisará voltar da versão filtrada para a lista de palavras original. Você não pode reivindicar o tempo polinomial em questão, a menos que você realmente execute todas essas etapas!
Eu tinha esquecido as não letras. Podemos assumir que estes são ASCII, ou de alguma forma dentro de um conjunto finito? Nesse caso, acho que qualquer algoritmo que começa com desduplicação pode reivindicar tempo polinomial.
xnor

Respostas:

3

Ruby 159 (iterativo)

Rubi 227 220 229 227 221 (recursiva)

Nova solução iterativa (com base no algoritmo descrito por @Niel):

c={('A'..'Z').to_a=>""}
while l=gets
d=c.clone
c.map{|k,v|j=k-l.upcase.chars
w=v+" "+l.strip
d[j]=w if !c[j]||c[j].size<w.size}
c=d
end
x=c[[]]
p x[1..-1] if x

Solução recursiva antiga:

W=[]
while l=gets
W<<l.strip
end
I=W.join(" ")+"!!"
C={[]=>""}
def o(r)if C[r]
C[r]
else
b=I
W.map{|x|s=r-x.upcase.chars
if s!=r
c=x+" "+o(s)
b=c if c.size<b.size
end}
C[r]=b
end
end
r=o ('A'..'Z').to_a
p r[0..-2] if r!=I

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:

#!/usr/bin/env ruby

$words = [];

while (line=gets)
  $words << line[0..-2];
end

$impossible = $words.join(" ")+"!!";

$cache = {};

def optimize(remaining)
  return $cache[remaining] if ($cache[remaining]);
  return "" if (remaining == []);

  best = $impossible;

  $words.each{|word|
    remaining2 = remaining - word.chars;
    if (remaining2 != remaining)
      curr = word + " " + optimize(remaining2);
      best = curr if (curr.length < best.length);
    end
  };

  $stderr.puts("optimize(#{remaining.inspect})=#{best.inspect}");

  return $cache[remaining] = best;
end

result = optimize(('a'..'z').to_a);

puts(result[0..-1]);

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)(onde Nestá o tamanho do arquivo de entrada), embora com uma constante enorme.

DepressedDaniel
fonte
1

JavaScript (ES6), 249 248 bytes, possivelmente competindo

a=>a.map(w=>w.replace(/[a-z]/gi,c=>b|=1<<parseInt(c,36)-9,b=0,l=w.length)&&(m.get(b)||[])[0]<l||m.set(b,[l,w]),m=new Map)&&[...m].map(([b,[l,w]])=>m.forEach(([t,s],e)=>(m.get(e|=b)||[])[0]<=t+l||m.set(e,[t+l+1,s+' '+w])))&&(m.get(-2^-1<<27)||[])[1]

Explicaçã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 undefinedse essa string não existir.)

Neil
fonte
Interessante. Você poderia expor mais sobre como ele funciona e, se disponível, postar o código não-bloqueado?
DepressedDaniel
11
Esta deve ser uma entrada válida / concorrente. Eu acho que isso realmente funciona em O ( n log n ), de fato! (O mapa tem um limite rígido de 2²⁶ entradas, e, portanto, não aparece na complexidade; portanto, o único tempo gasto é o momento de ler a entrada.)
Acabei de reler a descrição e entendo como ela funciona agora. Arrumado. +1 ... Hummm, quando ele decide parar de tentar aumentar o mapa considerando pares? Deve continuar até que não sejam possíveis relaxamentos.
DepressedDaniel
@DepressedDaniel Para cada máscara de bits extraída da lista de palavras original, ela verifica todos os pangramas parciais encontrados até o momento e se a adição da palavra cria um pangram menor do que o atualmente conhecido para a máscara de bit combinada.
Neil
@ ais523 Para entradas grandes (> 1000 palavras), a maior parte do tempo parece gasta na troca. Tentei mudar de um mapa para uma matriz e ficou ainda mais lento!
Neil
-1

Python 3, 98 , 94 , 92 bytes

print([s for s in input().split()if sum([1 for c in range(65,91)if chr(c)in s.upper()])>25])

Repete 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.

Erich
fonte
Eu acho que você pode remover um espaço entre (' ')e if. Você também pode mudar ord(i) in range(65,91)para 91>x>=65. Além disso, qual é a complexidade?
NoOneIsHere
11
Qual é a complexidade desta solução? É necessário que a resposta tenha complexidade polinomial, caso contrário, não é concorrente.
NoOneIsHere
Desculpe, acho que é O (n), porque a lista de entrada pode variar em comprimento, mas
Erich
Desculpe, acho que é O (n), porque a lista de entrada pode variar em tamanho, mas o segundo loop sempre varia de 65 a 90. Mas não testei.
Erich
Não tenho certeza se isso satisfaz "Cada sequência de saída deve ser a mais curta ou vinculada ao menor entre todas as seqüências com essas propriedades".
DepressedDaniel