Temukan trenggiling terpendek dari daftar kata

10

Sebuah pangram adalah string yang berisi setiap surat a- zdari bahasa Inggris alfabet, kasus-sensitif. (Tidak apa-apa jika pangram berisi lebih dari satu salinan surat, atau jika berisi karakter bukan huruf di samping surat-surat itu.)

Tulis program atau fungsi yang inputnya adalah daftar string, dan yang menghasilkan satu atau lebih string yang memiliki properti berikut:

  • Setiap string keluaran harus berupa pangram.
  • Setiap string output harus dibentuk dengan menggabungkan satu atau lebih string dari daftar input, dipisahkan oleh spasi.
  • Setiap string keluaran harus yang terpendek, atau diikat untuk yang terpendek, di antara semua string dengan properti ini.

Banyak program akan memilih untuk hanya menghasilkan satu string; Anda hanya ingin menghasilkan lebih dari satu string jika Anda harus menulis kode tambahan untuk membatasi output.

Anda dapat berasumsi bahwa input tidak mengandung karakter atau spasi yang tidak dapat dicetak, dan tidak ada kata di dalamnya yang lebih dari (26 kali logaritma natural dari panjang daftar) karakter. (Namun, Anda tidak boleh berasumsi bahwa input hanya berisi huruf, atau hanya huruf kecil; tanda baca dan huruf besar sepenuhnya mungkin.)

Input dan output dapat diberikan dalam format apa pun yang masuk akal. Untuk menguji program Anda, saya sarankan menggunakan dua test case: kamus kata-kata bahasa Inggris (kebanyakan komputer memiliki satu), dan case berikut (yang pangram sempurna (26 huruf) tidak mungkin, jadi Anda harus menemukan satu berisi surat rangkap):

abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz

Anda harus menyertakan sampel hasil program Anda bersama dengan kiriman Anda. (Ini mungkin berbeda untuk orang yang berbeda karena menggunakan daftar kata yang berbeda.)

Kondisi kemenangan

Ini adalah tantangan . Pemenangnya adalah program terpendek (dalam byte) yang berjalan dalam waktu polinomial . (Rangkuman untuk orang-orang yang tidak tahu apa artinya: jika Anda menggandakan ukuran daftar kata, program harus menjadi lebih lambat tidak lebih dari faktor konstan. Namun, faktor konstan yang dipermasalahkan bisa sebesar Anda. seperti. Misalnya, itu berlaku untuk menjadi empat kali lebih lambat, atau delapan kali lebih lambat, tetapi tidak untuk itu menjadi lebih kecil oleh faktor panjangnya daftar kata; faktor melalui mana ia menjadi lebih lambat harus dibatasi.)


sumber
Saat menentukan kerumitan, dapatkah kita menggunakan fakta bahwa setiap kata paling panjang 26 huruf? Bahwa ukuran alfabet adalah konstanta 26?
xnor
Iya. Saya menempatkan batasan pada input di sana sebagian untuk membuat kompleksitas lebih mudah untuk didefinisikan / dihitung.
Saya pikir ini berjalan ke teknis. Jika Anda mengabaikan kata-kata input berulang, ada paling banyak 27 ^ 26 kata input yang mungkin, dan paling banyak 2 ^ (27 ^ 26) subset yang mungkin dari mereka sebagai input mungkin. Ini sangat besar tetapi konstan. Jadi, setiap program pada himpunan terbatas ini adalah waktu konstan, dengan konstanta menjadi jumlah langkah maksimum yang diambil atas semua input yang mungkin.
xnor
Saya tidak mengatakan tidak ada duplikasi kata dalam input. Saya kira Anda dapat menjalankan program dalam waktu "teknis" O (n) dengan memfilter tanda baca dan mendupuplikasi input terlebih dahulu, meskipun (atau lebih mungkin O (n log n), yang akan menggunakan memori jauh lebih sedikit daripada radix deduplicate akan). Maka Anda harus kembali dari versi yang difilter ke daftar kata asli. Anda tidak dapat mengklaim waktu polinomial yang dimaksud kecuali Anda benar-benar melewati semua langkah itu!
Saya lupa tentang non-surat. Bisakah kita menganggap ini ASCII, atau dalam batas tertentu? Jika demikian, saya pikir algoritma apa pun yang dimulai dengan deduplicating dapat mengklaim sebagai polinomial-time.
xnor

Jawaban:

3

Ruby 159 (berulang-ulang)

Rubi 227 220 229 227 221 (rekursif)

Solusi iteratif baru (berdasarkan algoritma yang dijelaskan oleh @Niel):

c={('A'..'Z').to_a=>""}
while l=gets
d=c.clone
c.map{|k,v|j=k-l.upcase.chars
w=v+" "+l.strip
d[j]=w if !c[j]||c[j].size<w.size}
c=d
end
x=c[[]]
p x[1..-1] if x

Solusi rekursif lama:

W=[]
while l=gets
W<<l.strip
end
I=W.join(" ")+"!!"
C={[]=>""}
def o(r)if C[r]
C[r]
else
b=I
W.map{|x|s=r-x.upcase.chars
if s!=r
c=x+" "+o(s)
b=c if c.size<b.size
end}
C[r]=b
end
end
r=o ('A'..'Z').to_a
p r[0..-2] if r!=I

