Pemecah Kata Pencarian

17

Diberikan daftar kata dan kisi-kisi huruf, temukan semua kata dalam kisi dan hapus semua huruf yang bukan bagian dari kata-kata itu. Kata-kata itu bisa maju, mundur, naik, turun atau diagonal. Anda dapat berasumsi bahwa tidak ada kata dalam daftar yang akan muncul di lebih dari satu tempat di grid.

Input akan selalu: daftar kata, 1 per baris, diikuti oleh baris kosong, diikuti oleh kisi-kisi huruf.

Contohnya

Memasukkan

ADA
ALGOL
ASSEMBLY
BASIC
COBOL
DELPHI
FORTRAN
JAVA
LABVIEW
LOGO
PASCAL
PERL
PHP
PYTHON
SMALLTALK
VISUALC

LLJKCABLFCI
OROLOBOCOIM
GELACSAPRSX
LPSTAHWVTAV
ANRLXLXQRBI
IHPLEDOXAHS
KJYAPHPYNOU
FABMADANZJA
EVISNOHTYPL
AAYLBMESSAC
WEIVBALOGOM

Keluaran

LL K    FC
OR LOBOCOI 
GELACSAPRS
LP T    TAV
A  L    RBI
IHPLED  A S
 J APHP N U
 A MADA   A
 V SNOHTYPL
 AYLBMESSAC
WEIVBALOGO

Memasukkan

BACKSPACE
BOLD
CLOSE
COMPACTDISC
COPY
CPU
CURSOR
DELETE
DESKTOP
DVD
EDIT
ENTER
EXIT
FLOPPY
FONT
HARDWARE
INTERNET
KEYBOARD
MONITOR
MOUSE
PASSWORD
PASTE
RETURN
SAVE
SOFTWARE
START
TEXT
TOWER
WORDPROCESSING

IAUERAWTFOSICPN
DGZPFLOPPYARFLU
RSNOCURSORVZDBM
AMNIUOMRNHEGUIN
OTBNSRMONITORNT
BEYTTSGPJBOLDRT
YRQEAHEHARDWARE
EOGRRNECECLOSEP
KIONTYKTODTOWER
ELCENSUPERPDKNN
ATRTPRYKELPVIEJ
GIEANPOTKSEDUSL
NXCMPASSWORDRUC
TEDITAGVSWJCTOV
CWOYPGYQKNLVXMW

Keluaran

  UERAWTFOS    
DG PFLOPPYA    
R NOCURSORV    
A NI O    E    
OT NS MONITOR  
B  TTS P BOLD  
Y  EA EHARDWARE
E  RRNECECLOSE
K  NT KTO TOWER
   E SUPER D   
 TRTPRY ELPVIE 
 IEANPOTKSED S 
 XC PASSWORDRUC
TEDITA       O 
    P        MW

Ini adalah kode-golf - kemenangan solusi terpendek.

Contoh pencarian kata dari 1 dan 2 .

Gareth
sumber
Bisakah kita menganggap kisi selalu persegi?
Scott Logan
@ Kelinci Tidak, saya kira tidak. Kedua contoh yang diberikan adalah, tapi saya pikir seorang pemecah harus mampu menangani grid persegi panjang lainnya.
Gareth
Bisakah kita menganggap semua huruf besar dan AZ?
Howard
@ Howard Ya Anda bisa.
Gareth
@ Gareth: Dalam contoh pertama Anda, baris bawah memiliki "LABVIEW" di dalamnya, tetapi tidak ditampilkan pada output.
Briguy37

Jawaban:

3

Ruby 1.9, 214 210 206 182 177 173 172 166

