Board.php

<?php

use Config;
use Illuminate\Support\Contracts\ArrayableInterface;

class Board implements ArrayableInterface
{
    /**
     * Easy Difficulty
     *
     * Words are inserted either horizontally or vertically.
     */
    const EASY_DIFFICULTY = 1;

    /**
     * Medium Difficulty
     *
     * The words are inserted diagonally, horizonally or vertically.
     */
    const MEDIUM_DIFFICULTY = 2;

    /**
     * Hard Difficulty
     *
     * The words are inserted in the following fashions:
     *  Backwards Horizontally, Vertically, or Diagonally
     *  Vertically
     *  Horizontally
     */
    const HARD_DIFFICULTY = 3;

    /**
     * The number of times to try and insert a word into the board
     */
    const MAXIMUM_ATTEMPTS = 100;

    const MAXIMUM_GENERATE_ATTEMPTS = 200;

    /**
     * The UUID of the board
     *
     * @var string
     */
    protected $id;

    /**
     * The time, in seconds, you have to complete the board.
     *
     * @var int
     */
    protected $time;

    /**
     * The actual array for maintaining the boards state.
     *
     * @var array
     */
    protected $board = [];

    /**
     * The array of words to be found in the board
     *
     * @var array
     */
    protected $words;

    /**
     * The array for maintaining word start and end positions
     *
     * @var array
     */
    protected $wordPositions = [];

    /**
     * The difficulty of the board
     *
     * @var int
     */
    protected $difficulty;

    /**
     * The number of rows the board has, minus one
     *
     * @var int
     */
    protected $rows;

    /**
     * The number of columns the board has, minus one
     *
     * @var int
     */
    protected $columns;

    /**
     * Difficulty distributions for how to insert the word into the board.
     *
     * @var array
     */
    protected $distributions = [];

    /**
     * Constructs a new instance of a Word Search Board
     *
     * @param array $words
     * @param int   $difficulty
     * @param int   $rows
     * @param int   $columns
     *
     * @throws InvalidBoardException
     */
    public function __construct(array $words, $difficulty, $rows, $columns)
    {
        $this->words        = $words;
        $this->difficulty   = $difficulty;
        $this->rows         = $rows;
        $this->columns      = $columns;
        $this->distribution = Config::get('word_distributions')[$this->difficulty];
        $this->initializeBoard();
        $this->sortWordsByLength();
        $this->formatWords();
    }

    /**
     * Creates the board, based on its difficulty and words
     *
     * @return boolean
     */
    public function create()
    {
        $attempts = 0;
        foreach ($this->words as $word) {
            $successful = false;
            while (!$successful && $attempts < self::MAXIMUM_GENERATE_ATTEMPTS) {
                $insertionMethod = WeightedArrayRandom::randomize($this->distribution);
                $successful      = $this->{$insertionMethod}($word);
                $attempts++;
            }
        }

        if ($successful) {
            $this->finalizeBoard();
        }

        return $successful;
    }

    public function isValid()
    {
        try {
            $this->checkForValidWords();
        } catch (InvalidBoardException $e) {
            \Log::error($e->getMessage());

            return false;
        }

        return true;
    }

    /**
     * @return string
     */
    public function getId()
    {
        return $this->id;
    }

    /**
     * @param string $id
     */
    public function setId($id)
    {
        $this->id = $id;
    }

    /**
     * @return int
     */
    public function getTime()
    {
        return $this->time;
    }

    /**
     * @param int $time
     */
    public function setTime($time)
    {
        $this->time = $time;
    }

    protected function insertWordHorizontally($word)
    {
        $wordLength = strlen(trim($word->word));
        $successful = false;

        for ($attempts = 0; $attempts < self::MAXIMUM_ATTEMPTS; $attempts++) {
            $board         = $this->board;
            $wordPositions = $this->wordPositions;
            $wordRow       = rand(0, $this->rows - 1);
            $wordCol       = rand(0, $this->columns - 1 - $wordLength);

            for ($i = 0; $i < $wordLength; $i++) {
                $boardLetter = $board[$wordRow][$wordCol + $i];

                if (!$this->isValidPlacement($boardLetter, $word->word[$i])) {
                    $successful = false;
                    break;
                }

                $board         = $this->insertWordIntoBoard($word->word[$i], $wordRow, $wordCol + $i, $board);
                $wordPositions = $this->insertWordUUIDIntoPositions(
                    $word->uuid,
                    $wordRow,
                    $wordCol + $i,
                    $wordPositions
                );
                $successful    = true;
            }

            if ($successful) {
                $this->setBoard($board);
                $this->setWordPositions($wordPositions);
                break;
            }
        }

        return $successful;
    }

    protected function insertWordVertically($word)
    {
        $wordLength = strlen(trim($word->word));
        $successful = false;

        for ($attempts = 0; $attempts < self::MAXIMUM_ATTEMPTS; $attempts++) {
            $board         = $this->board;
            $wordPositions = $this->wordPositions;
            $wordRow       = rand(0, $this->rows - 1 - $wordLength);
            $wordCol       = rand(0, $this->columns - 1);

            for ($i = 0; $i < $wordLength; $i++) {
                $boardLetter = $board[$wordRow + $i][$wordCol];

                if (!$this->isValidPlacement($boardLetter, $word->word[$i])) {
                    $successful = false;
                    break;
                }

                $board         = $this->insertWordIntoBoard($word->word[$i], $wordRow + $i, $wordCol, $board);
                $wordPositions = $this->insertWordUUIDIntoPositions(
                    $word->uuid,
                    $wordRow + $i,
                    $wordCol,
                    $wordPositions
                );
                $successful    = true;
            }

            if ($successful) {
                $this->setBoard($board);
                $this->setWordPositions($wordPositions);
                break;
            }
        }

        return $successful;
    }

