Удалить буквы, сохраняя уникальность строк

15

Вдохновленный этой замечательной (основанной на количестве просмотров и голосов) проблемой, на которую, по моему скромному мнению, слишком мало ответов.

Учитывая (любым способом) список строк, возвращайте (любыми средствами) набор букв, который при удалении из заданных строк оставляет как можно меньшую общую длину (что осталось от) строк, сохраняя при этом каждый уникальная строка длиной не менее одного символа

Примеры:

Даны «День» и «День»; верните «ay», потому что заданные строки будут «D» и «d», когда символы «ay» удалены.

Даны "Hello World!", "Hello world." И "Hello world"; return «Helo Wrd» возвращает, потому что строки будут «!», «w.» и «w», когда символы «Helo Wrd» (с пробелом) удалены.

Даны "век", "десятилетие", "год", "месяц", "неделя", "день", "час", "минута" и "секунда"; вернуть "centurdowi", потому что заданные слова будут "y", "a", "ya", "mh", "k", "ay", "h", "m", "s", когда символы "centurdowi" "удалены.

Порядок и формат возвращаемого набора не важны.

Адам
источник
1
Ваш второй случай неверен: «Helo Wrd» дает общую длину 4 с «!», «W.» и "ш".
Люк
1
@ Люк Спасибо. Я исправлю это. Это показывает, что нам нужен алгоритм, так как выполнение его вручную подвержено ошибкам.
Адам
А для третьего 'centurdowi' выдает 'y', 'a', 'ya', 'mh', 'k', 'ay', 'h', 'm', 's' для общей длины 12.
Лука
@ Люк Спасибо.
Адам
+1 за использование задачи, чтобы помочь вам в другой игре!
Люк

Ответы:

4

Haskell, 138 130 байт

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]

Пример использования: f ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]-> "centurdoki".

Это подход грубой силы.

     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

Редактировать: @Seeq помог мне сэкономить 8 байтов. Благодарность!

Ними
источник
Как насчет того map(#s), чтобы тебе не нужно было переворачивать notElem? РЕДАКТИРОВАТЬ: Или вы не могли просто вставить это?
Seequ
@Seeq: когда вызов через map(#s), (#)должен быть определен как flip (filter . flip notElem). Но, конечно, встраивание гораздо короче. Благодарность!
Ними
2

Пиф, 34

Принимает ввод в формате ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Советы по гольфу приветствуются, как всегда.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ
Люк
источник
2

Pyth, 24 байта

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

Попробуйте онлайн. Тестирование.

Обратите внимание, что последний контрольный пример займет некоторое время для запуска.

Принимает ввод в виде массива, как ["Day", "day"].

Еще один интересный, который я нашел и улучшил isaacg (также 24 байта):

-J{sQhlDsM.A#f{ITm-RdQyJ
PurkkaKoodari
источник
Мне удалось сократить второй подход до 24 байт: -J{sQhlDsM.A#f{ITm-RdQyJ здесь
isaacg