Skip to content

Word Search

Find where each of a list of words lies in a square of letters, reading in any of the eight directions, by its first and last letter.

Adapted from Exercism’s problem specification (MIT). Listed under Grids & Matrices.

// FILE: word_search.nomi
//# Finds words in a grid of letters, in any of eight directions.

/// A letter's place in the puzzle, counted from 1 at the top left.
pub struct Position
    column: Int
    row:    Int
end

/// Where a word lies: its first letter and its last.
pub struct Span
    start: Position
    stop:  Position
end

/// The eight directions a word may run in, as a step in rows and a step in
/// columns.
once directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]

/// Where each of `words` lies in the rows of `grid`, or `None` for a word
/// that is not there.
pub fn search(grid: List<String>, words: List<String>) -> Map<String, Maybe<Span>>
    letters =
        grid
        |> Iter.map(Iter.to_vector)
        |> Iter.to_vector()

    words
    |> Iter.map(fn word -> (word, find(letters, word)))
    |> Iter.to_map()
end

/// Where `word` lies in `letters`: the first cell and direction from which
/// its letters read in order.
fn find(letters: Vector<Vector<String>>, word: String) -> Maybe<Span>
    spelling = Iter.to_list(word)
    last = Iter.count(spelling) - 1

    ((row, column), (down, across)) =
        letters
        |> Iter.with_index()
        |> Iter.flat_map(fn (row, line) -> Iter.map(0..Vector.length(line), &(row, &1)))
        |> Iter.flat_map(fn cell -> Iter.map(directions, &(cell, &1)))
        |> Iter.find(fn (cell, step) -> reads(letters, spelling, cell, step))?

    Some(Span{
        start: {column: column + 1, row: row + 1},
        stop:  {column: column + 1 + across * last, row: row + 1 + down * last},
    })
end

/// Whether `spelling` reads from the cell at `row` and `column`, stepping
/// `down` rows and `across` columns between letters, without leaving the
/// grid.
fn reads(
    letters:  Vector<Vector<String>>,
    spelling: List<String>,
    (row, column): (Int, Int),
    (down, across): (Int, Int),
) -> Bool
    spelling
    |> Iter.with_index()
    |> Iter.all_match(fn (i, letter) ->
        letter_at(letters, row + down * i, column + across * i) == Some(letter)
    end)
end

fn letter_at(letters: Vector<Vector<String>>, row: Int, column: Int) -> Maybe<String>
    letters |> Vector.get(row)? |> Vector.get(column)
end

// FILE: word_search_test.nomi
import word_search.{self, Span}

once puzzle = [
    "jefblpepre",
    "camdcimgtc",
    "oivokprjsm",
    "pbwasqroua",
    "rixilelhrs",
    "wolcqlirpc",
    "screeaumgr",
    "alxhpburyi",
    "jalaycalmp",
    "clojurermt",
]

