Pangram jest ciąg znaków, który zawiera wszystkie litery a- zz alfabetu angielskiego, bez uwzględniania wielkości liter. (Jest ok, jeśli pangram zawiera więcej niż jedną kopię litery lub jeśli oprócz liter zawiera znaki inne niż litery).

Napisz program lub funkcję, której wejściem jest lista ciągów i które wypisuje jeden lub więcej ciągów, które mają następujące właściwości:

• Każdy ciąg wyjściowy musi być pangramem.
• Każdy ciąg wyjściowy musi zostać utworzony przez połączenie jednego lub więcej ciągów z listy wejściowej, oddzielonych spacjami.
• Każdy ciąg wyjściowy musi być najkrótszy lub powiązany najkrótszym spośród wszystkich ciągów o tych właściwościach.

Wiele programów wybiera wyświetlanie tylko jednego ciągu; chciałbyś wypisać więcej niż jeden ciąg, jeśli w innym przypadku musiałbyś napisać dodatkowy kod, aby ograniczyć wynik.

Możesz założyć, że dane wejściowe nie zawierają żadnych niedrukowalnych znaków ani spacji i że żadne słowo nie ma więcej niż (26-krotność naturalnego logarytmu długości listy) znaków. (Nie możesz jednak zakładać, że dane wejściowe zawierają tylko litery lub tylko małe litery; znaki interpunkcyjne i wielkie litery są całkowicie możliwe.)

Dane wejściowe i wyjściowe można podawać w dowolnym rozsądnym formacie. Do testowania twojego programu zalecam użycie dwóch przypadków testowych: słownika angielskich słów (większość komputerów ma jeden) oraz następującego przypadku (dla którego idealny (26-literowy) pangram jest niemożliwy, więc musisz go znaleźć zawierające zduplikowane litery):

abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz

Do zgłoszenia należy dołączyć próbkę danych wyjściowych programu. (Może to być różne dla różnych osób w wyniku używania różnych list słów).

Warunek zwycięstwa

Jest to wyzwanie polegające na kodzie golfowym o złożonej strukturze . Zwycięzcą jest najkrótszy program (w bajtach), który działa w czasie wielomianowym . (Podsumowanie dla osób, które nie wiedzą, co to znaczy: jeśli podwoisz rozmiar listy słów, program powinien stać się wolniejszy o nie więcej niż stały współczynnik. Jednak stały współczynnik, o którym mowa, może być tak duży, jak ty np. ważne jest, aby stała się czterokrotnie wolniejsza lub ośmiokrotnie wolniejsza, ale nie może być mniejsza o współczynnik długości listy słów; czynnik, przez który staje się wolniejszy, musi być ograniczony).

Ruby 159 (iteracyjny)

Rubin 227 220 229 227 221 (rekurencyjny)

Nowe iteracyjne rozwiązanie (oparte na algorytmie opisanym przez @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

Stare rozwiązanie rekurencyjne:

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

Pomiar bajtów polega na pozostawieniu ostatniej nowej linii w pliku, co nie ma znaczenia ruby 2.3.1p112. Liczba bajtów wróciła po naprawieniu małego błędu (dodawanie.downcase .upcase dla rozróżniania wielkości liter, jak wymaga tego opis problemu).

Oto wcześniejsza wersja sprzed skrócenia identyfikatorów i takie:

#!/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]);

Jak to działa? Zasadniczo utrzymuje zestaw znaków do zakrycia i powtarza się tylko na słowie, jeśli zmniejszyłoby to odkryte. Dodatkowo wyniki rekurencji są zapamiętywane. Każdy podzbiór 2 ^ 26 odpowiada wpisowi w tablicy zapamiętywania. Każdy taki wpis jest obliczany w czasie proporcjonalnym do wielkości pliku wejściowego. Więc cała sprawa to O(N)(gdzie Njest rozmiar pliku wejściowego), choć z ogromną stałą.

JavaScript (ES6), 249 248 bajtów, prawdopodobnie konkurencyjny

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]

Objaśnienie: Przekształca tablicę, przekształcając litery w maskę bitów, zapisując tylko najkrótsze słowo dla każdej maski bitowej na mapie. Następnie iterując po kopii mapy, powiększ mapę, dodając każdą połączoną maskę bitową, jeśli wynikowy łańcuch byłby krótszy. Na koniec zwróć ciąg zapisany dla mapy bitowej odpowiadającej pangramowi. (Zwraca, undefinedjeśli taki ciąg nie istnieje.)

Python 3, 98 , 94 , 92 bajtów

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

Iteruje przez reprezentację alfabetu ASCII i dodaje 1 do listy, jeśli litera zostanie znaleziona w ciągu. Jeśli suma listy jest większa niż 25, zawiera ona wszystkie litery alfabetu i zostanie wydrukowana.