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
endok search (24 cases)
test result: ok. 24 passed, 0 failed
How it’s written
Section titled “How it’s written”- The answer is a
Mapfrom each word toMaybe<Span>, as the canonical data maps each word to a location ornull. ASpanholds twoPositions, each a struct with the canonicalcolumnandrow, counted from 1. - The grid is a
Vectorof rows, each aVectorof the row’s letters as one-grapheme strings (Iter.to_vectorover aString), so a letter is read by its row and column. findis one lazy pipeline: every cell, then every one of the eight directions from it, thenIter.findfor the first pair from which the word reads, with a?after it that answersNonewhen no pair does. The directions are aoncelist of row and column steps, so the diagonals and the reversed words need no code of their own.readswalks the word’s letters with their index and compares each with the letter that many steps away.letter_atanswersNoneoff 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
subteststable named by the description column. Ten of them search the same ten-line puzzle, which is aoncein the test file; the grids that differ from it are written in their rows.