Avatar of tylus

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()
    local first, last = WordSearch(puzzle).find('haskell')
    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.
function Position:add(other)
  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 nextpos = pos:add(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

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?