Wordsearch Solver

17

2

Given a list of words and a grid of letters, find all the words in the grid and remove any letters which are not part of any of the words. The words could be forwards, backwards, up, down or diagonal. You may assume that no word in the list will occur in more than one place in the grid.

Input will always be: a list of words, 1 per line, followed by a blank line, followed by the grid of letters.

Examples

Input

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

Output

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

Input

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

Output

  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

This is code-golf - shortest solution wins.

Example wordsearches from 1 and 2.

Gareth

Posted 2011-08-09T13:44:14.240

Reputation: 11 678

Can we assume the grid is always square? – Scott Logan – 2011-08-09T16:38:19.463

@Bunnit No, I don't think so. Both the given examples are, but I think a solver should be able to handle other rectangular grids. – Gareth – 2011-08-09T16:41:32.500

Can we assume all letters are uppercase and A-Z? – Howard – 2011-08-09T18:09:57.917

@Howard Yes you can. – Gareth – 2011-08-09T18:10:33.493

@Gareth: In your first example, the bottom row has "LABVIEW" in it, but it is not displayed on the output. – Briguy37 – 2011-08-09T18:17:58.320

@Briguy37 Thanks. I did those things by hand and it took ages. I knew I'd mess it up. :-S – Gareth – 2011-08-09T18:19:46.367

@Gareth: No worries, I didn't see it either till I was testing my program :) – Briguy37 – 2011-08-09T18:32:01.360

I want to see a Befunge answer. – Thomas Eding – 2011-08-10T18:22:37.757

What if one word is inside of another word? E.g. PASTE and AST? Does that count as a word being in "more than one place in the grid" ? – Joey Adams – 2011-08-11T03:43:07.097

Also, can we assume that the word list will be sorted? – Joey Adams – 2011-08-11T03:50:11.563

@Joey Adams You can assume there will never be two words where one is a substring of another, but not that the list will be sorted. – Gareth – 2011-08-11T08:05:48.150

Answers

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

Posted 2011-08-09T13:44:14.240

Reputation: 4 466

Nicely done. Your algorithm appears to be the same as in my answer, but considerably more compact in ruby. You're reinforcing my belief I should add ruby to my code-golf bag. – DCharness – 2011-08-12T20:13:12.500

6

Perl - 230 chars

Count includes 4 for "-ln " command-line options.

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}

Ungolfed:

# -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

Posted 2011-08-09T13:44:14.240

Reputation: 541

I'm not too familiar with Perl, so maybe I'm not seeing something in your solution, but doesn't your regex wrap around the sides for the diagonals? – migimaru – 2011-08-12T01:16:09.843

@migimaru The .{$n} portion of the regexp (along with the /s option) does wrap around for the diagonals (and straight down) to implement the downward component of the match direction. Is your concern a false match that wraps? AFAICT, this can't give false matches, because of the newlines in the string. Suppose letter i of a word matches in the rightmost column, and we're checking the SE diagonal. The .{$n} portion skips the next $W+1 characters, which are the immediately following \n and all of the next line. Letter i+1 will mismatch against the next \n, thus no overall match. – DCharness – 2011-08-12T19:57:51.707

Ah, I see. I missed the fact that the newlines are included and would prevent false matches. Thanks! – migimaru – 2011-08-13T00:11:01.230

3

JavaScript: 342 characters

Code-Golfed version:

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)}

Formatted version:

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');
}

The concept behind this solution is to iterate over all positions on the board, initialize a 2D-array's values to ' ' for each position, and then consider all potential word directions and word offsets. If a matching word is found, the array's value for that position is updated to the correct letter. Finally, the array is converted to a string and returned.

Briguy37

Posted 2011-08-09T13:44:14.240

Reputation: 2 616

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 ()
   })
  }
}

user unknown

Posted 2011-08-09T13:44:14.240

Reputation: 4 210

You could save a couple of characters by using stdin instead of fromFile. I didn't specify where input comes from. – Gareth – 2011-08-11T08:08:23.997