Biorąc pod uwagę ciąg liter i zestaw słów, wypisz kolejność słów, aby można je było znaleźć w ciągu, upuszczając niepotrzebne litery. Słowa mogą występować więcej niż jeden raz w zestawie słów. Łańcuch wejściowy i wszystkie słowa składają się z 1 do 1000 małych liter. Litery, które mają być upuszczone, mogą występować wewnątrz słów lub między słowami.
Twój program lub funkcja może zaakceptować ciąg liter i słowa jako listy, ciąg znaków lub ze STDIN i musi wypisać wszystkie słowa w prawidłowej kolejności jako wyjście listy lub ciągu. Jeśli istnieje więcej niż jedno prawidłowe rozwiązanie, wypisz tylko jedno z nich. Jeśli nie ma możliwego poprawnego rozwiązania, wypisz pustą listę lub pusty ciąg.
Przykłady:
dogcatfrog cat frog dog
-> dog cat frog
xxcatfixsxhingonxgrapexxxfishingcxat cat grape catfish fishing
-> catfish grape fishing cat
dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc
-> da ab ba ba ba cc bb aa ac dc db dd
flea antelope
->
(no solution)
To jest kod golfowy. Najniższa liczba bajtów wygrywa.
Edycja: wyjaśniono, że dodatkowe znaki mogą znajdować się w słowach.
cc
przedbb
alebb
icc
podciągi pojawiają się tylko raz, abb
podciąg pojawia się jako pierwszy.ccbcb
części ciągu wypisujemycc
następnie wynikbb
po upuszczeniu środkac
.Odpowiedzi:
Pyth,
2024 bajtówMoja pierwsza próba na Pyth :)
Jak to działa:
Uwagi: w trzecim przykładzie (
dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc
) zajmuje dużo czasu .źródło
Pyth, 10 bajtów
Demonstracja
Ten program ma bardzo brutalną siłę. Najpierw konstruuje każdy podzbiór danych wejściowych, a następnie każdą partycję podzbiorów, a następnie sprawdza, czy jest to pierwszy, który stanowi zmianę kolejności listy słów. Żadne możliwości nie są obsługiwane przez błędy bez wyjścia na standardowe wyjście, na co pozwala meta konsensus. Błąd można usunąć dla 2 dodatkowych bajtów.
Pamiętaj, że w przypadku wielu podanych przypadków testowych program nie zostanie ukończony w rozsądnym czasie.
źródło
JavaScript (ES6), 119 bajtów
Akceptuje ciąg znaków i tablicę słów i zwraca tablicę słów lub
undefined
w przypadku awarii. Dodaj 2 bajty, jeśli musi zwrócić pusty ciąg w przypadku niepowodzenia (?q:``
), w którym to przypadku ta alternatywna wersja ma tylko 120 bajtów i zwraca pusty ciąg w przypadku awarii, a nawet może zapisać 2 bajty, jeśli może zwrócić 0 w przypadku awarii:(Po napisaniu tego zauważyłem, że algorytm jest w zasadzie taki sam jak odpowiedź Pyth @ KennyLau.)
Edytowana edycja: zaktualizowana po wyjaśnieniu pytania, ale teraz jest bardzo powolna w trzecim przypadku testowym; Wyłączyłem go poprzedniej nocy i dziś rano zauważyłem, że znalazło rozwiązanie, gdzieś pomiędzy 30 a 40 godzin później. Byłem naprawdę podły i podałem mu rozwiązanie (najlepiej działa z rozwiązaniem odwróconym, które natychmiast zweryfikuje).
źródło
Java 7, 256 bajtów
Zdecydowanie powinna być możliwa gra w golfa przy użyciu innego podejścia, ale na razie to zrobi ...
Kod niepoznany i testowy:
Wypróbuj tutaj.
Wynik:
źródło
Groovy (44 bajty)
Nie mogę uwierzyć, że nikt inny nie użył do tego wyrażeń regularnych ...
Wyjaśnienie
/${b.join('|')}/
- Utwórz wyrażenie regularne, aby znaleźć dowolne słowo w ciągu..findAll(...)
- Znajdź i zbierz wszystkie wystąpienia ciągu w tablicy..join(" ")
- Połącz tablicę ze spacjami.Zasadniczo, jeśli nie ma żadnych wystąpień, tablica jest pusta i niejawnie zwraca pusty ciąg. Jeśli znajdzie wystąpienia, zwraca obiekt tablicy z wystąpieniami, a następnie spłaszcza go w ciąg.
źródło