This Week in Dev

JavaScript Word-Search Puzzle

Revisiting JavaScript this week - I think my solution to the wordsearch puzzle grid problem is particularly elegant. Check out my Solution here

I also tweeted about an elegant recursive algorithm I devised to generate integer sequences in JavaScript (which is utilized in the word search challenge) Some languages (Ruby, Haskell) use syntax like [1..10] to represent an integer sequence, but JavaScript doesn’t have a built-in way to do this, so I created my own.

function intSequence(start, end, n = start, arr = []) {
    return n === end ? arr.concat(n)
        : intSequence(start, end, start < end ? n + 1 : n - 1, arr.concat(n));
}

Wordsearch Solution

export default class WordSearch {
    constructor(grid) {
        this.yMax = grid.length;
        this.xMax = grid[0].length;
        this.searchMatrix = grid;
    }

    find(words) {
        let remit = {};
        for (const word of words) {
            let starts = this.findFirstLetter(word[0]);
            for (const start of starts) {
                const ends = this.findLastLetter(start, word);
                for (const end of ends) {
                    remit[word] = this.validateWordExistsAtVector(start, end, word)
                        ? {start: [start.y + 1, start.x + 1], end: [end.y + 1, end.x + 1]}
                        : undefined;
                }
            }
        }
        return remit;
    }

    validateWordExistsAtVector(start, end, word) {
        const yVector = intSequence(start.y, end.y);
        const xVector = intSequence(start.x, end.x);
        const yLen = yVector.length;
        const xLen = xVector.length;

        return [...word].every((letter, i) =>
            this.searchMatrix[yVector[i%yLen]][xVector[i%xLen]] === letter);
    }


    findLastLetter(start, word) {
        const length = word.length - 1;
        const lastLetter = word[length];
        const {y, x} = start;
        const potentialEndpoints = [
            {y: y         , x: x + length},
            {y: y         , x: x - length},
            {y: y + length, x: x         },
            {y: y - length, x: x         },
            {y: y + length, x: x + length},
            {y: y + length, x: x - length},
            {y: y - length, x: x + length},
            {y: y - length, x: x - length}
        ];

        return potentialEndpoints.filter(({y, x}) =>
            this.searchMatrix.hasOwnProperty(y)
                && this.searchMatrix[y][x] === lastLetter);
    }

    findFirstLetter(letter) {
        let remit = [];
        for (let y = 0; y < this.yMax; y++) {
            for (let x = 0; x < this.xMax; x++) {
                if (this.searchMatrix[y][x] === letter) {
                    remit.push({y, x});
                }
            }
        }
        return remit;
    }
}    

Jest unit tests for word-search (exercism.io):

import WordSearch from './word-search';

describe('single line grids', () => {
  test('Should accept an initial game grid', () => {
    const grid = ['jefblpepre'];
    const wordSearch = new WordSearch(grid);

    expect(wordSearch instanceof WordSearch).toEqual(true);
  });

  test('can accept a target search word', () => {
    const grid = ['jefblpepre'];
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['glasnost'])).toEqual({ glasnost: undefined });
  });

  test('should locate a word written left to right', () => {
    const grid = ['clojurermt'];
    const expectedResults = {
      clojure: {
        start: [1, 1],
        end: [1, 7],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });

  test('can locate a left to right word in a different position', () => {
    const grid = ['mtclojurer'];
    const expectedResults = {
      clojure: {
        start: [1, 3],
        end: [1, 9],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });

  test('can locate a different left to right word', () => {
    const grid = ['coffeelplx'];
    const expectedResults = {
      coffee: {
        start: [1, 1],
        end: [1, 6],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['coffee'])).toEqual(expectedResults);
  });
  test('can locate that different left to right word in a different position', () => {
    const grid = ['xcoffeezlp'];
    const expectedResults = {
      coffee: {
        start: [1, 2],
        end: [1, 7],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['coffee'])).toEqual(expectedResults);
  });
});

describe('multi line grids', () => {
  test('can locate a left to right word in a two line grid', () => {
    const grid = [
      'jefblpepre',
      'clojurermt',
    ];

    const expectedResults = {
      clojure: {
        start: [2, 1],
        end: [2, 7],
      },
    };

    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });
  test('can locate a left to right word in a different position in a two line grid', () => {
    const grid = [
      'jefblpepre',
      'tclojurerm',
    ];
    const expectedResults = {
      clojure: {
        start: [2, 2],
        end: [2, 8],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });
  test('can locate a left to right word in a three line grid', () => {
    const grid = [
      'camdcimgtc',
      'jefblpepre',
      'clojurermt',
    ];
    const expectedResults = {
      clojure: {
        start: [3, 1],
        end: [3, 7],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });

  test('can locate a left to right word in a ten line grid', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];

    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });

  test('can locate a left to right word in a different position in a ten line grid', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'clojurermt',
      'jalaycalmp',
    ];

    const expectedResults = {
      clojure: {
        start: [9, 1],
        end: [9, 7],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['clojure'])).toEqual(expectedResults);
  });
  test('can locate a different left to right word in a ten line grid', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'clojurermt',
      'jalaycalmp',
    ];
    const expectedResults = {
      scree: {
        start: [7, 1],
        end: [7, 5],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['scree'])).toEqual(expectedResults);
  });
});


