I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

# Thursday Code Puzzler: A Variation on Wordsearch

08.01.2013
| 4401 views |

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Find the Word

This week the challenge is to find a word in a two-dimensional array. The word can go in any direction, once it is connected (vertical, horizontal, diagonal, backwards). An example array would be

```'e','s','a','s','j'
'w','n','v','o','9'
'r','s','o','i','a'
'y','s','s','z','a'
'e','s','r','a','d'```

In the above you can find the word 'dzone'. Write a program that can take any string and find it in the 2D array - you can use the example of finding 'dzone' in the above input first. And don't forget, efficiency is everything

Catch up on all our previous puzzlers here

Tags:

### Ondřej Smola replied on Thu, 2013/08/01 - 3:11pm

Scala madness (its late) :)  Streams all possible results and result is list of pairs (i,j) without duplicates (character in array cannot be reused more times for one path).

``` def neighbor_chars_with_positions(pos: Tuple2[Int, Int], src: Array[Array[Char]]) =
List((pos._1, pos._2 + 1), (pos._1, pos._2 - 1), (pos._1 + 1, pos._2),
(pos._1 - 1, pos._2), (pos._1 + 1, pos._2 + 1), (pos._1 + 1, pos._2 - 1),
(pos._1 - 1, pos._2 + 1), (pos._1 - 1, pos._2 - 1))
.filter({ x => x._1 >= 0 && x._1 < src.size && x._2 >= 0 && x._2 < src(x._1).size  })
.map ({ x => (src(x._1)(x._2), x) })

def word_paths_from_position(word: String, src: Array[Array[Char]], pos: Tuple2[Int, Int], path_so_far: List[(Int, Int)] = List()): List[List[(Int, Int)]] = {
if (word.isEmpty) {
List((pos :: path_so_far) reverse)
} else {
neighbor_chars_with_positions(pos, src)
.map(_._2)
.filterNot(path_so_far.contains(_))
.flatMap(word_paths_from_position(word.tail, src, _, pos :: path_so_far))
}
}

def word_paths(word: String, src: Array[Array[Char]]) =
src.zipWithIndex
.flatMap{ case (row, i) =>
row.zipWithIndex.filter{case (el,_) => el == word.head}
.flatMap{ case (el,j) => word_paths_from_position(word.tail, src, (i, j))}}.toStream

word_paths("dzone",src) take 1000 foreach println```

### Cristian Martin replied on Wed, 2013/08/07 - 9:10am

My quick response in javascript:

```var finder = function(word, puzzle) {

this.dirLR = function(i,j) { if (j < (this.puzzle[i].length -1)) return { i: i, j: j+1, c: this.puzzle[i][j+1] }; }
this.dirRL = function(i,j) { if (j > 0) return {i: i-1, j: j, c: this.puzzle[i-1][j] }; }
this.dirUD = function(i,j) { if (i < (this.puzzle.length -1)) return { i: i+1, j: j, c: this.puzzle[i+1][j] }; }
this.dirDU = function(i,j) { if (i > 0) return { i: i-1, j: j, c: this.puzzle[i-1][j] }; }
this.diagonal1 = function(i,j) { if (i > 0 && j > 0) return { i: i-1, j: j-1, c: this.puzzle[i-1][j-1] }; }
this.diagonal2 = function(i,j) { if (i > 0 && j < (this.puzzle[i].length -1)) return { i: i-1, j: j+1, c: this.puzzle[i-1][j+1] }; }
this.diagonal3 = function(i,j) { if (i < (this.puzzle.length -1) && j < (this.puzzle[i].length -1)) return { i: i+1, j: j+1, c: this.puzzle[i+1][j+1] }; }
this.diagonal4 = function(i,j) { if (i < (this.puzzle.length -1) && j > 0) return {i: i+1, j: j-1, c: this.puzzle[i+1][j-1] }; }

this.init = function(word, puzzle) {
this.word = word;
this.puzzle = puzzle;
return this.find();
}

this.walk = function(i, j, dir, pos, finded) {
var res = this[dir](i,j);

if (!res) return finded;

pos++;

if ( res.c !== this.word[pos]) return finded;

finded.push(res);

if (pos < this.word.length-1) {
this.walk(res.i, res.j, dir, pos, finded);
}
}

this.find = function() {
var result = [], c,
directions = ['dirLR','dirRL','dirUD','dirDU','diagonal1','diagonal2','diagonal3','diagonal4'],
dir;

for (var i = 0, l = this.puzzle.length; i < l; i++) {
for (var j = 0, ll = this.puzzle[i].length; j < ll; j++) {
c = this.puzzle[i][j];
if (c === word[0]) {
var finded = [{ i:i, j: j, c: c }];

for (var z = 0, lll = directions.length; z < lll; z++) {
dir = directions[z];
this.walk(i,j, dir, 0, finded);
if (finded.length === this.word.length) {
return finded;
}
}
}
}
}

return result;
}

return this.init(word, puzzle);

}

var word = 'dzone';
var puzzle = [
['e','s','a','s','j'],
['w','n','v','o','9'],
['r','s','o','i','a'],
['y','s','s','z','a'],
['e','s','r','a','d']
];
var a = new finder(word, puzzle);
console.log(JSON.stringify(a));```

### Daniel Sobral replied on Mon, 2013/08/12 - 11:04am

Here's an efficient version in Scala. It does at most two passes (first top-left to bottom-right, then the opposite direction), stops when it finds the word, is memory-efficient (that is, the memory consumption is O(1)), and prints the coordinates of the word start plus the direction in which the word is written.

