word-search.org

Word Search

Prompt

This one came from Naomi K, who I was chatting with on IRC in the neighborhood of 2013:

Given a list of words, find all the orthogonal words in set string of characters. Lazy cracker asses need not apply.

// possible words
var words = ["lazy", "crackers", "hello", "cruel", "world", "bears", "need", "not", "apply"];

// characters
var puzzle = " \
r b f x w \
h e l l o \
o a h c r \
c r u e l \
v s u f d \
";

var solve = function solve(puzzle, words) {
  // you write this part
};

solve(puzzle, words);
//=> ["hello", "cruel", "world", "bears"]

My Solution in 2013

“Hello cruel world bears!” “That’s iiiit!!!” “Thanks Pat Sajak!!!!”

// possible words
var words = ["lazy", "crackers", "hello", "cruel", "world", "bears", "need", "not", "apply"];

// characters
var puzzle = " \
r b f x w \
h e l l o \
o a h c r \
c r u e l \
v s u f d \
";

//
// "I'd like to solve the puzzle..."
//
console.log(solve(enshapen(puzzle, 5, 5), words));
//=> ["hello", "cruel", "world", "bears"]

function solve(puzzle, words) {
  return words.filter(function (w) {
    //
    // TODO: Implement asDiagonalL and asDiagonalR
    //
    return asMatrix(puzzle).some(_find) ||
           asColumns(puzzle).some(_find);

    function _find(l) {
      return find(l, w);
    }
  });
};

function find(line, word) {
  var m = line.match(word);
  return m ? { start: m.index, end: m.index + word.length } : null;
};

function asMatrix(puzzle) {
  return puzzle.map(function (l) { return l.join(''); });
}

function asColumns(puzzle) {
  return Array.apply(null, Array(puzzle[0].length)).map(function (_, j) {
    return puzzle[j].map(function (_, i) {
      return puzzle[i][j];
    }).join('');
  });
}

function enshapen(puzz, i, j) {
  puzz = puzz.replace(/ /g, '');
  var shapened = [], _i, _j;

  for (_i = 0; _i < i; _i++) {
    shapened[_i] = puzz.slice(j * _i, j * (_i + 1)).split('');
  }

  return shapened;
}

My Solution in 2020

// possible words
const words = ["lazy", "crackers", "hello", "cruel", "world", "bears", "need", "not", "apply"];

// characters
const puzzle = " \
r b f x w \
h e l l o \
o a h c r \
c r u e l \
v s u f d \
";

const WIDTH = 5;
const HEIGHT = 5;

function solve(puzzle, words) {
  const matrix = new Array(HEIGHT);

  matrix.fill(null);

  let n = 0;

  let i = 0;
  let j = 0;

  // There is probably a way to do Math to find the right
  // character given an i and j with the original input,
  // but for me it was worthwhile to do this cleanup.
  // The full algorithm is going to scale with WIDTH * HEIGHT
  // anyway so this doesn't add any runtime *complexity*
  // (though it does mean more space)
  for (let c of puzzle) {
    if (c === " ") {
      continue;
    }

    // Make sure data structures are filled
    if (!matrix[i]) {
      matrix[i] = new Array(WIDTH);
      matrix[i].fill(null);
    }

    // Fill it in
    matrix[i][j] = c;

    // Increment i
    i++;

    // Go to the next line if necessary
    if (i == WIDTH) {
      i = 0;
      j++;
    }
  }

  // Our stategy for searching is going to be scanning over all
  // characters, looking for ones that match the first letter of
  // the thing we're searching for. Once we find that, we can try
  // to see if there's a row or column match. We'll also want the
  // shortest word length for that character and overall for a
  // handful of optimizations.
  const index = new Map();
  let minWordSize = Infinity;

  for (let word of words) {
    // Track the minimum word length overall
    if (word.length < minWordSize) {
      minWordSize = word.length;
    }
    // Collect our candidates in a set and track the minimum
    // word length in that set
    if (!index.has(word[0])) {
      index.set(word[0], {candidates: new Set(), length: Infinity});
    }
    const value = index.get(word[0]);
    value.candidates.add(word);
    if (word.length < value.length) {
      value.length = word.length;
    }
  }

  const matches = [];

  for (let i = 0; i < HEIGHT; i++) {
    // The lower right corner can't have words longer than
    // its width/height in it, so if the row index is above
    // a certain size then the column index has a nice bound
    // and we get a tidy optimization
    const jUpperBound = (i >= (HEIGHT - minWordSize))
      ? WIDTH - minWordSize
      : WIDTH;

    for (let j = 0; j < jUpperBound; j++) {
      if (index.has(matrix[i][j])) {
        // The index matches the first character of some words!
        const {candidates, length} = index.get(matrix[i][j]);

        for (word of candidates) {
          // We know a'priori that if the word is too long
          // to fit that we can rule out a solution on that
          // axis
          let ruledOutRow = (i + word.length) > WIDTH;
          let ruledOutCol = (j + word.length) > HEIGHT;

          if (ruledOutRow && ruledOutCol) {
            continue;
          }

          // Now we can progressively check every other
          // character
          for (let n = 1; n < word.length; n++) {
            ruledOutRow = ruledOutRow || (matrix[i + n][j] !== word[n]);
            ruledOutCol = ruledOutCol || (matrix[i][j + n] !== word[n]);

            // If we ruled it out we can short circuit
            if (ruledOutRow && ruledOutCol) {
              break;
            }
          }

          // If we never ruled it out then we found a solution
          const foundSolution = !ruledOutRow || !ruledOutCol;

          if (foundSolution) {
            // Save our word
            matches.push(word);
            // Since we found the word we don't need to search
            // for a second match
            candidates.delete(word);
            // If we don't have any words for this character
            // anymore we can stop searching against it
            if (!candidates.size) {
              index.delete(matrix[i][j]);
            }
          }
        }
      }

      // If we've found every word we're done
      if (!index.size) {
        break;
      }
    }
    if (!index.size) {
      break;
    }
  }

  return matches;
};

console.log(solve(puzzle, words));
//=> ["hello", "cruel", "world", "bears"]