Pengukuran byte didasarkan pada meninggalkan baris baru terakhir dalam file, yang tidak masalah ruby 2.3.1p112. Hitungan byte naik kembali setelah memperbaiki bug kecil (menambahkan.downcase .upcase untuk case-insensitivity seperti yang dipersyaratkan oleh pernyataan masalah).

Ini adalah versi sebelumnya dari sebelum memperpendek pengidentifikasi dan semacamnya:

#!/usr/bin/env ruby

$words = [];

while (line=gets)
  $words << line[0..-2];
end

$impossible = $words.join(" ")+"!!";

$cache = {};

def optimize(remaining)
  return $cache[remaining] if ($cache[remaining]);
  return "" if (remaining == []);

  best = $impossible;

  $words.each{|word|
    remaining2 = remaining - word.chars;
    if (remaining2 != remaining)
      curr = word + " " + optimize(remaining2);
      best = curr if (curr.length < best.length);
    end
  };

  $stderr.puts("optimize(#{remaining.inspect})=#{best.inspect}");

  return $cache[remaining] = best;
end

result = optimize(('a'..'z').to_a);

puts(result[0..-1]);

Bagaimana cara kerjanya? Itu pada dasarnya mempertahankan satu set karakter masih untuk menutupi dan hanya berulang pada kata jika itu akan mengurangi set terbuka. Selain itu, hasil rekursi juga dicatat. Setiap subset dari 2 ^ 26 sesuai dengan entri tabel memoisasi. Setiap entri tersebut dihitung dalam waktu sebanding dengan ukuran file input. Jadi semuanya O(N)(di mana Nukuran file input), meskipun dengan konstanta besar.

DepresiDaniel
sumber
1

JavaScript (ES6), 249 248 byte, mungkin bersaing

a=>a.map(w=>w.replace(/[a-z]/gi,c=>b|=1<<parseInt(c,36)-9,b=0,l=w.length)&&(m.get(b)||[])[0]<l||m.set(b,[l,w]),m=new Map)&&[...m].map(([b,[l,w]])=>m.forEach(([t,s],e)=>(m.get(e|=b)||[])[0]<=t+l||m.set(e,[t+l+1,s+' '+w])))&&(m.get(-2^-1<<27)||[])[1]

Penjelasan: Mengubah array dengan mengubah huruf menjadi bitmask, menyimpan hanya kata terpendek untuk setiap bitmask di peta. Kemudian beralih di atas salinan peta, tambahkan peta dengan menambahkan setiap bitmask gabungan jika string yang dihasilkan akan lebih pendek. Akhirnya kembalikan string yang disimpan untuk bitmap yang sesuai dengan pangram. (Kembali undefinedjika tidak ada string seperti itu.)

Neil
sumber
Menarik. Bisakah Anda menjelaskan lebih lanjut tentang cara kerjanya dan, jika tersedia, memposting kode yang tidak disatukan?
DepressedDaniel
1
Ini harus menjadi entri yang valid / bersaing. Saya pikir ini benar-benar berjalan di O ( n log n ), sebenarnya! (Peta memiliki batas keras entri 2²⁶, dan dengan demikian tidak muncul dalam kompleksitas; dengan demikian satu-satunya waktu yang dihabiskan adalah waktu membaca input.)
Saya baru saja membaca deskripsi dan saya mendapatkan cara kerjanya sekarang. Rapi. +1 ... Hmm, kapan itu memutuskan untuk berhenti mencoba menambah peta dengan mempertimbangkan pasangan? Itu harus terus berjalan sampai relaksasi tidak mungkin.
DepressedDaniel
@DepressedDaniel Untuk setiap bitmask yang diekstrak dari daftar kata asli, ia memeriksa semua pangram parsial yang telah ditemukan sejauh ini, dan apakah menambahkan kata itu menciptakan pangram yang lebih pendek daripada yang saat ini dikenal sebagai bitmask gabungan.
Neil
@ ais523 Untuk input besar (> 1000 kata), sebagian besar waktu sepertinya dihabiskan untuk bertukar. Saya mencoba beralih dari Peta ke Array dan bahkan lebih lambat!
Neil
-1

Python 3, 98 , 94 , 92 byte

print([s for s in input().split()if sum([1 for c in range(65,91)if chr(c)in s.upper()])>25])

Iterasi melalui representasi ASCII dari alfabet dan tambahkan 1 ke daftar jika huruf ditemukan dalam string. Jika jumlah daftar lebih besar dari 25, itu berisi semua huruf alfabet dan akan dicetak.

Erich
sumber
Saya pikir Anda dapat menghapus spasi antara (' ')dan if. Anda juga dapat mengubah ord(i) in range(65,91)ke 91>x>=65. Juga, apa kompleksitasnya?
NoOneIsHere
1
Apa kompleksitas dari solusi ini? Hal ini diperlukan untuk jawaban berada di kompleksitas polinomial, jika tidak maka non-bersaing.
NoOneIsHere
Maaf, saya pikir itu O (n), karena daftar input panjangnya dapat bervariasi tetapi
Erich
Maaf, saya pikir itu O (n), karena daftar input panjangnya bisa bervariasi tetapi loop kedua selalu berjalan dari 65 menjadi 90. Tapi saya belum mengujinya.
Erich
Tidak yakin ini memuaskan "Setiap string keluaran harus yang terpendek, atau terikat untuk yang terpendek, di antara semua string dengan properti ini."
DepressedDaniel