Słowo złożone to słowo, które zawiera 2 lub więcej słów. Możemy jednak zrobić to lepiej. Musimy stworzyć 1 (nonsensowne) słowo, które zawiera każde słowo .
Chcemy jednak, aby to słowo było jak najkrótsze. W tym celu możemy użyć nakładających się liter.
Na przykład, jeśli twoja lista słów była ["cat", "atom", "a"]
, chciałbyś powrócić "catom"
.
Wejście wyjście
Twój program będzie musiał pobrać listę słów jako dane wejściowe i zwrócić słowo złożone jako dane wyjściowe.
Według Google lista słów, której będziesz używać, to 10000 najpopularniejszych słów w języku angielskim (jeśli ta lista okaże się zbyt łatwa, mogę ją zmienić na dłuższą). Dla porównania, po prostu dołączenie każdego słowa daje wynik 65888.
Twój wynik to liczba liter w ostatnim słowie, im niższa, tym lepsza. Łamacz remisów trafia na pierwszy plakat.
źródło
Odpowiedzi:
C ++, końcowa długość słowa: 38272
(zoptymalizowana wersja zajęła około 20 minut)
Weryfikacja bash one-liner:
Stworzyło też całkiem fajne słowa w toku. Oto niektóre z moich ulubionych:
I:
Ostateczne wyjście znajduje się na pastebin tutaj: http://pastebin.com/j3qYb65b
źródło
max_word_length - overlap(word[i], word[j])
(gdzieoverlap
sprawdza nakładanie się z prawej strony pierwszy argument po lewej stronie drugiego). Rozwiązanie tego (powodzenia!), A następnie odcięcie powstałej pętli przy najwyższym koszcie (najniższe nakładanie się) da uporządkowaną listę słów, które można połączyć, aby uzyskać optymalne rozwiązanie.C ++ 11, 38272 liter, sprawdzone jako optymalne
Ten algorytm gwarantuje dolną granicę rozwiązania. W takim przypadku jest w stanie osiągnąć dolną granicę i wydać optymalne rozwiązanie 38272 liter. (To pasuje do rozwiązania znalezionego przez chciwy algorytm Dave'a. Byłem zaskoczony i trochę rozczarowany odkryciem, że jest optymalny, ale tak jest.)
Działa poprzez rozwiązanie problemu minimalnego kosztu przepływu w sieci zbudowanej w następujący sposób.
Każdy ciąg długości n, który zawiera każde słowo, można przekształcić w przepływ w tej sieci, kosztując najwyżej n . Dlatego minimalny przepływ kosztów w tej sieci stanowi dolną granicę długości najkrótszego takiego ciągu.
Jeśli mamy szczęście - i w tym przypadku mamy - to po przekierowaniu przepływu wchodzącego do w _1 z powrotem z w _0, znajdziemy optymalny przepływ, który ma tylko jeden połączony komponent i który przechodzi przez węzeł dla pustego strunowy. Jeśli tak, będzie zawierać obwód Eulera, który zaczyna się i kończy. Taki obwód Eulera można odczytać jako ciąg optymalnej długości.
Jeśli nie będziemy mieli szczęścia, dodaj dodatkowe łuki między pustym łańcuchem a najkrótszymi łańcuchami w innych połączonych komponentach, aby upewnić się, że istnieje obwód Eulera. W takim przypadku łańcuch niekoniecznie byłby już optymalny.
Korzystam z biblioteki LEMON dla jej minimalnego kosztu przepływu i algorytmów obwodu Eulera. (To był mój pierwszy raz, kiedy korzystałem z tej biblioteki i byłem pod wrażeniem - na pewno użyję jej ponownie do przyszłych potrzeb algorytmów graficznych.) LEMON jest wyposażony w cztery różne algorytmy przepływu minimalnych kosztów; można spróbować je tutaj z
--net
,--cost
,--cap
i--cycle
(domyślnie).Program działa w ciągu 0,5 sekundy , generując ten ciąg wyjściowy .
źródło
Java 8, ~ 5 minut, długość 39 279
Wkład:
Wydajność:
źródło
26,609
postaci.Python 2, 39254 znaków
Uruchomienie na mojej maszynie zajmuje 1-2 minuty. Działa, biorąc najdłuższe słowo, a następnie zawsze dodając słowo do ciągu wynikowego, który ma najwięcej wspólnych ciągów. (Wcześniej wszystkie słowa będące podciągami innych słów są usuwane, aby zapobiec niepotrzebnemu dodawaniu do łańcucha).
Aktualizacja: Próbowałem spojrzeć w obu kierunkach, ale to nie robi nic lepszego. (może używa słów, których później można lepiej użyć?)
Link do słowa na pastebin.
pierwszych 100 znaków:
Kod:
źródło
Ruby, 39222 znaków
Używa podobnego podejścia do @KarlKastor w swojej odpowiedzi w Pythonie, ale łańcuch początkowy jest jednym z najmniejszych słów zamiast największego. Kolejną optymalizacją (nie wiem, jak bardzo to pomaga) jest to, że pomiędzy każdym dodaniem przycina wszystkie słowa, które mogły być już zawarte w ciągu z powodu nakładających się słów.
Działa na mojej maszynie w nieco ponad 4 minuty, nie licząc żądania internetowego, aby pobrać listę słów, ale nie całkiem 4:20.
Słowo o Pastebin.
źródło
PowerShell v2 +, 46152 znaków
Pobiera dane wejściowe jako listę, rzutuje je na ArrayList (abyśmy mogli nimi manipulować). Mamy
sort
tolength
w-des
porządku rosnącym. Następniewhile
nadal mamy słowa w naszej tablicy wejściowej, wykonaj pętlę. W każdej iteracji ustaw pomocnika$x
na równi z tym, ile nam pozostało, przypnij następny element na liście do naszej produkcji$o
, a następnie przejrzyj wszystko, co wciąż jest na naszej liście. Jeśli.IndexOf
to nie jest równe-1
(tzn. Słowo zostało znalezione gdzieś w środku$o
), usuwamy to słowo z naszej listy pozostałych słów. Wreszcie na koniec wyjście$o
.Nie mam dostępu do Pastebin lub podobnego, więc tutaj jest początek i koniec słowa tymczasowego -
telecommunicationscharacterizationresponsibilitiessublimedirectory...fcmxvtwvfxwujmjsuhjjrxjdbkdxqc
. Zgaduję, że zgoliłem około 20 000 znaków z wejścia, więc nie jest tak źle, jak sądzę.Pracuję nad udoskonaleniami.
źródło
PHP 46612 znaków
To dopiero początek. Mam nadzieję to poprawić. Wszystko, co do tej pory zrobiłem, to usunięcie dowolnego słowa, które jest podłańcuchem innego słowa. Pracuję nad 3 kopiami tablicy, ale pamięć nie wydaje się być problemem.
źródło