Teka-teki Pencarian Kata

29

Diberikan teks persegi panjang sebagai teka-teki pencarian kata dan string pencarian, tentukan apakah teks tersebut berisi string pencarian. String pencarian dapat muncul:

  • secara horizontal, vertikal atau diagonal
  • maju atau mundur

Anda dapat menulis fungsi atau program dan mengambil dua string sebagai input melalui argumen fungsi, ARGV atau STDIN. Output harus menjadi truthy atau falsy hasil yang baik dapat kembali dari fungsi atau ditulis ke stdout.

Asumsikan bahwa teks tersebut akan berisi karakter ASCII yang dapat dicetak secara acak (kode hex 20 hingga 7E) dan karakter pemisah baris. Huruf peka huruf besar-kecil. Anda dapat mengasumsikan bahwa teks input berbentuk persegi panjang, yaitu semua baris memiliki panjang yang sama. Anda dapat apakah input diakhiri dengan baris baru atau tidak (jika itu penting untuk kiriman Anda).

Ini adalah kode golf, jawaban terpendek (dalam byte) menang.

Contohnya

Menggunakan kisi ini dari artikel Wikipedia tentang pencarian kata sebagai input pertama:

WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

string pencarian berikut harus menghasilkan hasil yang benar atau salah masing-masing:

Truthy: RANDOM, VERTICAL, HORIZONTAL, WORDSEARCH, WIKIPEDIA, TAIL
Falsy:  WordSearch, CODEGOLF, UNICORN

Atau, gunakan teks input ini

Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur.

Kami mendapatkan hasil pencarian berikut (menggunakan kutipan sekarang, karena ada spasi di beberapa string pencarian):

Truthy: "Lorem", "mine", "uma bop", "tuetdod", "snol,a", "texas", "pii.d  v", "vexta"
Falsy:  "lorem", "wordsearch", "pii.d v", "mute"
Martin Ender
sumber

Jawaban:

7

CJam, 46 37 byte

qN%{_zW%__,N**2$2$+,)/z\}4*]:+N*eas#)

Membaca kotak dari STDIN dan kata sebagai argumen baris perintah. Mencetak bilangan bulat positif untuk kecocokan dan 0 untuk tidak cocok.

Dengan biaya dua byte tambahan, kedua string (kata, linefeed, kisi) dapat dibaca dari STDIN:

qN%(\{_zW%__,N**2$2$+,)/z\}4*](\:+N*\#)

Anda dapat mencoba versi ini secara online dengan juru bahasa CJam .

Contoh dijalankan

$ for W in Lorem mine uma\ bop tuetdod snol,a texas pii.d\ \ v vexta WordSearch CODEGOLF UNICORN; do echo -e "$(cjam wordsearch.cjam "$W" < grid)\t$W"; done
1       Lorem
3085    mine
2055    uma bop
5142    tuetdod
3878    snol,a
1426    texas
5371    pii.d  v
2536    vexta
0       WordSearch
0       CODEGOLF
0       UNICORN

Latar Belakang

Asumsikan input adalah kisi berikut:

ABCD
EFGH
IJKL

Memisahkan pada linefeeds, kami mendapatkan array berikut:

A := [
         "ABCD"
         "EFGH"
         "IJKL"
     ]

Itu mencakup kata-kata Timur (kata-kata dari kiri ke kanan).

Sekarang, kita bergabung dengan elemen Amenggunakan string len(A)linefeeds sebagai pemisah:

"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

Kemudian, kami memotong string yang dihasilkan dalam potongan panjang len(A) + len(A[0]) + 1:

[
    "ABCD⏎⏎⏎E"
    "FGH⏎⏎⏎IJ"
    "KL"
]

Jika kami "zip" array (transpos baris dan kolom), kami memperoleh:

[
    "AFK"
    "BGL"
    "CH"
    "D⏎"
    "⏎⏎"
    "⏎⏎"
    "I⏎"
    "EJ"
]

Itu mencakup kata-kata Tenggara.

Jika kami membuka zip A dan membalikkan urutan baris hasil, kami memperoleh:

[
    "DHL"
    "CGK"
    "BFJ"
    "AEI"
]

Itu mencakup Selatan dan - setelah mengulangi proses untuk diagonal - kata-kata Barat Daya.

Zip dan membalikkan lagi, kami memperoleh:

[
    "LKJI"
    "HGFE"
    "DCBA"
]

Itu mencakup Barat dan - setelah mengulangi proses untuk diagonal - kata-kata Barat Laut.

Zip dan membalikkan sekali lagi, kami memperoleh:

[
    "IEA"
    "JFB"
    "KGC"
    "LHD"
]

Itu mencakup Utara dan - setelah mengulangi proses untuk diagonal - kata-kata Timur Laut.

Bagaimana itu bekerja

Kode tidak seperti yang dijelaskan pada bagian sebelumnya, dengan dua perbedaan kecil:

  • Ritsleting dan terbalik sekali di awal.
  • Itu dihitung len(A) + len(A[0])sebagai len(A + zip(A)).

Akhirnya, ia bergabung dengan semua baris dari semua array yang dihasilkan menggunakan linefeed sebagai pemisah dan mencari kata dalam string yang dihasilkan.

qN%                                   " A := split(input(),'\n')                          ";
   {                    }4*           " Do 4 times:                                       ";
    _zW%                              "   B := reverse(zip(A))                            ";
        __,N**                        "   C := B.join(len(B) * '\n')                      ";
              2$2$+,)/z               "   D := zip(C.chunks(len(A + B) + 1))              ";
                       \              "   A := B                                          ";
                           ]          " Collect all values of A and D in an array R.      ";
                            :+        " R := flatten(R)                                   ";
                              N*      " R := R.join('\n')                                 ";
                                eas   " I := flatten(ARGV)                                ";
                                   #) " print R.index(I) + 1                              ";
