test_wordsearch.py

import sys
import time
import functools
import timeit
import logging

directions = [
    (0, -1),  # north
    (0, 1),  # south
    (1, 0),   # east
    (-1, 0),   # west
    (-1, -1),   # north-west
    (1,  -1),  # north-east
    (-1, 1),  # south-west
    (1, 1),  # south-east
]

DEMO_MODE = False


def print_board(board, location, current_word, word_list):

    for x, line in enumerate(board):
        for y, char in enumerate(line):
            if (x, y) == location:
                print(f" *{char}* ", end="")
            else:
                print(f"  {char}  ", end="")
        print("")
        print("")
    for word in word_list:
        out = f' *{word}* ' if word == current_word else f"  {word}  "
        print(out, end=",")
    print("")
    time.sleep(0.01)

    for _ in range(len(board) * 2 + 1):
        sys.stdout.write("\x1b[1A\x1b[2K")  # move up cursor and delete whole line


def check_in_direction(direction, word, board, x, y, word_list):
    for c in word:
        if DEMO_MODE:
            print_board(board_realistic, (x, y), word, word_list)
        if x < 0 or y < 0 or y > len(board) - 1 or x > len(board) - 1:  # looking out of board range
            return False

        if not c == board[x][y]:
            return False
        x, y = x + direction[0], y + direction[1]

    return True


def check_wordsearch(board, words):
    for x, line in enumerate(board):
        for y, char in enumerate(line):
            for word in words:
                found_in_direction = []
                for direction in directions:
                    found_in_direction.append(check_in_direction(direction, word, board, x, y, words))
                if any(found_in_direction):
                    words.remove(word)
                    continue
    return not words


# testing

board_realistic = [
    ['m', 'x', 'a', 'f', 'g', 'j', 't'],
    ['d', 'r', 's', 'r', 'l', 'u', 'o'],
    ['d', 'r', 'g', 'r', 'a', 's', 'p'],
    ['o', 'e', 'e', 'w', 'd', 't', 'e'],
    ['f', 'w', 'r', 'f', 'e', 'x', 'd'],
    ['p', 'o', 'd', 'e', 'a', 'h', 'h'],
    ['j', 'c', 'x', 'm', 'p', 'w', 'c']
]

words_realistic = [
    "chew",
    "cower",
    "depot",
    "dregs",
    "exam",
    "fax",
    "fox",
    "glad",
    "just",
    "odd",
    "rasp",
    "wafer"
]


def test_01_sanity():
    board_minimal = [['w', 'b', 'c'],
                     ['a', 'a', 'c'],
                     ['a', 'b', 'r']]

    words_minimal = ['war', 'aac', 'bab', 'waa', 'caa', 'aac']

    assert check_wordsearch(board_minimal, words_minimal)


def test_02_real_life_example():
    assert check_wordsearch(board_realistic, words_realistic)


def test_02_real_life_example_timing():
    t = timeit.Timer(functools.partial(check_wordsearch, board_realistic, words_realistic))
    took = t.timeit(10000) * 1000.0
    logging.info(f'running 10000 took {took}ms')
    assert took < 35.0


def test_03_word_doesnt_exists():
    board_a = [['a', 'b', 'c'],
               ['a', 'b', 'c'],
               ['a', 'b', 'c']]

    words_a = ['ac', 'ab']

    assert not check_wordsearch(board_a, words_a)


if __name__ == "__main__":
    # demo
    DEMO_MODE = True
    assert check_wordsearch(board_realistic, words_realistic)