```def find(word: String, m: Array[Array[Char]]) = {
def checkAt(char: Char, row: Int, column: Int, i: Array[Array[Int]]) = {
if (i.indices.contains(row)
&& i.indices.contains(column)
&& word(i(row)(column)) == char) i(row)(column) + 1
else 0
}

def checkDirection(direction: Int, i: Array[Array[Int]]): Option[(String, String, Int, Int)] = {
val rowIndices = if (direction < 0) m.indices else m.indices.reverse
val columnIndices = if (direction < 0) m(0).indices else m(0).indices.reverse
for {
row <- rowIndices
column <- columnIndices
} {
val char = m(row)(column)
val topBottom = checkAt(char, row + direction, column, i)
val leftRight = checkAt(char, row, column + direction, i)
val diagonal = checkAt(char, row + direction, column + direction, i)
val here = checkAt(char, row, column, i)

val fromStart = direction * (word.size - 1)

if (topBottom == word.size)
return Some(("top", "bottom", row - fromStart, column))
if (leftRight == word.size)
return Some(("left", "right", row, column - fromStart))
if (diagonal == word.size)
return Some(("top left", "bottom right", row + fromStart, column + fromStart))

i(row)(column) = List(topBottom, leftRight, diagonal, here).max
}
None
}

val direct = Array.ofDim[Int](m.size, m(0).size)
val directResult = checkDirection(-1, direct) map {
case (from, to, row, column) => "("+row+", "+column+") from "+from+" to "+to
}
val reverse = Array.ofDim[Int](m.size, m(0).size)
val result = directResult orElse {
checkDirection(1, reverse) map {
case (from, to, row, column) => "("+row+", "+column+") from "+to+" to "+from
}

result
}
```

### Philip Puthenvila replied on Tue, 2013/08/13 - 7:26pm

```import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang.StringUtils;

public class WordPuzzler {

public static void main(String[] args) {
String[][] a1 = new String[][] {
// //
{ "e", "s", "a", "s", "j" },
// //
{ "w", "n", "v", "o", "9" },
// //
{ "r", "s", "o", "i", "a" },
// //
{ "y", "s", "s", "z", "a" },
// //
{ "e", "s", "r", "a", "d" } };
Map<Integer, List<String>> map = new HashMap<Integer, List<String>>(5);
for (int i = 0; i < a1.length; i++) {
map.put(new Integer(i), Arrays.asList(a1[i]));
}
String word = "dzone";
Set<Integer> keyset = map.keySet();
for (Integer integer : keyset) {
List<String> wordlist = map.get(integer);
// find the horizontal
processWordString(word, (String[]) wordlist.toArray());
}
String[] tmp = new String[word.length()];
int wordLength = word.length();
int tmplength = 0;
// diagonal left corner
Iterator<Integer> iterator = keyset.iterator();
while (iterator.hasNext()) {
List<String> wordlist = map.get((Integer) iterator.next());
tmp[tmplength] = wordlist
.get(wordLength - (wordLength - tmplength));
tmplength++;
}
processWordString(word, (tmp));
// diagonal right corner
iterator = keyset.iterator();
tmplength = wordLength - 1;
tmp = new String[word.length()];
while (iterator.hasNext()) {
List<String> wordlist = map.get((Integer) iterator.next());
tmp[tmplength] = wordlist.get(wordLength
- (wordLength - (tmplength)));
tmplength--;
}
processWordString(word, (tmp));
// vertical
int maincount = 0;
while (maincount < wordLength) {
tmplength = 0;
tmp = new String[word.length()];
iterator = keyset.iterator();
while (iterator.hasNext() && tmplength >= 0) {
List<String> wordlist = map.get((Integer) iterator.next());
tmp[tmplength] = wordlist.get(maincount);
tmplength++;
}
processWordString(word, (tmp));
maincount++;
}

}

private static void processWordString(String word, String[] wordlist) {
String wordstring = StringUtils.join(wordlist);
if (wordstring.equals(word)) {
System.err.println("Got the word : " + wordstring);
return;
}
if (wordstring.endsWith(word.substring(0, 1))) {
wordstring = StringUtils.reverse(wordstring);
if (wordstring.equals(word))
System.err.println("Got the word : " + wordstring);
return;
}
}```

### Camilo Rivera replied on Mon, 2013/10/28 - 7:09pm

Ruby code supporting multiple appearances of word in the same multi-dimensional array.

```class WordSearch

def initialize(array)
@matrix = array
end

def find(word)
[:row,:col,:diag].each do |dir|
found = find_in_words(all_words(dir), word, dir)
puts "Found word '#{word}' at #{dir} #{found[0]} #{found[1]}" if found != nil
end
end

private

def find_in_words(words, word, dir)
(0...words.length).each do |i|
return [i,'regular'] if words[i].join.index(word) != nil
return [i,'reverse'] if words[i].reverse.join.index(word) != nil
end
return nil
end

def all_words(dir)
case dir
when :row
@matrix
when :col
@matrix.transpose
when :diag
diagonals
end
end

def diagonals()
words = Array.new
(@matrix.length-1).downto(0).each do |e|
words << get_word(0,e,1,1)
end
(1...@matrix[0].length).each do |e|
words << get_word(e,0,1,1)
end
words
end

def get_word(x, y, dx, dy)
i = x
j = y
word = Array.new
while i < @matrix.length && j < @matrix[0].length do
word << @matrix[i][j]
i = i + dx
j = j + dy
end
word
end
end

MATRIX_1 = [['e','s','a','s','j'],['w','n','v','o','9'], ['r','s','o','i','a'], ['y','s','s','z','a'], ['e','s','r','a','d']]
ws = WordSearch.new(MATRIX_1)
ws.find("dzone")
ws.find("sssn")
ws.find("vos")
ws.find("so")```