Supprimez les lettres tout en gardant les chaînes uniques

15

Inspiré par ce merveilleux défi (basé sur le nombre de vues et de votes), qui, à mon humble avis, a bien trop peu de réponses.

Étant donné (par tous les moyens) une liste de chaînes, renvoyez (par tous les moyens) un ensemble de lettres qui, lorsqu'elles sont supprimées des chaînes données, laisse la longueur totale de (ce qui reste de) les chaînes aussi petite que possible, tout en gardant chacune chaîne unique et longue d'au moins un caractère.

Exemples:

Étant donné "Jour" et "jour"; retourne "ay", car les chaînes données seront "D" et "d" lorsque les caractères "ay" seront supprimés.

Étant donné "Hello World!", "Hello world." Et "Hello world"; return "Helo Wrd" donne car les chaînes seront "!", "w." et "w" lorsque les caractères "Helo Wrd" (avec un espace) seront supprimés.

Étant donné "siècle", "décennie", "année", "mois", "semaine", "jour", "heure", "minute" et "seconde"; retourner "centurdowi" car les mots donnés seront "y", "a", "ya", "mh", "k", "ay", "h", "m", "s" lorsque les caractères "centurdowi " sont enlevés.

L'ordre et le format de l'ensemble retourné ne sont pas importants.

Adam
la source
1
Votre deuxième cas est faux: "Helo Wrd" donne une longueur totale de 4 avec "!", "W". et W".
Luke
1
@Luke Merci. Je vais arranger ça. Cela montre que nous avons besoin d'un algorithme, car le faire à la main est sujet aux erreurs.
Adám
Et pour le troisième, «centurdowi» donne «y», «a», «ya», «mh», «k», «ay», «h», «m», «s» pour une longueur totale de 12.
Luke
@Luke Merci.
2015
+1 pour avoir utilisé un défi pour vous aider dans un autre défi!
Luke

Réponses:

4

Haskell, 138 130 octets

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]

Exemple d'utilisation: f ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]-> "centurdoki".

Il s'agit d'une approche par force brute.

     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 m'a aidé à économiser 8 octets. Merci!

nimi
la source
Que diriez - vous map(#s), si vous n'avez pas besoin de retourner notElem? EDIT: Ou ne pourriez-vous pas simplement l'intégrer?
seequ
@Seeq: lors d'un appel via map(#s), (#)doit être défini comme flip (filter . flip notElem). Mais bien sûr, la doublure est beaucoup plus courte. Merci!
nimi
2

Pyth, 34

Prend la saisie dans le format ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Les conseils de golf sont appréciés, comme toujours.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ
Luc
la source
2

Pyth, 24 octets

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

Essayez-le en ligne. Suite de tests.

Notez que le dernier scénario de test prendra un peu de temps à s'exécuter.

Prend l'entrée sous forme de tableau, comme ["Day", "day"].

Un autre intéressant que j'ai trouvé et isaacg amélioré (également 24 octets):

-J{sQhlDsM.A#f{ITm-RdQyJ
PurkkaKoodari
la source
J'ai pu réduire la deuxième approche à 24 octets: -J{sQhlDsM.A#f{ITm-RdQyJ ici
isaacg