    protected function insertWordDiagonally($word)
    {
        $wordLength = strlen(trim($word->word));
        $successful = false;

        for ($attempts = 0; $attempts < self::MAXIMUM_ATTEMPTS; $attempts++) {
            $board         = $this->board;
            $wordPositions = $this->wordPositions;
            $wordRow       = rand(0, $this->rows - 1 - $wordLength);
            $wordCol       = rand(0, $this->columns - 1 - $wordLength);

            for ($i = 0; $i < $wordLength; $i++) {
                $boardLetter = $board[$wordRow + $i][$wordCol + $i];

                if (!$this->isValidPlacement($boardLetter, $word->word[$i])) {
                    $successful = false;
                    break;
                }

                $board         = $this->insertWordIntoBoard($word->word[$i], $wordRow + $i, $wordCol + $i, $board);
                $wordPositions = $this->insertWordUUIDIntoPositions(
                    $word->uuid,
                    $wordRow + $i,
                    $wordCol + $i,
                    $wordPositions
                );
                $successful    = true;
            }

            if ($successful) {
                $this->setBoard($board);
                $this->setWordPositions($wordPositions);
                break;
            }
        }

        return $successful;
    }

    protected function insertWordReversedDiagonally($word)
    {
        $word = clone $word;
        $word->word = strrev($word->word);

        return $this->insertWordDiagonally($word);
    }

    protected function insertWordReversedHorizontally($word)
    {
        $word = clone $word;
        $word->word = strrev($word->word);

        return $this->insertWordHorizontally($word);
    }

    protected function insertWordReversedVertically($word)
    {
        $word = clone $word;
        $word->word = strrev($word->word);

        return $this->insertWordVertically($word);
    }

    /**
     * Inserts the letter into the board based on row & column.
     *
     * @param array  $board  The word search board
     * @param string $letter The letter to insert
     * @param int    $row    The row to insert at
     * @param int    $col    The column to insert at
     *
     * @return array
     */
    protected function insertWordIntoBoard($letter, $row, $col, array $board)
    {
        $board[$row][$col] = $letter;

        return $board;
    }

    /**
     * Inserts the word uuid into the positions board based on row & column.
     *
     * @param string $wordId
     * @param int    $row
     * @param int    $col
     * @param array  $wordPositions
     *
     * @return array
     */
    protected function insertWordUUIDIntoPositions($wordId, $row, $col, array &$wordPositions = [])
    {
        $wordPositions[$row][$col][] = $wordId;

        return $wordPositions;
    }

    protected function initializeBoard()
    {
        foreach (range(0, $this->rows - 1) as $row) {
            foreach (range(0, $this->columns - 1) as $col) {
                $this->board[$row][$col]         = null;
                $this->wordPositions[$row][$col] = null;
            }
        }
    }

    protected function finalizeBoard()
    {
        foreach (range(0, $this->rows - 1) as $row) {
            foreach (range(0, $this->columns - 1) as $col) {
                if (is_null($this->board[$row][$col])) {
                    $this->board[$row][$col] = chr(mt_rand(65, 90));
                }
            }
        }
    }

    protected function checkForValidWords()
    {
        if (empty($this->words)) {
            throw new InvalidBoardException('Cannot create a board with no words!');
        }

        foreach ($this->words as $word) {
            $word       = $word->word;
            $wordLength = strlen($word);

            if ($wordLength > $this->rows || $wordLength > $this->columns) {
                throw new InvalidBoardException('One or more of the words does not fit on the board');
            }
        }
    }

    protected function sortWordsByLength()
    {
        $words = $this->words;
        usort($words, function ($a, $b) {
            return strcasecmp($a->word, $b->word);
        });
        usort($words, function ($a, $b) {
            return strlen($b->word) - strlen($a->word);
        });
        $this->words = $words;
    }

    /**
     * Get the instance as an array.
     *
     * @return array
     */
    public function toArray()
    {
        $returnBoard = array(
            'id'   => $this->getId(),
            'time' => $this->getTime()
        );
        $returnBoard = $this->buildWordList($returnBoard);
        foreach ($this->board as $key => $row) {
            $returnBoard['board'][$key] = array(
                'row' => $key + 1
            );

            foreach ($row as $cKey => $col) {
                $letter = array(
                    'letter' => $col
                );

                if (!empty($this->wordPositions[$key][$cKey])) {
                    $letter['words'] = $this->wordPositions[$key][$cKey];
                }

                $returnBoard['board'][$key]['letters'][] = $letter;
            }
        }

        return $returnBoard;
    }

    protected function buildWordList(array $returnBoard)
    {
        foreach ($this->words as $word) {
            $returnBoard['words'][] = array(
                'id'   => $word->uuid,
                'word' => $word->word
            );
        }

        return $returnBoard;
    }

    protected function formatWords()
    {
        array_walk($this->words, function (&$value) {
            $value->word = strtoupper($value->word);
        });
    }

    /**
     * @param $board
     */
    protected function setBoard($board)
    {
        $this->board = $board;
    }

    /**
     * @param $wordPositions
     */
    protected function setWordPositions($wordPositions)
    {
        $this->wordPositions = $wordPositions;
    }

    /**
     * @param $boardLetter
     * @param $wordLetter
     *
     * @return bool
     */
    protected function isValidPlacement($boardLetter, $wordLetter)
    {
        return $boardLetter === $wordLetter || is_null($boardLetter);
    }
}