Pemecah Kata Pencarian

13

Saya harus bertanya-tanya kemarin apakah saya bisa menulis sebuah program untuk menyisir pencarian kata yang diberikan dan menghasilkan jawaban. Sebenarnya sangat mudah. Sekarang saya bertanya-tanya seberapa kecil yang bisa kita dapatkan.

Aturan

  • Input pertama Anda adalah string atau kumpulan n baris, yang masing-masing panjangnya n karakter
  • Input kedua Anda adalah daftar kata-kata dalam format apa pun untuk ditemukan dalam teka-teki
  • Semua kata dalam daftar pencarian dijamin berada dalam teka-teki
  • Kata-kata dapat diorientasikan dalam salah satu dari empat arah mata angin, serta secara diagonal baik maju dan mundur
  • Hanya karakter AZ huruf besar yang akan hadir dalam puzzle
  • Kode Anda harus menemukan setiap kata dalam string pencarian, dan menampilkan posisi koordinat huruf awal, di mana 0,0 adalah karakter kiri atas.
  • Jika Anda menemukan lebih dari satu contoh kata yang sama, Anda dapat menanganinya sesuka Anda. Keluarkan beberapa kali, atau hanya sekali, terserah Anda

Contoh / Kasus Uji

Diberikan papan berikut:

ABCD
EFGH
IJKL
MNOP

Dan string pencarian berikut:

ABCD,CGKO,POMN,NJF,AFKP,CFI,LGB,MJGD

Program Anda harus menampilkan yang berikut, dalam urutan apa pun:

ABCD at 0,0
CGKO at 0,2
PONM at 3,3
NJF at 3,1
AFKP at 0,0
CFI at 0,2
LGB at 2,3
MJGD at 3,0

Seperti biasa, jawaban terpendek menang

morpen
sumber
6
Selamat datang di PPCG! Tantangan pertama yang bagus!
AdmBorkBork
2
Serupa , satu-satunya perbedaan nyata adalah inklusi lokasi dalam output.
FryAmTheEggman
@ NL628 Ya, semua kata pencarian dijamin berada dalam teka-teki. Jika ada lebih dari satu kejadian, Anda bisa menampilkannya dua kali atau mengabaikannya yang kedua, terserah Anda.
morpen
@ JonathanAllan Ide bagus. Saya akan memperbaruinya seperti yang Anda sarankan.
morpen
1
@RickHitchcock Ya seharusnya :)
morpen

Jawaban:

4

JavaScript (Node.js) , 154 152 150 141 byte

  • terima kasih kepada Arnauld untuk mengurangi 2 byte

mengembalikan array lokasi (sebelumnya berupa string dengan baris baru)

(b,w)=>w.map(s=>[...b].map((_,p)=>[1,-1,r=b.search`
`,-r,~r,++r,-~r,~r].map(d=>[...s].every((c,i)=>c==b[p+d*i])?s+=" at "+[p/r|0,p%r]:0))&&s)

Cobalah online!

DanielIndie
sumber
3

Python 2 , 213 byte

lambda a,W:[(w,i,j)for w in W for i in R(L(a))for j in R(L(a[0]))for U in R(9)if U-4and g(i,j,U/3-1,U%3-1,a).find(w)==0]
g=lambda i,j,u,v,a,s='':L(a)>i>=0<=j<L(a[0])and g(i+u,j+v,u,v,a,s+a[i][j])or s
L=len;R=range

Cobalah online!

gmengambil lokasi awal i,jdan arah u,vdan melalui rekursi mengekstraksi string yang dimulai di lokasi itu ke arah itu.

fkemudian mengunjungi setiap lokasi awal i,jdan arah U/3-1,U%3-1dan memeriksa setiap kata wuntuk melihat apakah string yang dihasilkan dimulai w.

Chas Brown
sumber
2

Python 3 , 149 147 byte

def g(b,w):h=b.find('\n')+1;return[f'{y} at {i//h},{i%h}'for y in w for i in range(len(b))for d in(1,h+1,h,h-1,-1,~h,-h,1-h)if y==b[i::d][:len(y)]]

Cobalah online!

Versi tidak disatukan

def g(b,w):
    h = b.find('\n') + 1                              # width of a row plus the '\n'
    a = []
    for y in w:                                       # iterate over the words
        for i in range(len(b)):                       #   iterate over the game board
            for d in(1,h+1,h,h-1,-1,~h,-h,1-h):       #     for each possible direction
                if y==b[i::d][:len(y)]:               #       see if the word matches
                    a.append(f'{y} at {i//h},{i%h}')
    return a

Gagasan utamanya adalah b[i::d]memilih sepotong dari papan permainan. Irisan dimulai sebagai posisi idan memanjang ke arah d. Misalnya, d = h+1berkorespondensi dengan diagonal tenggara, sedangkan d = ~h, yang sama dengan -h-1, berkorespondensi dengan diagonal barat laut. [:len(y)] memotong irisan dengan panjang yang sama dengan kata yang dicari.

RootTwo
sumber