Wordsearch Solver

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
EVISNOHTYPL
AAYLBMESSAC
WEIVBALOGOM


Output

LL K    FC
OR LOBOCOI
GELACSAPRS
LP T    TAV
A  L    RBI
IHPLED  A S
J APHP N U
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
PASTE
RETURN
SAVE
SOFTWARE
START
TEXT
TOWER
WORDPROCESSING

IAUERAWTFOSICPN
DGZPFLOPPYARFLU
RSNOCURSORVZDBM
AMNIUOMRNHEGUIN
OTBNSRMONITORNT
BEYTTSGPJBOLDRT
YRQEAHEHARDWARE
EOGRRNECECLOSEP
KIONTYKTODTOWER
ELCENSUPERPDKNN
ATRTPRYKELPVIEJ
GIEANPOTKSEDUSL
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
TEDITA       O
P        MW


This is code-golf - shortest solution wins.

Example wordsearches from 1 and 2.

• Can we assume the grid is always square? Aug 9, 2011 at 16:38
• @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. Aug 9, 2011 at 16:41
• Can we assume all letters are uppercase and A-Z? Aug 9, 2011 at 18:09
• @Howard Yes you can. Aug 9, 2011 at 18:10
• @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. Aug 11, 2011 at 8:05

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
}

• 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? Aug 12, 2011 at 1:16
• @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. Aug 12, 2011 at 19:57 • Ah, I see. I missed the fact that the newlines are included and would prevent false matches. Thanks! Aug 13, 2011 at 0:11 Ruby 1.9, 214210206182177173172 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

• 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. Aug 12, 2011 at 20:13

05AB1E, 87 (or 83?) bytes

||UεVX8FD»YåiY1:AuSð:1Y:}D€g©ËiεSÐ0:«NFÁ}}øíJ0δKõKë®à©FD®£€нJRsεN®‹i¦}}¦}\)]€Søε{θ}J®ä»


With the actual I/O as mentioned in the challenge description.

Try it online. (For some reason, the Á is very slow on an inner list of characters instead of a string in this program, so εSÐ0:«NFÁ}} has been replaced with εÐS0:«NFÁ}S} (rotate first; then convert it to a list of characters) to speed things up substantially - it'll now output on TIO in roughly a second, instead of timing out without any output after 60 seconds.)

With less strict I/O (first words-input as a list, second grid-input as a list of lines; output-grid as a list of lines as well), this would be 83 bytes instead:

εVI8FD»YåiY1:AuSð:1Y:}D€g©ËiεSÐ0:«NFÁ}}øíJ0δKõKë®à©FD®£€нJRsεN®‹i¦}}¦}\)]€Søε{θ}J®ä


Try it online (with the same modification as above so it won't time out).

Explanation:

In pseudo-code, I do the following steps:

Map over the list of words:
Push the input-grid
Loop 8 times:
If the word is present horizontally left-to-right:
Replace everything else with a space
Rotate the grid 45 degrees counterclockwise
Reduce/combine all grids of spaces and words


As for the actual code, of which most (50 bytes) is used to rotate the grid 45 degrees:

|                      # Get all inputs until an empty line is encountered,
# resulting in the list of words
|                     # Do it again, resulting in the grid
U                    # Pop and store the grid in variable X
ε                     # Map over each of the words:
V                    #  Pop and store the word in variable Y
X                    #  Push grid X
8F                  #  Loop 8 times:
D»Yå              #   Check if the word is in the grid:
D                 #    Duplicate the grid
»                #    Join the lines with newline delimiter
Yå              #    Check that this contains the word Y
i             #   If this is truthy:
Y1:          #    Replace the word temporarily with a 1
AuSð:        #    Replace all uppercase letters with a space
1Y:          #    Replace the 1 back to the word
}             #   Close the if-statement
#   Rotate the grid 45 degrees counterclockwise:
D€g©Ë             #    Check if the grid is a rectangle:
D                 #     Duplicate the grid
€g               #     Get the length of each row
©              #     Save this list of lengths in variable ® (without popping)
Ë             #     Check whether these lengths are all equal
i            #    If this is truthy:
ε           #     Map over each row:
S          #      Convert it to a list of characters
Ð0:«      #      Append the row-length amount of 0s to the row
Ð         #       Triplicate the row
0:       #       Pop two, and replace all characters to 0s
«      #       Merge this list of 0s to the row
NF        #      Loop the 0-based map-index amount of times:
Á       #       Rotate the row once towards the right
}         #      Close the loop
}           #     Close the map
øí         #     Now rotate 90 degrees clockwise:
ø          #      Zip/transpose; swapping rows/columns
í         #      Reverse each row
J        #     Join the inner list of characters back to a string
δ      #     Map over each row:
0 K     #      Remove all 0s from the row
õK   #     Remove any empty rows
ë            #    Else (it's a diamond-shape instead):
®           #     Push the list of lengths
à          #     Pop and push its maximum
©         #     Store this maximum as new variable ® (without popping)
F        #     Loop this maximum amount of times:
D       #      Duplicate the list
®£     #      Only leave the first max amount of values
€н   #      Only leave the first character of each row
J  #      Join these characters together to a string
R #      Reverse it
s       #      Swap so the list is at the top again
ε      #      Map over each row:
N®‹i  #       If the map-index is smaller than max ®:
¦ #        Remove the first character
}  #       Close the if-statement
}      #      Close the map
¦     #      Remove the first (now empty) row
}        #     Close the loop
\       #     Discard the now empty list
)      #     Wrap all rows on the stack into a list
]                     # Close the open if-statement; loop; and map
# (we now have a list space-grids, except for the found words)
€S                   # Convert each inner grid to a flattened list of characters
ø                  # Zip/transpose; swapping rows/columns
ε                 # Map over each inner list:
{                #  Sort; spaces at the front, potential letter(s) at the end
θ               #  Pop and leave the last character
}                 # Close the map
J                # Join everything together to one huge string
®               # Push the last maximum ®
ä              # Split the string into that many equal-sized parts
»             # Join the list of rows with newline delimiter
# (after which it is output implicitly as result)

