Encuentra los pangramas más cortos de una lista de palabras

10

Un pangrama es una cadena que contiene todas las cartas a- zdel alfabeto Inglés, entre mayúsculas y minúsculas. (Está bien si el pangrama contiene más de una copia de una letra, o si contiene caracteres que no son letras además de las letras).

Escriba un programa o función cuya entrada sea una lista de cadenas y que genere una o más cadenas que tengan las siguientes propiedades:

  • Cada cadena de salida debe ser un pangrama.
  • Cada cadena de salida debe formarse concatenando una o más cadenas de la lista de entrada, separadas por espacios.
  • Cada cadena de salida debe ser la más corta, o estar vinculada por la más corta, entre todas las cadenas con estas propiedades.

Muchos programas elegirán generar solo una cadena; solo querría generar más de una cadena si de lo contrario tendría que escribir código adicional para limitar la salida.

Puede suponer que la entrada no contiene caracteres o espacios no imprimibles, y que ninguna palabra contiene más de (26 veces el logaritmo natural de la longitud de la lista) caracteres. (Sin embargo, no puede suponer que la entrada contiene nada más que letras, o solo letras minúsculas; los signos de puntuación y las letras mayúsculas son totalmente posibles).

La entrada y salida se pueden dar en cualquier formato razonable. Para probar su programa, le recomiendo usar dos casos de prueba: un diccionario de palabras en inglés (la mayoría de las computadoras tienen uno) y el siguiente caso (para el cual es imposible un pangrama perfecto (26 letras), por lo que tendría que encontrar uno que contiene letras duplicadas):

abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz

Debe incluir una muestra de la salida de su programa junto con su envío. (Esto puede ser diferente para diferentes personas como resultado del uso de diferentes listas de palabras).

Condición de victoria

Este es un desafío de . El ganador es el programa más corto (en bytes) que se ejecuta en tiempo polinómico . (Un resumen para las personas que no saben lo que eso significa: si duplica el tamaño de la lista de palabras, el programa no debería ser más lento que un factor constante. Sin embargo, el factor constante en cuestión puede ser tan grande como usted). Por ejemplo, es válido para que sea cuatro veces más lento u ocho veces más lento, pero no para que se reduzca en un factor de la longitud de la lista de palabras; el factor a través del cual se vuelve más lento debe estar limitado).


fuente
Al determinar la complejidad, ¿podemos usar el hecho de que cada palabra tiene como máximo 26 letras? ¿Que el tamaño del alfabeto es una constante de 26?
xnor
Si. Puse esa restricción en la entrada allí en parte para hacer que la complejidad sea más fácil de definir / calcular.
Creo que esto se topa con un tecnicismo. Si ignora las palabras de entrada repetidas, hay a lo sumo 27 ^ 26 palabras de entrada posibles, y por lo tanto, a lo sumo 2 ^ (27 ^ 26) subconjuntos posibles de ellas como posibles entradas. Esto es enorme pero constante. Por lo tanto, cualquier programa en este conjunto finito es de tiempo constante, siendo la constante el número máximo de pasos dados sobre todas las entradas posibles.
xnor
No dije que no hay palabras duplicadas en la entrada. Sin embargo, supongo que podría ejecutar el programa en un tiempo "técnico" O (n) filtrando los signos de puntuación y deduplicando la entrada (o más probablemente O (n log n), que usaría mucha menos memoria que una raíz deduplicar lo haría). Luego tendría que volver de la versión filtrada a la lista de palabras original. ¡Sin embargo, no puede reclamar el tiempo polinómico en cuestión a menos que realmente siga todos esos pasos!
Me había olvidado de las no letras. ¿Podemos suponer que estos son ASCII, o de lo contrario dentro de un conjunto finito? Si es así, creo que cualquier algoritmo que comience por deduplicación puede pretender ser de tiempo polinómico.
xnor

Respuestas:

3

Ruby 159 (iterativo)

Rubí 227 220 229 227 221 (recursivo)

Nueva solución iterativa (basada en el 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

Antigua solución recursiva:

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

La medición de bytes se basa en dejar la nueva línea final en el archivo, lo que no importa ruby 2.3.1p112. El recuento de bytes volvió a subir después de corregir un pequeño error (agregando.downcase .upcase para la insensibilidad a mayúsculas y minúsculas como lo requiere la declaración del problema

Aquí hay una versión anterior de antes de acortar los identificadores y 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? Básicamente mantiene un conjunto de caracteres aún por cubrir y solo se repite en una palabra si reduciría el conjunto descubierto. Además, los resultados de la recursividad se memorizan. Cada subconjunto de 2 ^ 26 corresponde a una entrada de la tabla de memorización. Cada una de estas entradas se calcula en tiempo proporcional al tamaño del archivo de entrada. Entonces, todo el asunto es O(N)(¿dónde Nestá el tamaño del archivo de entrada), aunque con una gran constante.

Daniel deprimido
fuente
1

JavaScript (ES6), 249 248 bytes, posiblemente compitiendo

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]

Explicación: Transforma la matriz al convertir las letras en una máscara de bits, guardando solo la palabra más corta para cada máscara de bits en un mapa. Luego, iterando sobre una copia del mapa, aumente el mapa agregando cada máscara de bits combinada si la cadena resultante sería más corta. Finalmente, devuelva la cadena guardada para el mapa de bits correspondiente a un pangrama. (Devuelve undefinedsi no existe tal cadena).

Neil
fuente
Interesante. ¿Podría extenderse más sobre cómo funciona y, si está disponible, publicar el código no protegido?
DepressedDaniel
1
Esta debe ser una entrada válida / competitiva. Creo que esto realmente se ejecuta en O ( n log n ), de hecho! (El mapa tiene un límite duro de 2²⁶ entradas, y por lo tanto no aparece en la complejidad, por lo que el único tiempo es el tiempo de leer la entrada.)
Acabo de volver a leer la descripción y entiendo cómo funciona ahora. Ordenado. +1 ... Hmm, ¿cuándo decide dejar de intentar aumentar el mapa considerando pares? Debe continuar hasta que no haya relajaciones posibles.
DepressedDaniel
@DepressedDaniel Para cada máscara de bits extraída de la lista de palabras original, verifica todos los pangramas parciales que ha encontrado hasta ahora, y si agregar la palabra crea un pangrama que es más corto que el que actualmente conoce para la máscara de bits combinada.
Neil
@ ais523 Para entradas grandes (> 1000 palabras), parece que la mayor parte del tiempo se pasa intercambiando. ¡Intenté cambiar de un Mapa a una Matriz y se hizo aún más 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])

Itera a través de la representación ASCII del alfabeto y agrega un 1 a una lista si la letra se encuentra en la cadena. Si la suma de la lista es mayor que 25, contiene todas las letras del alfabeto y se imprimirá.

Erich
fuente
Creo que puedes eliminar un espacio entre (' ')y if. También puedes cambiar ord(i) in range(65,91)a 91>x>=65. Además, ¿cuál es la complejidad?
NoOneIsHere
1
¿Cuál es la complejidad de esta solución? Se requiere que la respuesta esté en complejidad polinómica, de lo contrario no es competitiva.
NoOneIsHere
Lo siento, creo que es O (n), porque la lista de entrada puede variar en longitud, pero
Erich
Lo siento, creo que es O (n), porque la lista de entrada puede variar en longitud, pero el segundo ciclo siempre va de 65 a 90. Pero no lo he probado.
Erich
No estoy seguro de que esto satisfaga "Cada cadena de salida debe ser la más corta, o estar vinculada por la más corta, entre todas las cadenas con estas propiedades".
DepressedDaniel