test "search"
    cases: List<(String, List<String>, List<String>, Map<String, Maybe<Span>>)> = [
        (
            "Should accept an initial game grid and a target search word",
            ["jefblpepre"],
            ["clojure"],
            {"clojure" => None},
        ),
        ("Should locate one word written left to right", ["clojurermt"], ["clojure"], {
            "clojure" => Some({start: {column: 1, row: 1}, stop: {column: 7, row: 1}}),
        }),
        (
            "Should locate the same word written left to right in a different position",
            ["mtclojurer"],
            ["clojure"],
            {
                "clojure" => Some({start: {column: 3, row: 1}, stop: {column: 9, row: 1}}),
            },
        ),
        ("Should locate a different left to right word", ["coffeelplx"], ["coffee"], {
            "coffee" => Some({start: {column: 1, row: 1}, stop: {column: 6, row: 1}}),
        }),
        (
            "Should locate that different left to right word in a different position",
            ["xcoffeezlp"],
            ["coffee"],
            {
                "coffee" => Some({start: {column: 2, row: 1}, stop: {column: 7, row: 1}}),
            },
        ),
        (
            "Should locate a left to right word in two line grid",
            ["jefblpepre", "tclojurerm"],
            ["clojure"],
            {
                "clojure" => Some({start: {column: 2, row: 2}, stop: {column: 8, row: 2}}),
            },
        ),
        (
            "Should locate a left to right word in three line grid",
            ["camdcimgtc", "jefblpepre", "clojurermt"],
            ["clojure"],
            {
                "clojure" => Some({start: {column: 1, row: 3}, stop: {column: 7, row: 3}}),
            },
        ),
        ("Should locate a left to right word in ten line grid", puzzle, ["clojure"], {
            "clojure" => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
        }),
        (
            "Should locate that left to right word in a different position in a ten line grid",
            [
                "jefblpepre",
                "camdcimgtc",
                "oivokprjsm",
                "pbwasqroua",
                "rixilelhrs",
                "wolcqlirpc",
                "screeaumgr",
                "alxhpburyi",
                "clojurermt",
                "jalaycalmp",
            ],
            ["clojure"],
            {
                "clojure" => Some({start: {column: 1, row: 9}, stop: {column: 7, row: 9}}),
            },
        ),
        (
            "Should locate a different left to right word in a ten line grid",
            [
                "jefblpepre",
                "camdcimgtc",
                "oivokprjsm",
                "pbwasqroua",
                "rixilelhrs",
                "wolcqlirpc",
                "fortranftw",
                "alxhpburyi",
                "clojurermt",
                "jalaycalmp",
            ],
            ["fortran"],
            {
                "fortran" => Some({start: {column: 1, row: 7}, stop: {column: 7, row: 7}}),
            },
        ),
        (
            "Should locate multiple words",
            [
                "jefblpepre",
                "camdcimgtc",
                "oivokprjsm",
                "pbwasqroua",
                "rixilelhrs",
                "wolcqlirpc",
                "fortranftw",
                "alxhpburyi",
                "jalaycalmp",
                "clojurermt",
            ],
            ["fortran", "clojure"],
            {
                "clojure" => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "fortran" => Some({start: {column: 1, row: 7}, stop: {column: 7, row: 7}}),
            },
        ),
        ("Should locate a single word written right to left", ["rixilelhrs"], ["elixir"], {
            "elixir" => Some({start: {column: 6, row: 1}, stop: {column: 1, row: 1}}),
        }),
        (
            "Should locate multiple words written in different horizontal directions",
            puzzle,
            ["elixir", "clojure"],
            {
                "clojure" => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"  => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
            },
        ),
        (
            "Should locate words written top to bottom",
            puzzle,
            ["clojure", "elixir", "ecmascript"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
            },
        ),
        (
            "Should locate words written bottom to top",
            puzzle,
            ["clojure", "elixir", "ecmascript", "rust"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
                "rust"       => Some({start: {column: 9, row: 5}, stop: {column: 9, row: 2}}),
            },
        ),
        (
            "Should locate words written top left to bottom right",
            puzzle,
            ["clojure", "elixir", "ecmascript", "rust", "java"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
                "rust"       => Some({start: {column: 9, row: 5}, stop: {column: 9, row: 2}}),
                "java"       => Some({start: {column: 1, row: 1}, stop: {column: 4, row: 4}}),
            },
        ),
        (
            "Should locate words written bottom right to top left",
            puzzle,
            ["clojure", "elixir", "ecmascript", "rust", "java", "lua"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
                "rust"       => Some({start: {column: 9, row: 5}, stop: {column: 9, row: 2}}),
                "java"       => Some({start: {column: 1, row: 1}, stop: {column: 4, row: 4}}),
                "lua"        => Some({start: {column: 8, row: 9}, stop: {column: 6, row: 7}}),
            },
        ),
        (
            "Should locate words written bottom left to top right",
            puzzle,
            ["clojure", "elixir", "ecmascript", "rust", "java", "lua", "lisp"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
                "rust"       => Some({start: {column: 9, row: 5}, stop: {column: 9, row: 2}}),
                "java"       => Some({start: {column: 1, row: 1}, stop: {column: 4, row: 4}}),
                "lua"        => Some({start: {column: 8, row: 9}, stop: {column: 6, row: 7}}),
                "lisp"       => Some({start: {column: 3, row: 6}, stop: {column: 6, row: 3}}),
            },
        ),
        (
            "Should locate words written top right to bottom left",
            puzzle,
            ["clojure", "elixir", "ecmascript", "rust", "java", "lua", "lisp", "ruby"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
                "rust"       => Some({start: {column: 9, row: 5}, stop: {column: 9, row: 2}}),
                "java"       => Some({start: {column: 1, row: 1}, stop: {column: 4, row: 4}}),
                "lua"        => Some({start: {column: 8, row: 9}, stop: {column: 6, row: 7}}),
                "lisp"       => Some({start: {column: 3, row: 6}, stop: {column: 6, row: 3}}),
                "ruby"       => Some({start: {column: 8, row: 6}, stop: {column: 5, row: 9}}),
            },
        ),
        (
            "Should fail to locate a word that is not in the puzzle",
            puzzle,
            ["clojure", "elixir", "ecmascript", "rust", "java", "lua", "lisp", "ruby", "haskell"],
            {
                "clojure"    => Some({start: {column: 1, row: 10}, stop: {column: 7, row: 10}}),
                "elixir"     => Some({start: {column: 6, row: 5}, stop: {column: 1, row: 5}}),
                "ecmascript" => Some({start: {column: 10, row: 1}, stop: {column: 10, row: 10}}),
                "rust"       => Some({start: {column: 9, row: 5}, stop: {column: 9, row: 2}}),
                "java"       => Some({start: {column: 1, row: 1}, stop: {column: 4, row: 4}}),
                "lua"        => Some({start: {column: 8, row: 9}, stop: {column: 6, row: 7}}),
                "lisp"       => Some({start: {column: 3, row: 6}, stop: {column: 6, row: 3}}),
                "ruby"       => Some({start: {column: 8, row: 6}, stop: {column: 5, row: 9}}),
                "haskell"    => None,
            },
        ),
        (
            "Should fail to locate words that are not on horizontal, vertical, or diagonal lines",
            ["abc", "def"],
            ["aef", "ced", "abf", "cbd"],
            {"aef" => None, "ced" => None, "abf" => None, "cbd" => None},
        ),
        (
            "Should not concatenate different lines to find a horizontal word",
            ["abceli", "xirdfg"],
            ["elixir"],
            {"elixir" => None},
        ),
        (
            "Should not wrap around horizontally to find a word",
            ["silabcdefp"],
            ["lisp"],
            {"lisp" => None},
        ),
        (
            "Should not wrap around vertically to find a word",
            ["s", "u", "r", "a", "b", "c", "t"],
            ["rust"],
            {"rust" => None},
        ),
    ]

    subtests cases, (description, grid, words, expected), description
        assert word_search.search(grid, words) == expected
    end
end
  • The answer is a Map from each word to Maybe<Span>, as the canonical data maps each word to a location or null. A Span holds two Positions, each a struct with the canonical column and row, counted from 1.
  • The grid is a Vector of rows, each a Vector of the row’s letters as one-grapheme strings (Iter.to_vector over a String), so a letter is read by its row and column.
  • find is one lazy pipeline: every cell, then every one of the eight directions from it, then Iter.find for the first pair from which the word reads, with a ? after it that answers None when no pair does. The directions are a once list of row and column steps, so the diagonals and the reversed words need no code of their own.
  • reads walks the word’s letters with their index and compares each with the letter that many steps away. letter_at answers None off the grid, so a word that would run past an edge, or wrap to the next line, simply does not read; that is what the four “should not” cases check.
  • The canonical cases are one subtests table named by the description column. Ten of them search the same ten-line puzzle, which is a once in the test file; the grids that differ from it are written in their rows.