Znajdź najkrótsze pangramy z listy słów

10

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


źródło
Czy przy określaniu złożoności możemy wykorzystać fakt, że każde słowo ma maksymalnie 26 liter? Czy rozmiar alfabetu jest stały 26?
xnor
Tak. Położyłem to ograniczenie na danych wejściowych częściowo, aby ułatwić zdefiniowanie / obliczenie złożoności.
Myślę, że to prowadzi do problemów technicznych. Jeśli zignorujesz powtarzające się słowa wejściowe, istnieje co najwyżej 27 ^ 26 możliwych słów wejściowych, a więc co najwyżej 2 ^ (27 ^ 26) możliwych ich podzbiorów jako możliwych danych wejściowych. To jest ogromne, ale stałe. Tak więc każdy program w tym skończonym zestawie jest czasem stałym, przy czym stała jest maksymalną liczbą kroków wykonanych na wszystkich możliwych wejściach.
xnor
Nie powiedziałem, że na wejściu nie ma zduplikowanych słów. Wydaje mi się, że można uruchomić program w „technicznym” czasie O (n), odfiltrowując znaki interpunkcyjne i najpierw deduplikując dane wejściowe (lub bardziej prawdopodobne O (n log n), co zużyłoby dużo mniej pamięci niż podstawa deduplikacja). Następnie musisz wrócić z przefiltrowanej wersji do oryginalnej listy słów. Nie możesz jednak twierdzić o wielomianowym czasie, o ile nie wykonasz wszystkich tych kroków!
Zapomniałam o nieliterach. Czy możemy założyć, że są to ASCII lub w inny sposób w ramach skończonego zbioru? Jeśli tak, to uważam, że każdy algorytm, który zaczyna się od deduplikacji, może twierdzić, że jest czasem wielomianowym.
xnor

Odpowiedzi:

3

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łą.

DepressedDaniel
źródło
1

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

Neil
źródło
Ciekawy. Czy możesz wyjaśnić więcej na temat tego, jak to działa i, jeśli są dostępne, opublikować nieoznaczony kod?
DepressedDaniel
1
To powinien być prawidłowy / konkurujący wpis. Myślę, że tak naprawdę działa to w O ( n log n )! (Mapa ma twardy limit wpisów 2²⁶, a zatem nie pokazuje się w złożoności; w związku z tym jedynym czasem spędzonym na czytaniu danych wejściowych.)
Właśnie przeczytałem opis i rozumiem, jak to działa. Schludny. +1 ... Hmm, kiedy decyduje się przestać próbować powiększać mapę, biorąc pod uwagę pary? Powinno to trwać, dopóki nie będą możliwe żadne relaksacje.
DepressedDaniel
@DepressedDaniel Dla każdej maski bitowej wyodrębnionej z oryginalnej listy słów, sprawdza wszystkie częściowe pangramy, które dotąd znalazł, i czy dodanie słowa tworzy pangram, który jest krótszy niż ten, który obecnie zna dla połączonej maski bitowej.
Neil,
@ ais523 W przypadku dużych nakładów (> 1000 słów) większość czasu wydaje się na zamianę. Próbowałem zmienić mapę na tablicę i stało się jeszcze wolniej!
Neil,
-1

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.

Erich
źródło
Myślę, że możesz usunąć spację między (' ')i if. Możesz także zmienić ord(i) in range(65,91)na 91>x>=65. Jaka jest złożoność?
NoOneIsHere
1
Jaka jest złożoność tego rozwiązania? Wymagane jest, aby odpowiedź była złożona wielomianowo, w przeciwnym razie nie jest konkurencyjna.
NoOneIsHere
Przepraszam, myślę, że jest to O (n), ponieważ lista danych wejściowych może różnić się długością, ale
Erich
Przepraszam, myślę, że jest to O (n), ponieważ lista danych wejściowych może mieć różną długość, ale druga pętla zawsze ma długość od 65 do 90. Ale ja tego nie testowałem.
Erich
Nie jestem pewien, czy to spełnia kryteria „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”.
DepressedDaniel