s,G=$<.read.split$/*2
O=G.tr'^
',' '
(s+$/+s.reverse).split.map{|w|[0,l=G=~/$/,l+1,l-1].map{|d|(k=G=~/#{[*w.chars].*?.*d}/m)&&w.size.times{|i|O[k+d*i+i]=w[i]}}}
$><<O
Lowjacker
sumber
Bagus sekali. Algoritme Anda tampaknya sama dengan jawaban saya, tetapi jauh lebih ringkas di ruby. Anda memperkuat keyakinan saya, saya harus menambahkan ruby ​​ke tas kode-golf saya.
DCharness
6

Perl - 230 karakter

Hitungan termasuk 4 untuk opsi baris perintah "-ln".

if(1../^$/){push@w,$_,''.reverse if$_}else{$a.="$_\n"}END{$_=$a;/.+/;$W=$+[0];y/A-Z/ /;chomp;for$w(@w){for$n(0,$W-1..$W+1){$r=join".{$n}",map"($_)",(@l=split//,$w);if($i=$a=~/$r/s){substr($_,$-[$i++],1,shift@l)while@l}}}print}

Tidak Disatukan:

# -n: implicitly loop over input lines
# -l: strip the newlines
if ( 1 .. /^$/ ) {              # from first line to empty line
  push @w,                      # record in @w
    $_,                         #   the word
      ''.reverse                #   and its reverse
        if $_                   #   if it's not the empty line
}
else {
  $a .= "$_\n"                  # otherwise, add to the search array
}

END {
  $_ = $a;                      # make a copy for the output
  /.+/; $W = $+[0];             # compute array width
  y/A-Z/ /;                     # blank the output board
  chomp;                        # and remove the trailing newline,
                                #  because -l will add it back for us
  for $w (@w) {                 # for each word
    for $n (0, $W-1 .. $W+1) {  # for each direction in E, SW, S, SE
      $r = join ".{$n}",        # form a regexp with an appropriate
                                #  number of characters skipped between letters
                                #  (0 -> adjacent, so E; $W -> next line, so S;
                                #   off by one from $W for the diagonals),
        map "($_)",             #  capturing the letters of the word (for their offsets),
          (@l=split//,$w);      #  which we split up here
      if ( $i = $a =~ /$r/s ) { # if the word matches in this orientation
        substr( $_,             # set the substring of the output
                $-[$i++],       #  at the offset this letter matched
                1,              #  length 1
                shift @l )      #  to the corresponding letter
          while @l              #  (for each letter)
      }
    }
  }
  print                         # and print the output
}
DCharness
sumber
Saya tidak terlalu akrab dengan Perl, jadi mungkin saya tidak melihat sesuatu dalam solusi Anda, tetapi bukankah regex Anda membungkus sisi untuk diagonal?
migimaru
@migimaru .{$n}Bagian regexp (bersama dengan /sopsi) tidak membungkus diagonal untuk (dan lurus ke bawah) untuk menerapkan komponen ke bawah dari arah pertandingan. Apakah kekhawatiran Anda cocok palsu yang membungkus? AFAICT, ini tidak dapat memberikan kecocokan yang salah, karena baris baru dalam string. Misalkan huruf i dari sebuah kata cocok di kolom paling kanan, dan kami sedang memeriksa SE diagonal. The .{$n}porsi melompat $ berikutnya W + 1 karakter, yang segera setelah \ n dan semua baris berikutnya. Huruf i +1 akan tidak cocok dengan \ n berikutnya, sehingga tidak ada kecocokan keseluruhan.
DCharness
Ah, begitu. Saya melewatkan fakta bahwa baris baru disertakan dan akan mencegah kecocokan yang salah. Terima kasih!
migimaru
3

JavaScript: 342 karakter

Versi Kode-Golf:

function a(b){c='\n';d=b.split(c+c);e=d[1].split(c);for(f=-1,g=[];h=e[++f];)for(i=-1,g[f]=[];h[++i];)for(j=-2,g[f][i]=' ';2>++j;)for(l=-2;2>++l;)for(k=0;m=d[0].split(c)[k++];)for(n=-1;o=m[++n];)for(p=f-n*j-j,q=i-n*l-l,r=0;(s=m[r++])&&(t=e[p+=j])&&(u=t[q+=l])&&s==u;)if(r==m.length)g[f][i]=o;for(i=0;v=g[i];)g[i++]=v.join('');return g.join(c)}

Versi yang diformat:

function solveWordsearch(input){
    var lineBreak = '\n';
    var solver = input.split(lineBreak+lineBreak);
    var board = solver[1].split(lineBreak);

    for(row=-1,output=[]; line=board[++row];){
        for(col=-1,output[row]=[]; line[++col];){
            for(rowIncrement=-2,output[row][col]=' ';2>++rowIncrement;){
                for(colIncrement=-2;2>++colIncrement;){
                    for(k=0; word=solver[0].split(lineBreak)[k++];){
                        for(charPosition=-1; wordChar=word[++charPosition];){
                            var startRowIndex=row-charPosition*rowIncrement-rowIncrement;
                            var startColIndex=col-charPosition*colIncrement-colIncrement;
                            for(wordIndex=0;(compareWordChar=word[wordIndex++])&&(compareBoardRow=board[startRowIndex+=rowIncrement])&&(compareBoardChar=compareBoardRow[startColIndex+=colIncrement])&&compareWordChar==compareBoardChar;){
                                if(wordIndex == word.length){
                                    output[row][col]=wordChar;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    for(i=0;outLine=output[i];){
        output[i++]=outLine.join('');
    }

    return output.join('\n');
}

Konsep di balik solusi ini adalah untuk mengulangi semua posisi di papan tulis, menginisialisasi nilai-nilai array 2D ke '' untuk setiap posisi, dan kemudian mempertimbangkan semua arah kata yang potensial dan offset kata. Jika kata yang cocok ditemukan, nilai array untuk posisi itu diperbarui ke huruf yang benar. Akhirnya, array dikonversi menjadi string dan dikembalikan.

Briguy37
sumber
1

Scala 697, 666 649

val(z,n)=io.Source.fromFile("F").getLines.toList.span(_.length>0)
val m=n.tail
val(w,h)=(m.head.length,m.size)
def g(d:Int,e:Int,k:Int,g:Int,h:Int,i:Int,s:String)={
def f(x:Int,y:Int):Seq[(Int,Int)]={
val q=for(c<-(0 to s.size-1))
yield (y+c*i,x+c*k)
if((q.map(p=>m(p._1)(p._2))).mkString==s)q else Nil}
val t=for(x<-(d to e);
y<-(g to h))yield f(x,y)
t.flatten}
def i(s:String)={val l=s.size
g(0,w-l,1,0,h-1,0,s)++ g(0,w-1,0,0,h-l,1,s)++ g(0,w-l,1,l-1,h-1,-1,s)++ g(0,w-l,1,0,h-l,1,s)}
def j(s: String)=i(s)++ i(s.reverse)
val k=z.map(j).flatten
(0 to h-1).map(r=>{(0 to w-1).map(c=>if(k.contains(r,c))print(""+m(r)(c))else print(" "));println()})

degolfed:

object Golf {

def main (args: Array[String]) = {
  val (words, matrix) = io.Source.fromFile ("./wordsearch.data").getLines.toList.span (_.length > 0)
  val m = matrix.tail
  val (w,h) = (m.head.length, m.size)

  // xi: x-increment, yi: y-increment
  def find (x: Int, y: Int, xi: Int, yi: Int, s: String): Seq [(Int, Int)] = {
    val points = for (c <- (0 to s.length-1))
       yield (y + c*yi, x + c * xi)
    if ((points.map (p => m (p._1)(p._2))).mkString == s) points else Nil
  }

  def findInScope (xS: Int, xD: Int, xi: Int, yS: Int, yD: Int, yi: Int, s: String): Seq [(Int, Int)] = {
    val ppoints = for (x <- (xS to xD);
          y <- (yS to yD)) yield find (x, y, xi, yi, s)
    ppoints.flatten 
  }

  def findRowColFallingClimbing (s: String) = {
    val l=s.length

    // horizontal:
      findInScope (0,   w-l,  1,   0, h-1,  0, s) ++
    // vertical: 
      findInScope (0,   w-1,  0,   0, h-l,  1, s) ++
    // climbing /:
      findInScope (0,   w-l,  1, l-1, h-1, -1, s) ++
    // falling \:
      findInScope (0,   w-l,  1,   0, h-l,  1, s)
  }

  def findBoth (s: String) = findRowColFallingClimbing (s) ++ findRowColFallingClimbing (s.reverse)
  val coords = words.map (findBoth).flatten

  (0 to h-1).map ( r => {
    (0 to w-1).map (c =>
      if (coords.contains (r, c))
       print ("" + m(r)(c)) 
      else print (" ")
     )
     println ()
   })
  }
}
Pengguna tidak diketahui
sumber
Anda dapat menyimpan beberapa karakter dengan menggunakan stdinalih-alih fromFile. Saya tidak menentukan dari mana input berasal.
Gareth