Dennis
sumber
7

Jawa: 183 211 321

boolean s(char[]w,char[]s){int j,z,a=s.length,i=a*9,f=1,q=0;for(;s[q++]>10;);for(;i-->0;)for(j=w.length,z=i/9;i%9!=4&j-->0&z>=0&z<a&&s[z]==w[j];z+=q*(i/3%3)+i%3-q-1)f*=j;return f==0;}

Kekuatan kasar dasar. Tidak banyak yang bisa dikatakan, kurasa. Input adalah jarum pertama dan tumpukan jerami kedua. Diasumsikan kisi diakhiri oleh baris baru .

Versi yang sedikit lebih mudah dibaca dengan test case ditunjukkan:

public class WordSearch {
    static String grid = "WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH";
    static String search = "RANDOM";

    public static void main(String[] args) {
        System.out.println(new WordSearch().s(search.toCharArray(),grid.toCharArray()));
    }

    boolean s(char[]w,char[]s){
        int j,z,a=s.length,i=a*9,f=1,q=0;
        for(;s[q++]>10;);
        for(;i-->0;)
            for(j=w.length,z=i/9;
                i%9!=4&j-->0&z>=0&z<a&&s[z]==w[j];
                z+=q*(i/3%3)+i%3-q-1)
                f*=j;
        return f==0;
    }
}
Geobit
sumber
if(e<1)return 1>0;bisa return e<1;bukan?
FryAmTheEggman
@FryAmTheEggman Tidak, itu akan kembali setelah menemukan kegagalan pertama, sehingga tidak akan mencari seluruh kotak.
Geobits
1
Ah maaf, tersesat di sana; _;
FryAmTheEggman
4
Keluar dua untuk loop bisa runtuh ke dalam satu bukannya sehingga Anda akan melakukan i=a*9,dan for(;i-->0;)kemudian z=i/9;dan i%a!=4&dan sebagainya?
Will
1
Wow, ini sangat mirip dengan milikku. Dan saya hanya meliriknya setelah saya mulai. Saya tidak meluangkan waktu untuk melihat cara kerjanya. +1.
Level River St
6

JavaScript (E6) 111 116

Brute force mencari setiap karakter di segala arah - bermain golf semampu saya

F=(b,w)=>
  [1,-1,r=b.search('\n'),-r,++r,-r,++r,-r].some(d=>
    [...b].some((_,p)=>
      [...w].every(c=>c==b[p+=d],p-=d)
    )
  )

Uji di konsol FireFox / Firebug

;["RANDOM", "VERTICAL", "HORIZONTAL", "WORDSEARCH", "WIKIPEDIA", "TAIL",
"WordSearch", "CODEGOLF", "UNICORN"]
.forEach(w=>console.log('\n'+ w +' -> '+
  F("WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH",w)))

Keluaran

RANDOM -> true
VERTICAL -> true
HORIZONTAL -> true
WORDSEARCH -> true
WIKIPEDIA -> true
TAIL -> true
WordSearch -> false
CODEGOLF -> false
UNICORN -> false
edc65
sumber
5

