word-search.js

/*
HOW TO RUN THIS SCRIPT
node ws.js input.txt
*/

console.log(findPaths());

/*
main routine
*/
function findPaths() {
	// parse input
	const {rows, cols, matrix, noWarp, words} = parseInput();

	// keep result of each input word as an array
	const res = Array(words.length).fill('NOT FOUND');

	// remember which block is alreay visited in DFS
	let visited = Array(rows).fill({}).map(r => Array(cols).fill(false));

	// build trie and use it to search multiple words at the same time
	const trie = buildTrie(words);

	// run depth first search
	for (let r = 0; r < rows; r++) {
		for (let c = 0; c < cols; c++) {
			traverse({r, c}, r, c, trie);
		}
	}

	// join result as string
	return res.join('\n');



	function traverse(from, r, c, trieNode) {
		// boundary checking
		if (noWarp && (r < 0 || r === rows || c < 0 || c === cols)) {
			return;
		}

		r = (r + rows) % rows;
		c = (c + cols) % cols;

		if (visited[r][c]) {
			return;
		}

		const ch = matrix[r][c];
		const next = trieNode[ch];

		if (!next) {
			return;
		}

		/*
		add result if any word is found
		*/
		if (next.wordIndex !== undefined) {
			res[next.wordIndex] = `(${from.r}, ${from.c}), (${r}, ${c})`;
		}

		visited[r][c] = true;
		traverse(from, r - 1, c - 1, next);
		traverse(from, r, c - 1, next);
		traverse(from, r + 1, c - 1, next);
		traverse(from, r - 1, c, next);
		traverse(from, r, c, next);
		traverse(from, r + 1, c, next);
		traverse(from, r - 1, c + 1, next);
		traverse(from, r, c + 1, next);
		traverse(from, r + 1, c + 1, next);
		visited[r][c] = false;
	}
}

/*
input []string
output trie
*/
function buildTrie(words) {
	const trie = {};
	words.map(addWord);
	return trie;

	function addWord(word, idx) {
		let curr = trie;
		word.split('').forEach(ch => {
			curr[ch] = curr[ch] || {};
			curr = curr[ch];
		});

		// keep the idx of word so it is easier to build results
		curr.wordIndex = idx;
	}
}


/*
input: filepath
output:
{
  rows Number
  cols Number
  matrix [][]
  noWarp Bool
  words []
}
*/
function parseInput() {
	let lineIdx = 0;
	const fs = require('fs');
	const lines = fs.readFileSync(process.argv[2], 'utf8').split('\n').filter(l => !!l);

	// 1. find dimensions
	let rows, cols;
	[rows, cols] = lines[lineIdx++].split(' ');
	rows = parseInt(rows);
	cols = parseInt(cols);

	// 2. create matrix
	const matrix = [];
	for (i = 0; i < rows; i++) {
		matrix.push(lines[lineIdx++].split(''));
	}

	// 3. noWarp flag
	const noWarp = lines[lineIdx++] === 'NO_WRAP';

	// 4. testing words
	// skip the number of testing words
	lineIdx++;
	const words = [];
	while (lineIdx < lines.length) {
		words.push(lines[lineIdx++]);
	}

	return {
		rows,
		cols,
		matrix,
		noWarp,
		words
	};
}