Remova as letras mantendo as strings exclusivas

15

Inspirado por esse desafio maravilhoso (baseado no número de opiniões e votos), que, na minha humilde opinião, tem poucas respostas.

Dada (por qualquer meio) uma lista de cadeias, retorne (por qualquer meio) um conjunto de letras que, quando removidas das cadeias fornecidas, deixa o comprimento total (o que resta) das cadeias o menor possível, mantendo cada string exclusiva e com pelo menos um caractere.

Exemplos:

Dado "dia" e "dia"; retorne "ay", porque as seqüências fornecidas serão "D" e "d" quando os caracteres "ay" forem removidos.

Dado "Olá, mundo!", "Olá, mundo." E "Olá, mundo"; return "Helo Wrd" fornece porque as strings serão "!", "w." e "w" quando os caracteres "Helo Wrd" (com um espaço) forem removidos.

Dado "século", "década", "ano", "mês", "semana", "dia", "hora", "minuto" e "segundo"; retorne "centurdowi" porque as palavras fornecidas serão "y", "a", "ya", "mh", "k", "ay", "h", "m", "s" quando os caracteres "centurdowi" " estão removidos.

A ordem e o formato do conjunto retornado não são importantes.

Adão
fonte
1
Seu segundo caso está errado: "Helo Wrd" fornece um comprimento total de 4 com "!", "W". e W".
Lucas
1
@ Luke Obrigado. Eu vou consertar isso. Isso mostra que precisamos de um algoritmo, pois fazê-lo manualmente é propenso a erros.
Adám
E para o terceiro, 'centurdowi' produz 'y', 'a', 'ya', 'mh', 'k', 'ay', 'h', 'm', 's' para um comprimento total de 12.
Lucas
@ Luke Obrigado.
Adám
+1 por usar um desafio para ajudá-lo em outro desafio!
Lucas

Respostas:

4

Haskell, 138 130 bytes

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]

Exemplo de uso: f ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]-> "centurdoki".

Esta é uma abordagem de força bruta.

     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

Edit: @Seeq me ajudou a salvar 8 bytes. Obrigado!

nimi
fonte
Que map(#s)tal, então você não precisa virar notElem? EDIT: Ou você não poderia simplesmente inline?
seequ
@Seeq: quando a chamada via map(#s), (#)deve ser definida como flip (filter . flip notElem). Mas é claro que inlining é muito menor. Obrigado!
nimi
2

Pyth, 34

Recebe entrada no formato ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Dicas de golfe são apreciadas, como sempre.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ
Lucas
fonte
2

Pitão, 24 bytes

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

Experimente online. Suíte de teste.

Observe que o último caso de teste levará um tempo para ser executado.

Recebe entrada em forma de matriz, como ["Day", "day"].

Outro interessante que encontrei e o isaacg melhorou (também 24 bytes):

-J{sQhlDsM.A#f{ITm-RdQyJ
PurkkaKoodari
fonte
Consegui reduzir a segunda abordagem para 24 bytes: -J{sQhlDsM.A#f{ITm-RdQyJ aqui
isaacg