Python, 175

Tidak terlalu terinspirasi, tapi begini:

def s(h,n):
 l=h.find('\n')+2;h+='\n'*l;L=i=len(h)
 while i>0:
  i-=1
  for d in[-l,1-l,2-l,-1,1,l-2,l-1,l]:
    j=i;m=len(n)
    for c in n:m-=c==h[j%L];j+=d
    if m<1:i=-1
 return-i

Argumen pertama adalah tumpukan jerami, kedua adalah jarum.

Elo
sumber
Saya pikir Anda dapat menyimpan 6 karakter dengan menggunakan h,n=input()dan print. Juga, apakah ini bekerja dengan input non-square? (m = len (n)? Saya akui tidak sepenuhnya memahami apa yang Anda lakukan, jadi saya mungkin sepenuhnya salah!)
FryAmTheEggman
@FryAmTheEggman: Ya, ia bekerja dengan input nonsquare.
Ell
1
Beberapa optimasi Python standar: while i>0ke while i:(karena itidak pernah bisa menjadi negatif), if m<1:i=-1hingga i-=m<1.
xnor
1
@xnor Saya pikir Anda mungkin memiliki salah membaca if m<1:i=-1sebagai if m<1:i-=1sebagai satu pun dari mereka akan bekerja karena ia adalah setting imenjadi negatif.
FryAmTheEggman
@FryAmTheEggman Oh, ya, saya benar-benar salah membaca itu.
xnor
5

Bash + coreutils, 214 169 byte

r()(tee >(rev) $@)
t()(eval paste -d'"\0"' `sed 's/.*/<(fold -1<<<"&")/'`)
d()(while IFS= read l;do echo "$a$l";a+=_;done|t)
r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep -q "$1"

Menggunakan 3 fungsi transformasi r, tdan duntuk membalik, mengubah posisi dan pergeseran diagonal, dalam semua kombinasi yang diperlukan.

Pembaruan - rfungsi sekarang menghasilkan keluaran terbalik dan tidak terbalik untuk golfiness ekstra

Input melalui argumen commandline - string pencarian, diikuti oleh blok pencarian kata persegi panjang (baris baru).

Output adalah kode status keluar shell yang benar secara idiomatis - 0 berarti BENAR dan 1 berarti SALAH.

Keluaran:

$ for w in "Lorem" "mine" "uma bop" "tuetdod" "snol,a" "texas" "pii.d  v" "vexta" ; do ./ws.sh "$w" "Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur."; echo $?; done
0
0
0
0
0
0
0
0
$ for w in WordSearch CODEGOLF UNICORN ; do ./ws.sh "$w" "Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur."; echo $?; done
1
1
1
$ 
Trauma Digital
sumber
1. Saya akan menyarankan T()(tee >(r) $@), tapi itu lebih baik. 2. Saya tidak berpikir saya pernah melihat sintaks fungsi itu sebelumnya. 3. Mengingat string non-kosong benar dan string kosong palsu, saya pikir Anda dapat menghilangkan -q.
Dennis
Jika Anda mendefinisikan r()(tee >(rev) $@), r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep "$1"harus bekerja juga.
Dennis
Saya belum menguji apa-apa lagi, tetapi dua test case dalam pertanyaan diperiksa ketika saya mencoba.
Dennis
@ Dennis Nice - ya itu berfungsi sekarang. Saya memeriksa dengan Martin - dia ingin -qtetap.
Digital Trauma
5

C, 163

f(char*h,char*n){int i,j,d,p,y=0,l=strlen(h),w=strchr(h,10)-h+1;for(i=l*9;i--;y+=d&&!n[j]){p=i/9;d=i%9/3*w-w+i%3-1;for(j=0;p>=0&p<l&h[p]==n[j];j++)p+=d;}return y;}

Tidak ada pengaturan ulang grid, saya cukup mencoba setiap huruf awal di setiap arah, dan berjalan sepanjang sampai saya lari dari grid atau menemukan ketidakcocokan.

Saya mengambil keuntungan dari kenyataan bahwa string C berakhir dalam byte nol. Karena tidak ada nol byte di grid, SELALU akan ada ketidakcocokan. Tetapi jika ketidakcocokan terjadi pada byte nol, kami tahu kami telah menemukan ujung string yang akan dicari, dan merekamnya sebagai kecocokan.

Tidak digabungkan dalam program uji

