Hapus huruf sambil menjaga string tetap unik

15

Terinspirasi oleh tantangan yang luar biasa ini (berdasarkan jumlah pandangan dan suara), yang, menurut pendapat saya, memiliki terlalu sedikit jawaban.

Diberikan (dengan cara apa pun) daftar string, kembalikan (dengan cara apa pun) satu set surat yang, ketika dihapus dari string yang diberikan, meninggalkan panjang total (apa yang tersisa dari) string sekecil mungkin, sambil menjaga masing-masing string yang unik dan setidaknya satu karakter.

Contoh:

Diberi "Hari" dan "hari"; kembali "ay", karena string yang diberikan akan menjadi "D" dan "d" ketika karakter "ay" dihapus.

Diberi "Hello World!", "Hello world.", Dan "Hello world"; kembali "Helo Wrd" memberi karena string akan menjadi "!", "w.", dan "w" ketika karakter "Helo Wrd" (dengan spasi) dihapus.

Diberi "abad", "dekade", "tahun", "bulan", "minggu", "hari", "jam", "menit", dan "kedua"; kembalikan "centurdowi" karena kata-kata yang diberikan adalah "y", "a", "ya", "mh", "k", "ay", "h", "m", "s" ketika karakter "centurdowi "dihapus.

Urutan dan format set yang dikembalikan tidak penting.

Adm
sumber
1
Kasus kedua Anda salah: "Helo Wrd" memberikan total panjang 4 dengan "!", "W." dan W".
Lukas
1
@ Lukas Terima kasih. Saya akan memperbaikinya. Itu menunjukkan bahwa kita memerlukan algoritma, karena melakukannya dengan tangan adalah kesalahan.
Adám
Dan untuk yang ketiga, 'centurdowi' menghasilkan 'y', 'a', 'ya', 'mh', 'k', 'ay', 'h', 'm', 's' dengan total panjang 12.
Luke
@ Lukas Terima kasih.
Adám
+1 untuk menggunakan tantangan untuk membantu Anda dalam tantangan lain!
Lukas

Jawaban:

4

Haskell, 138 130 byte

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]

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

Ini adalah pendekatan brute force.

     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

Sunting: @Seeq membantu saya menghemat 8 byte. Terima kasih!

nimi
sumber
Bagaimana map(#s), jadi Anda tidak perlu membalik notElem? EDIT: Atau tidak bisakah Anda hanya sebaris itu?
seequ
@Seeq: saat panggilan via map(#s), (#)harus didefinisikan sebagai flip (filter . flip notElem). Tapi tentu saja inlining jauh lebih pendek. Terima kasih!
nimi
2

Pyth, 34

Mengambil input dalam format ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Tips golf sangat dihargai, seperti biasa.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ
Luke
sumber
2

Pyth, 24 byte

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

Cobalah online. Suite uji.

Perhatikan bahwa test case terakhir akan membutuhkan waktu untuk dijalankan.

Mengambil input dalam bentuk array, misalnya ["Day", "day"].

Satu lagi yang menarik yang saya temukan dan isaacg membaik (juga 24 byte):

-J{sQhlDsM.A#f{ITm-RdQyJ
PurkkaKoodari
sumber
Saya bisa mengurangi pendekatan kedua menjadi 24 byte: di -J{sQhlDsM.A#f{ITm-RdQyJ sini
isaacg