15
\$\begingroup\$

Inspired by this wonderful (based on the number of views and votes) challenge, which, in my humble opinion, has way too few answers.

Given (by any means) a list of strings, return (by any means) a set of letters that, when removed from the given strings, leaves the total length of (what remains of) the strings as small as possible, while keeping each string unique and at least one character long.

Examples:

Given "Day" and "day"; return "ay", because the given strings will be "D" and "d" when the characters "ay" are removed.

Given "Hello World!", "Hello world.", and "Hello world"; return "Helo Wrd" gives because the strings will be "!", "w.", and "w" when the characters "Helo Wrd" (with a space) are removed.

Given "century", "decade", "year", "month", "week", "day", "hour", "minute", and "second"; return "centurdowi" because the given words will be "y", "a", "ya", "mh", "k", "ay", "h", "m", "s" when the characters "centurdowi" are removed.

The order and format of the returned set is not important.

\$\endgroup\$
  • 1
    \$\begingroup\$ Your second case is wrong: "Helo Wrd" gives a total length of 4 with "!", "w." and "w". \$\endgroup\$ – Luke Dec 21 '15 at 20:26
  • 1
    \$\begingroup\$ @Luke Thanks. I'll fix that. That shows that we need an algorithm, as doing it by hand is error prone. \$\endgroup\$ – Adám Dec 21 '15 at 20:31
  • \$\begingroup\$ And for the third one, 'centurdowi' yields 'y', 'a', 'ya', 'mh', 'k', 'ay', 'h', 'm', 's' for a total length of 12. \$\endgroup\$ – Luke Dec 21 '15 at 20:44
  • \$\begingroup\$ @Luke Thanks. \$\endgroup\$ – Adám Dec 21 '15 at 20:54
  • \$\begingroup\$ +1 for using a challenge to help you in another challenge! \$\endgroup\$ – Luke Dec 21 '15 at 21:29
4
\$\begingroup\$

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]

Usage example: f ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"] -> "centurdoki".

This is a brute force approach.

     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 helped me saving 8 bytes. Thanks!

\$\endgroup\$
  • \$\begingroup\$ How about map(#s), so you don't need to flip notElem? EDIT: Or couldn't you just inline it? \$\endgroup\$ – seequ Dec 22 '15 at 9:57
  • \$\begingroup\$ @Seeq: when call via map(#s), (#) must be defined as flip (filter . flip notElem). But of course inlining is far shorter. Thanks! \$\endgroup\$ – nimi Dec 22 '15 at 10:07
2
\$\begingroup\$

Pyth, 34

Takes input in the format ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Golfing tips are appreciated, as always.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ
\$\endgroup\$
2
\$\begingroup\$

Pyth, 24 bytes

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

Try it online. Test suite.

Note that the last test case will take a little while to run.

Takes input in array form, like ["Day", "day"].

Another interesting one I found and isaacg improved (also 24 bytes):

-J{sQhlDsM.A#f{ITm-RdQyJ
\$\endgroup\$
  • \$\begingroup\$ I was able to reduce the second approach to 24 bytes: -J{sQhlDsM.A#f{ITm-RdQyJ here \$\endgroup\$ – isaacg Dec 22 '15 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.