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
| 4339 views |
  • submit to reddit

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

Comments

sun east replied on Fri, 2013/08/02 - 9:24am



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)
        .filter(_._1 == word.head)
        .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));

Alexey Kutuzov replied on Thu, 2013/08/08 - 3:20am

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
      }
    } getOrElse "Word not found"
    
    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")

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.