• Input is strict, so you can't use the 4 byte saving version I'm afraid. On the positive side, I guess you've taken the lead - 10 years after the question was first asked. :-) Jan 30 at 14:56
• I'll give @ovs a chance to reduce the size of their entry with the strict input requirement (unlikely that any of the others will update their entries now) - I'll update the big green tick in a couple of days. Jan 30 at 15:01

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.

BQN, 126 114 bytesSBCS

{S←-++×¬⋄{w𝕊g:g⊑∘↑˜¨¯2+∨´⥊w{H←⊒˜∊·⥊(↕≠𝕨)+⌜·/𝕨⊸⍷⋄(H˘∨1↓˘⊒˜⌽⁼˘·H˘⌾⍉⊒˜⌽˘' '⊸∾˘)⌾(⌽∘⍉⍟𝕩)g}⌜↕4}⟜>´(S⟨⟩⊸≡¨)⊸⊔𝕩⊔˜S𝕩='
'}


Run online!

One third of the code is parsing the input, the more interesting parts are outlined below:

{w𝕊g:g⊑∘↑˜¨¯2+∨´⥊w{H←⊒˜∊·⥊(↕≠𝕨)+⌜·/𝕨⊸⍷⋄(H˘∨1↓˘⊒˜⌽⁼˘·H˘⌾⍉⊒˜⌽˘' '⊸∾˘)⌾(⌽∘⍉⍟𝕩)g}⌜↕4}


Run online!

{w𝕊g:g⊑∘↑˜¨¯2+∨´⥊w{ ... }⌜↕4}
w𝕊g:                          # A dyadic function taking:
#  - left argument w: word list
#  - right argument g: grid
↕4   # 0 1 2 3
{ ... }⌜     # For each of those numbers on the right (specifying rotation) and ...
w             # each word on the left, call the inner function.
# The inner function returns boolean matrices of the same shape of the input
∨´⥊              # Boolean OR of all the matrices
g⊑∘↑˜¨¯2+                 # For 1's in the matrix take a character from the grid, for 0's take a space.


The inner function rotates the grid (as many times as its right argument specifies: ⌽∘⍉⍟𝕩), checks for words from left to right and on diagonals and then rotates the result back.

How to get get diagonals:

This method is mostly taken from BQNcrate. First a space is prepended to each row. Then each row is rotated by its index. Now words previously in the diagonals are in the columns, by transposing we get them in the rows. After marking the words, all the steps can be reversed: Try with step-by-step results!

• Sorry, input is strict. Jan 30 at 14:51

Scala 697, 666 649

val(z,n)=io.Source.fromFile("F").getLines.toList.span(_.length>0)
val m=n.tail
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 ()
})
}
}

• You could save a couple of characters by using stdin instead of fromFile`. I didn't specify where input comes from. Aug 11, 2011 at 8:08