ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# tylus's solution

## to Word Search in the Lua Track

Published at May 07 2019 · 0 comments
Instructions
Test suite
Solution

In word search puzzles you get a square of letters and have to find specific words in them.

For example:

``````jefblpepre
camdcimgtc
oivokprjsm
pbwasqroua
rixilelhrs
wolcqlirpc
screeaumgr
alxhpburyi
jalaycalmp
clojurermt
``````

There are several programming languages hidden in the above square.

Words can be hidden in all kinds of directions: left-to-right, right-to-left, vertical and diagonal.

Given a puzzle and a list of words return the location of the first and last letter of each word.

## Running the tests

To run the tests, run the command `busted` from within the exercise directory.

## Further information

For more detailed information about the Lua track, including how to get help if you're having trouble, please visit the exercism.io Lua language page.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### word-search_spec.lua

``````local WordSearch = require('word-search')

describe('word-search', function()
local puzzle = {
'jefblpepre',
'camdcimgtc',
'oivokprjsm',
'pbwasqroua',
'rixilelhrs',
'wolcqlirpc',
'screeaumgr',
'alxhpburyi',
'jalaycalmp',
'clojurermt',
}

it('should find horizontal words written left-to-right', function()
local first, last = WordSearch(puzzle).find('clojure')
assert.same({ 1, 10 }, first)
assert.same({ 7, 10 }, last)
end)

it('should find horizontal words written right-to-left', function()
local first, last = WordSearch(puzzle).find('elixir')
assert.same({ 6, 5 }, first)
assert.same({ 1, 5 }, last)
end)

it('should find vertical words written top-to-bottom', function()
local first, last = WordSearch(puzzle).find('ecmascript')
assert.same({ 10, 1 }, first)
assert.same({ 10, 10 }, last)
end)

it('should find vertical words written bottom-to-top', function()
local first, last = WordSearch(puzzle).find('rust')
assert.same({ 9, 5 }, first)
assert.same({ 9, 2 }, last)
end)

it('should find diagonal words written top-left-to-bottom-right', function()
local first, last = WordSearch(puzzle).find('java')
assert.same({ 1, 1 }, first)
assert.same({ 4, 4 }, last)
end)

it('should find diagonal upper written bottom-right-to-top-left', function()
local first, last = WordSearch(puzzle).find('lua')
assert.same({ 8, 9 }, first)
assert.same({ 6, 7 }, last)
end)

it('should find diagonal upper written bottom-left-to-top-right', function()
local first, last = WordSearch(puzzle).find('lisp')
assert.same({ 3, 6 }, first)
assert.same({ 6, 3 }, last)
end)

it('should find diagonal upper written top-right-to-bottom-left', function()
local first, last = WordSearch(puzzle).find('ruby')
assert.same({ 8, 6 }, first)
assert.same({ 5, 9 }, last)
end)

it('should not find words that are not in the puzzle', function()
assert.same(nil, first)
assert.same(nil, last)
end)

it('should be able to search differently-sized puzzles', function()
local puzzle = {
'qwertyuiopz',
'luamsicrexe',
'abcdefghijk'
}
local first, last = WordSearch(puzzle).find('exercism')
assert.same({ 11, 2 }, first)
assert.same({ 4, 2 }, last)
end)
end)``````
``````--- A Position is point in euclidean space with integer offsets.
local Position = {}

function Position:new(x, y)
local o = {x=x, y=y}
setmetatable(o, self)
self.__index = self
return o
end

--- Returns a new point as the sum of this and the other point.
return Position:new(self.x + other.x, self.y + other.y)
end

--- True if the other object points at the same place as self.
function Position:__eq(other)
return self.x == other.x and self.y == other.y
end

--- Convert this Position into a two-item table for export.
function Position:toTable()
return {self.x, self.y}
end

--- The eight auspicious winds.
local dirs = {
Position:new( 1,  0),
Position:new( 1,  1),
Position:new( 0,  1),
Position:new(-1,  1),
Position:new(-1,  0),
Position:new(-1, -1),
Position:new( 0, -1),
Position:new( 1, -1),
}

--- The map is a handy representation of the puzzle.
-- It maps each existing character to a list of the positions
-- where that character can be found.
local function makeMap(puzzle)
local map = {}
local x
local y
for y, row in ipairs(puzzle) do
for x = 1, #row do
c = row:sub(x, x)
map[c] = map[c] or {}
table.insert(map[c], Position:new(x, y))
end
end
return map
end

--- Initialize the finder.
return function(puzzle)
local map = makeMap(puzzle)

--- Given a word, starting position, and direction, check if the word is there.
local function track(word, pos, dir)
local thischar = word:sub(1, 1)
local rest = word:sub(2)
local candidates = map[thischar]
if not candidates then return end

for _, candidate in ipairs(candidates) do
if nextpos == candidate then
if #word > 1 then
local chain = track(rest, nextpos, dir)
if chain then
table.insert(chain, 1, nextpos)
return chain
end
else
return {nextpos}
end
end
end
end

--- Wherever the first character appears in the puzzle, look around to see if the whole word is there.
local function scan(word)
local thischar = word:sub(1, 1)
local candidates = map[thischar]
for _, dir in ipairs(dirs) do
for _, first in ipairs(candidates) do
local chain = track(word:sub(2), first, dir)
if chain then
table.insert(chain, 1, first)
return chain
end
end
end
end

--- Look for the word.
-- If found, return the answer in the requested format.
local function find(word)
local chain = scan(word)
if chain then
return chain[1]:toTable(), chain[#chain]:toTable()
end
end

return {find = find}
end``````