char h[]="WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH\n";

f(char*h,char*n){                                   //haystack,needle
  int i,j,d,p,y=0,l=strlen(h),w=strchr(h,10)-h+1;   //l=length of whole grid. w=width of row, including terminal newline ASCII 10
  for(i=l*9;i--;){                                  //for each start letter and direction
    p=i/9;                                          //pointer to start letter
    d=i%9/3*w-w+i%3-1;                              //9 possible values of direction vector {-w,0,w}+{-1,0,1}
    for(j=0;p>=0&p<l&h[p]==n[j];j++)p+=d;           //walk p in the direction defined by d until we walk off the top or bottom of the grid or a mismatch is fount
    y+=d&&!n[j];                                    //if we got all the way to the terminal 0, record it as a hit. If d=0, don't record as this is an invalid direction.
  }
  return y;   
}

main(int c, char**v){
  printf("%d",f(h,v[1]));  
}

Keluaran

Perhatikan bahwa fungsi ini akan mengembalikan jumlah total dari string yang dicari dalam kisi. Jadi untuk ODitu mengembalikan 6. Jika tidak ada insiden ditemukan itu mengembalikan 0 yang merupakan satu-satunya nilai falsy dalam C. Mengubah ke y|=d*!n[j]akan menyimpan satu karakter tetapi kehilangan fungsi ini.

$ ./a UNICORN
0

$ ./a CODEGOLF
0

$ ./a WordSearch
0

$ ./a RANDOM
1

$ ./a WORDSEARCH
1

$ ./a VERTICAL
1

$ ./a HORIZONTAL
1

$ ./a WIKIPEDIA
1

$ ./a TAIL
1

$ ./a OD
6
Level River St
sumber
5

C # - 218 197 186 bytes

Fungsi C # yang mengambil 2 string, pertama kata yang dicari, kemudian grid dengan feed baris ( \n) di antara baris. Segalanya menjadi putus asa sekarang ... begitu susah payah pada kenyataan bahwa edit saya sebelumnya tidak bekerja!

Kode golf:

bool F(string D,string S){int l=S.Length,i=l*13,r,p;for(S+="\n";i-->l*5;i=r<0?r:i)for(r=D.Length,p=i%l;p>-1&p<l&r-->0&&D[r]==S[p];p+=(S.IndexOf('\n')+1)*(i/l%9/3-1)+i/l%3-1);return i<0;}

Kurang golf dengan kode tes:

class P
{
    static void Main()
    {
        System.Console.WriteLine(new P().F(System.Console.ReadLine(),System.Console.In.ReadToEnd())?"Truthy":"Falsy"); // because why not
    }

    bool F(string D,string S)
    {
        int l=S.Length,i=l*13,r,p;

        for(S+="\n";i-->l*5;i=r<0?r:i) // for each cell/direction
            for(r=D.Length,p=i%l;p>-1&p<l&r-->0&&D[r]==S[p];p+=(S.IndexOf('\n')+1)*(i/l%9/3-1)+i/l%3-1); // test against string (backwards)

        return i<0;
    }
}
VisualMelon
sumber
4

Haskell - 173

Alih-alih mencari langsung di grid, saya mengubah grid dengan cara yang berbeda dan mencocokkan kata dengan setiap baris dari grid baru.

Sebagai contoh,

G1    G2    G3       G4   G5

abcd  aA1   abcd     a..  ..1
ABCD  bB2   .ABCD    bA.  .A2
1234  cC3   ..1234   cB1  aB3
      dD4            dC2  bC4
                      D3  cD
                       4  d

Cari kata di setiap baris G1, G2, G4 dan G5, lalu selesai. Perhatikan bahwa G3 tidak digunakan, saya mempostingnya di sini hanya untuk ilustrasi.

Ide serupa diterapkan untuk mencari maju dan mundur: cukup cari kata asli dan kata terbalik.

Jadi sekarang kami telah mencari 8 arah. Inilah kodenya, yang kebenarannya diverifikasi oleh skrip lain .

import Data.List
v=reverse
t=transpose
y=any
d r=zipWith(++)(scanr(\_->('\n':))[]r)r
g r w=y(y$y((==w).take(length w)).tails)[r,t r,t.d$r,t.d.v$r]
f r w=y(g(lines r))[w,v w]

Fungsi fadalah apa yang kita inginkan dan argumennya radalah string persegi panjang, wadalah kata yang dicari.

sinar
sumber
4

