Wordsearch Solver
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
}
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.
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