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

glennj's solution

to Word Search in the Lua Track

Published at Mar 15 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)``````
``````-----------------------------------------------------------------
-- Utility functions
-----------------------------------------------------------------

-- A "map" function that also passes the list index to the function
local mapi = function (list, func)
local result = {}
for i, elem in ipairs(list) do
result[i] = func(elem, i)
end
return result
end

--  '123',    '147',
--  '456', -> '258',
--  '789'     '369'
local transpose = function(list)
local result = {}
for col = 1, #list[1] do
result[col] = ""
for row = 1, #list do
result[col] = result[col] .. list[row]:sub(col,col)
end
end
return result
end

--  '123',    '321',
--  '456', -> '654',
--  '789'     '987'
local reverse = function(board)
return mapi(board, string.reverse)
end

--  '123',    '789',
--  '456', -> '456',
--  '789'     '123'
local invert = function(board)
return mapi(board, function(_, i)
return board[#board - i + 1]
end)
end

--  '123',    top     '  123',
--  '456', -> skew -> ' 456 ',
--  '789'             '789  '
--
--  '123',   bottom   '123  ',
--  '456', -> skew -> ' 456 ',
--  '789'             '  789'
local skew = function(top_or_bottom, board)
local is_top = top_or_bottom == "top"
return mapi(board, function(row, i)
local sp1, sp2 = #board - i, i - 1
return ("%s%s%s"):format(
(" "):rep(is_top and sp1 or sp2),
row,
(" "):rep(is_top and sp2 or sp1)
)
end)
end

-----------------------------------------------------------------
-- the WordSearch object
--
-- A frustrating amount of very similar methods that are just
-- different enough to prevent much code reuse.
--
-- My approach here is to only use left-to-right searching to
-- actually find the word, and then for all other directions,
-- I transform the puzzle itself to search left-to-right and
-- then remap the found coordinates.
--
-- For example, searching for "159"
--
-- '123',    '  123',    '  7',
-- '456', => ' 456 ', => ' 48',
-- '789'     '789  '     '159',  << found left-to-right
--                       '26 ',
--                       '3  '
--
-- Then remap {{1,3},{3,3} to {{3,1},{3,3}} to {{1,1},{3,3}}
-----------------------------------------------------------------

return function(puzzle)
local left2right = function(word, board)
board = board or puzzle
for y = 1, #board do
for x = 1, #board[1] - #word + 1 do
if word == board[y]:sub(x, x + #word - 1) then
return {x, y}, {x + #word - 1, y}
end
end
end
end

local right2left = function(word)
local board = reverse(puzzle)
local first, last = left2right(word, board)
if first then
first = {#board[1] - first[1] + 1, first[2]}
last  = {#board[1] - last[1]  + 1, last[2]}
return first, last
end
end

local top2bottom = function(word, board)
board = transpose(board or puzzle)
local first, last = left2right(word, board)
if first then
return {first[2], first[1]}, {last[2], last[1]}
end
end

local bottom2top = function(word)
local board = invert(puzzle)
local first, last = top2bottom(word, board)
if first then
first = {first[1], #board - first[2] + 1}
last  = {last[1],  #board - last[2]  + 1}
return first, last
end
end

local topleft2bottomright = function(word)
board = skew("top", puzzle)
local first, last = top2bottom(word, board)
if first then
first = {first[1] - (#board - first[2]), first[2]}
last  = {last[1]  - (#board - last[2]),  last[2]}
return first, last
end
end

local bottomleft2topright = function(word)
local board = invert(skew("top", puzzle))
local first, last = top2bottom(word, board)
if first then
first = {first[1] - (first[2] - 1), #board - first[2] + 1}
last  = {last[1]  - (last[2] - 1),  #board - last[2]  + 1}
return first, last
end
end

local topright2bottomleft = function(word)
board = skew("bottom", puzzle)
local first, last = top2bottom(word, board)
if first then
first = {first[1] - (first[2] - 1), first[2]}
last  = {last[1]  - (last[2]  - 1), last[2]}
return first, last
end
end

local bottomright2topleft = function(word)
local board = invert(skew("bottom", puzzle))
local first, last = top2bottom(word, board)
if first then
first = {first[1] - (#board - first[2]), #board - first[2] + 1}
last  = {last[1]  - (#board - last[2]),  #board - last[2]  + 1}
return first, last
end
end

return {
find = function(word)
for _,search_func in ipairs({
left2right,
right2left,
top2bottom,
bottom2top,
topleft2bottomright,
bottomleft2topright,
topright2bottomleft,
bottomright2topleft,
})
do
first, last = search_func(word)
if first then return first, last end
end
end,
}
end``````