Python 2 - 246 259 275 308 298 297 294 313 322

w,s=input()
r=range
d='\n'
I=''.join
w=w.split(d)
t,u=len(w),len(w[0])
v=d.join([I(x)for x in zip(*w)]+[d]+[I([w[i+j][i]for i in r(min(u,t-j))])+d+I([w[i][i+j]for i in r(min(t,u-j))])for j in r(max(t,u))]+[d]+w)
print s in v or s[::-1]in v

Terima kasih kepada Will atas bantuannya dalam berurusan dengan cetak dan menentukan bergabung.

Berkat kereta api bawah tanah untuk mengingatkan saya pada ruang golf dengan benar; p

Diperbaiki untuk pertandingan yang buruk berkat menggunakan ',' sebagai pembatas.

Tampaknya cara terbaik untuk bermain golf adalah dengan menambahkan banyak scroll horizontal.

Masukan sebagai spasi kosong bang baris batas baru dalam tanda kutip: "WVERTICALL \ nROOAFFLSAB \ nACRILIATOA \ nNDODKONWDC \ nDRKESOODDK \ nOEEPZEGLIW \ nMSIIHOAERA \ nALRKRRIRER \ nKODEL" RANDA "

FryAmTheEggman
sumber
1
L=len;J=''.joindll dan print any(s in(v,d,w,r...))? Saya akan melakukan hal yang sama ketika saya melihat Anda diposting :)
Will
@Terima kasih atas bantuannya! Menentukan biaya len sama banyaknya dengan karakter yang dihemat, dan saya tidak yakin tentang cara mendefinisikan bergabung secara optimal (beberapa memiliki koma), jadi saya akan melakukannya sedikit.
FryAmTheEggman
Di mana pun Anda memiliki )atau ]diikuti oleh spasi, Anda dapat mengambil ruang.
undergroundmonorail
2

APL (Dyalog Classic) , 44 byte

1∊⍞⍷↑{⍉0,⍵,↑(0,⊢)\↓0,⍵}¨{⍉⌽⍵}\4⍴⊂↑a⊆⍨a≠⊃⌽a←⎕

Cobalah online!

ngn
sumber
Um, maaf, tapi sepertinya Anda tidak bisa mendapatkan input seperti itu di sini, itu perlu \n-separasi (yaitu, memiliki ⎕TC[2]sebagai pemisah).
Erik the Outgolfer
@EriktheOutgolfer oh sial ... Saya akan memperbaikinya nanti. Terima kasih.
ngn
diperbaiki sekarang, sayangnya jauh lebih lama
ngn
0

J , 60 53 byte

<@[e.[:,[:(;|.)@>[:<\\.@>[:(<"1,</.)@>@(;|.@|:)[;.2@]

Cobalah online!

Membutuhkan input pertama untuk tidak mengandung baris baru.

Penjelasan:

linkrotate=: ;|.@|:     NB. link with itself rotated 90° ccw
infixes   =: <\\.       NB. list of boxes containing the infixes
lines     =: <"1 , </.  NB. horizontal and diagonal lines, boxed
linkrev   =: ;|.        NB. link with itself reversed
appearin  =: <@[ e. [: , [: linkrev@> [: infixes@> [: lines@>@linkrotate [;.2@]

Cobalah online!

Kait bermanfaat.

pengguna202729
sumber
Tampaknya ini juga berhasil. (51 bytes)
user202729
0

Jelly , 16 byte

Memecahkan tantangan terkait (mungkin duplikat) dengan 15 dari 16 byte ini sebagai inti dari kode ...

ỴZU$3С;ŒD$€Ẏw€Ẹ

Tautan diad yang menerima daftar karakter di sebelah kiri dan daftar karakter di sebelah kanan yang mengembalikan 1 jika ditemukan dan 0 jika tidak.

Cobalah online!

Bagaimana?

ZU$3С;ŒD$€Ẏw€Ẹ - Link: words, grid
   3С          - repeat three times and collect the results (inc input):
  $             -   last two links as a monad:
Z               -     transpose
 U              -     upend     (together these rotate by a quarter)
          €     - for €ach:
         $      -   last two links as a monad:
       ŒD       -     get forward-diagonals
      ;         -     concatenate
           Ẏ    - tighten (to get all the runs across the grid) 
             €  - for €ach run:
            w   -   sublist-index (0 if not found)
              Ẹ - any truthy? (i.e. was the word found?)
Jonathan Allan
sumber