Usuń litery, zachowując ciągi unikalne

15

Zainspirowany tym cudownym (na podstawie liczby wyświetleń i głosów) wyzwaniem, które moim skromnym zdaniem ma zbyt mało odpowiedzi.

Biorąc pod uwagę (w jakikolwiek sposób) listę ciągów, zwróć (w jakikolwiek sposób) zestaw liter, który po usunięciu z podanych ciągów pozostawia całkowitą długość (tego, co pozostało) ciągów tak małą, jak to możliwe, zachowując każde ciąg unikalny i co najmniej jeden znak.

Przykłady:

Biorąc pod uwagę „Dzień” i „Dzień”; zwraca „ay”, ponieważ podane ciągi będą „D” i „d”, gdy znaki „ay” zostaną usunięte.

Biorąc pod uwagę „Hello World!”, „Hello world.” I „Hello world”; return „Helo Wrd” daje, ponieważ ciągi znaków będą „!”, „w.” i „w”, gdy znaki „Helo Wrd” (ze spacją) zostaną usunięte.

Biorąc pod uwagę „wiek”, „dekadę”, „rok”, „miesiąc”, „tydzień”, „dzień”, „godzinę”, „minutę” i „sekundę”; zwraca „centurdowi”, ponieważ podane słowa będą „y”, „a”, „ya”, „mh”, „k”, „ay”, „h”, „m”, „s”, gdy znaki „centurdowi” " są usunięte.

Kolejność i format zwracanego zestawu nie jest ważna.

Adám
źródło
1
Drugi przypadek jest błędny: „Helo Wrd” daje całkowitą długość 4 za pomocą „!”, „W.” i „w”.
Łukasz
1
@Luke Thanks. Naprawię to. To pokazuje, że potrzebujemy algorytmu, ponieważ wykonywanie go ręcznie jest podatne na błędy.
Adám
A dla trzeciego „centurdowi” daje „y”, „a”, „ya”, „mh”, „k”, „ay”, „h”, „m”, „s” dla całkowitej długości 12.
Łukasz
@Luke Thanks.
Adám
+1 za użycie wyzwania, które pomoże ci w innym wyzwaniu!
Łukasz

Odpowiedzi:

4

Haskell, 138 130 bajtów

import Data.List
c=concat
f i=snd$minimum[(length$c q,s)|s<-subsequences$nub$c i,q<-[map(filter(`notElem`s))i],nub q==q,all(>"")q]

Przykład użycia: f ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]-> "centurdoki".

To podejście z użyciem brutalnej siły.

     s<-subsequences$nub$c i  -- concatenate input i to a single string, remove
                              -- duplicates and make a list of all subsequences
       q<-[map(filter(...))i] -- remove chars appearing in subsequence s from all
                              -- input words, call result q
          nub q==q            -- keep those s where q has no duplicates (i.e. each
                              -- resulting string is unique) and
            all(>"")q         -- contains no empty strings
  (length$c q,s)              -- make pairs from all kept s, where the first element
                              -- is the combines length of all strings in q,
                              -- second element is s itself
snd$minimum                   -- find minimum of those pairs and discard length

Edycja: @Seeq pomógł mi zaoszczędzić 8 bajtów. Dzięki!

nimi
źródło
Co powiesz na to map(#s), żebyś nie musiał odwracać notElem? EDYCJA: A może nie mógłbyś tego po prostu wstawić?
patrz
@Seeq: podczas połączenia za pośrednictwem map(#s), (#)musi być zdefiniowany jako flip (filter . flip notElem). Ale oczywiście inklinacja jest znacznie krótsza. Dzięki!
nimi
2

Pyth, 34

Pobiera dane wejściowe w formacie ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Wskazówki dotyczące gry w golfa są mile widziane, jak zawsze.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ
Łukasz
źródło
2

Pyth, 24 bajty

hols-RNQf<}kJ-RTQ{IJy{sQ

Wypróbuj online. Zestaw testowy.

Pamiętaj, że uruchomienie ostatniego przypadku testowego zajmie trochę czasu.

Pobiera dane wejściowe w postaci tablicy, np ["Day", "day"] .

Kolejny interesujący, który znalazłem i poprawiłem isaacg (także 24 bajty):

-J{sQhlDsM.A#f{ITm-RdQyJ
PurkkaKoodari
źródło
Udało mi się zredukować drugie podejście do 24 bajtów: -J{sQhlDsM.A#f{ITm-RdQyJ tutaj
isaacg