describe('can find multiple words', () => {
  test('can find two words written left to right', () => {
    const grid = [
      'aefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
      'xjavamtzlp',
    ];
    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      java: {
        start: [11, 2],
        end: [11, 5],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['java', 'clojure'])).toEqual(expectedResults);
  });
});

describe('different directions', () => {
  test('should locate a single word written right to left', () => {
    const grid = ['rixilelhrs'];
    const expectedResults = {
      elixir: {
        start: [1, 6],
        end: [1, 1],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['elixir'])).toEqual(expectedResults);
  });
  test('should locate multiple words written in different horizontal directions', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];
    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['elixir', 'clojure'])).toEqual(expectedResults);
  });
});

describe('vertical directions', () => {
  test('should locate words written top to bottom', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];
    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
      ecmascript: {
        start: [1, 10],
        end: [10, 10],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['elixir', 'clojure', 'ecmascript'])).toEqual(expectedResults);
  });
  test('should locate words written bottom to top', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];
    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
      ecmascript: {
        start: [1, 10],
        end: [10, 10],
      },
      rust: {
        start: [5, 9],
        end: [2, 9],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find(['elixir', 'clojure', 'ecmascript', 'rust'])).toEqual(expectedResults);
  });
  test('should locate words written top left to bottom right', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];
    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
      ecmascript: {
        start: [1, 10],
        end: [10, 10],
      },
      rust: {
        start: [5, 9],
        end: [2, 9],
      },
      java: {
        start: [1, 1],
        end: [4, 4],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find([
      'clojure',
      'elixir',
      'ecmascript',
      'rust',
      'java',
    ])).toEqual(expectedResults);
  });
  test('should locate words written bottom right to top left', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];

    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
      ecmascript: {
        start: [1, 10],
        end: [10, 10],
      },
      rust: {
        start: [5, 9],
        end: [2, 9],
      },
      java: {
        start: [1, 1],
        end: [4, 4],
      },
      lua: {
        start: [9, 8],
        end: [7, 6],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find([
      'clojure',
      'elixir',
      'ecmascript',
      'rust',
      'java',
      'lua',
    ])).toEqual(expectedResults);
  });
  test('should locate words written bottom left to top right', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];
    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
      ecmascript: {
        start: [1, 10],
        end: [10, 10],
      },
      rust: {
        start: [5, 9],
        end: [2, 9],
      },
      java: {
        start: [1, 1],
        end: [4, 4],
      },
      lua: {
        start: [9, 8],
        end: [7, 6],
      },
      lisp: {
        start: [6, 3],
        end: [3, 6],
      },
    };

    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find([
      'clojure',
      'elixir',
      'ecmascript',
      'rust',
      'java',
      'lua',
      'lisp',
    ])).toEqual(expectedResults);
  });
  test('should locate words written top right to bottom left', () => {
    const grid = [
      'jefblpepre',
      'camdcimgtc',
      'oivokprjsm',
      'pbwasqroua',
      'rixilelhrs',
      'wolcqlirpc',
      'screeaumgr',
      'alxhpburyi',
      'jalaycalmp',
      'clojurermt',
    ];

    const expectedResults = {
      clojure: {
        start: [10, 1],
        end: [10, 7],
      },
      elixir: {
        start: [5, 6],
        end: [5, 1],
      },
      ecmascript: {
        start: [1, 10],
        end: [10, 10],
      },
      rust: {
        start: [5, 9],
        end: [2, 9],
      },
      java: {
        start: [1, 1],
        end: [4, 4],
      },
      lua: {
        start: [9, 8],
        end: [7, 6],
      },
      lisp: {
        start: [6, 3],
        end: [3, 6],
      },
      ruby: {
        start: [6, 8],
        end: [9, 5],
      },
    };
    const wordSearch = new WordSearch(grid);

    expect(wordSearch.find([
      'clojure',
      'elixir',
      'ecmascript',
      'rust',
      'java',
      'lua',
      'lisp',
      'ruby',
    ])).toEqual(expectedResults);
  });
});