Pecahkan Anagram

9

Lihat juga: Nenek mencintai Ana

Anda akan diberi serangkaian huruf ASCII huruf kecil. Menggunakan file kamus ini (DIPERBARUI), tugas Anda adalah menyelesaikan anagram. Untuk menyelesaikan anagram, Anda harus mengeluarkan semua kata atau grup kata yang dapat dibentuk menggunakan setiap huruf dari string input tepat satu kali, dipisahkan oleh baris baru. Grup dengan kata yang sama dalam urutan yang berbeda tidak unik dan tidak boleh di-output secara terpisah; Namun, urutan kata-katanya tidak masalah . Urutan solusi keluaran juga tidak masalah . Jika input tidak dapat membentuk kata, tidak menghasilkan apa-apa.

Beberapa kasus uji yang berguna:

Input:  viinlg
Output: living

Input:  fceodglo
Output: code golf

Input:  flogflog
Output: golf golf

Input:  ahwhygi
Output: highway
        high way

Input:  bbbbbb
Output: 

Aturan / peringatan:

  • Anda dapat mengakses daftar kamus dengan cara apa pun yang Anda suka. Argumen baris perintah, stdin, membaca dari file, atau membaca dari internet semuanya dapat diterima.

  • Input akan terdiri dari huruf ASCII huruf kecil saja. Anda tidak diharuskan untuk menampilkan hasil dalam kasus tertentu.

  • Anda tidak akan diberi string yang sudah membentuk kata yang valid (namun, Anda dapat diberikan string yang membentuk banyak kata, seperti bluehouse).

  • Trailing newlines diperbolehkan tetapi tidak diperlukan.

  • Celah standar berlaku.

Ini adalah . Kode terpendek dalam byte menang. Semoga berhasil!

menyebarkan
sumber
Haruskah kita menggunakan 1 ruang untuk memisahkan set kata atau pemisah non-huruf sudah mencukupi?
Erik the Outgolfer
@EriktheOutgolfer Untuk memisahkan set kata, pemisah apa pun baik-baik saja; namun Anda masih harus memisahkan kata-kata dalam satu solusi dengan spasi.
berhamburan
@Christian Rules mengatakan Anda harus memisahkan set kata dengan baris baru.
Erik the Outgolfer
@EriktheOutgolfer Lalu mengapa Anda bertanya "Haruskah kita menggunakan 1 ruang untuk memisahkan set kata"? Pertanyaan Anda membingungkan saya, dan seharusnya tidak ada alasan untuk lebih memilih apa pun daripada baris baru untuk memisahkan set. Saya akan mengatakan tetap pada spec.
bubar

Jawaban:

2

Python 2 , 341 327 337 320 byte

Solusi ini mengasumsikan kamus disimpan dalam variabel wsebagai serangkaian string. Set pertama combinationstidak perlu menggunakan combinations_with_replacement, tetapi menggunakan yang terakhir menghemat byte.

from itertools import*
d,o,j,c={},sorted,''.join,combinations_with_replacement
s,w=o(raw_input()),input()
l=len(s)
r=range(l)
for x in w:d.setdefault(j(o(x)),[]).append(x)
b=set(chain(*[d[j(x)]for y in r for x in c(s,y+1)if j(x) in d]))
print'\n'.join(' '.join(x)for y in r for x in c(b,y+1)if(len(j(x)),o(j(x)))==(l,s))

Cobalah online!

Input - Kata anagram yang diikuti oleh kamus kata sebagai satu set:

anagram_word
{'entry1', 'entry2', ...., 'entryN'}

Edit: Input yang Diperbarui.

Sunny Patel
sumber
1

Python 3 , 248 202 byte

from itertools import*
A=set()
def f(s,*G,i=1,A=A):
 if' '>s:A|={' '.join(sorted(G))}
 for _ in s:s[:i]in S and f(s[i:],s[:i],*G);i+=1
I,*S=iter(input,'')
for p in permutations(I):f(''.join(p))
print(A)

Cobalah online!

Masukan adalah sebagai berikut:

word_input
dic_entry_1
dic_entry_2
....
dic_entry_N
                 # <<< empty line + \n

Mempercepatnya:

Untuk tujuan pengujian, jika Anda mengubah dari I,*S=iter(input,'')menjadi I=input();S=set(iter(input,'')), runtime akan berkurang secara drastis dan hasilnya akan sama.

Penjelasan:

Di setiap permutasi input, ia mencoba untuk membagi permutasi secara rekursif di semua lokasi yang mungkin, mulai dari kiri ke kanan, tanpa melewatkan huruf, dengan kata-kata yang ada di kamus. Jika kombinasi split cocok dengan semua permutasi input, kata-kata split diurutkan dan ditambahkan ke setyang akan dicetak pada dan dari evaluasi.

Felipe Nardi Batista
sumber
1

Javascript, 139 137 129 Bytes

-2 Bytes berkat @FelipeNardiBatista

-8 Bytes terima kasih sudah membaca dokumen;)

k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])}

Dimasukkan ke dalam kamus sebagai input dalam bentuk array string.

var arr = ["living", "code", "golf", "highway", "high", "way"];

var _=
k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])};

console.log(_(arr)("viinlg"));
console.log(_(arr)("fceodglo"));

Penjelasan:

Untuk setiap kata dalam kamus, periksa apakah setiap huruf terkandung dalam kata yang dipilih, sekaligus menghapusnya dari kata tersebut. Di akhir setiap entri kamus, kembalikan kata ke kondisi tidak berubah untuk memeriksa kecocokan lebih lanjut.

Terima kasih
sumber
@FelipeNardiBatista Anda benar, saya lupa golf nama itu. Terima kasih :)
Hankrecords