Устраиваемся на работу в Airbnb

Конечно же на должность программиста.
В сети опубликованы каверзные вопросы на различные должности в этой компании. Меня заинтересовал вопрос по программированию. Собственно вот он.

Задача

Вам дают словарь и матрицу букв. Найдите слова в матрице, которые есть в словаре.

Визуализируем задачу

То есть попробуйте найти слова из правой колонки в матрице символов. Слова могут "извиваться змейкой" по горизонтали и вертикали. Какие-то слова могут присутствовать в матрице, какие-то нет. Каждое слово ищется "по новой", то есть любая клетка матрицы может быть использована для нахождения разных слов.
Задачу такого масштаба можно решить вручную. А представьте, что у вас 10000 слов и матрица размерами 500х800 клеток.

Решение

Давайте пронумеруем строки и столбцы матрицы.

Теперь будем обходить по очереди все слова из списка и искать их в матрице.

Принцип поиска

Берём первую букву слова и ищем её в матрице, запоминаем координаты. Если буква повторяется - запоминаем их все и обходим поочерёдно, пока не составим слово полностью или не убедимся в отсутствии решения.

Для удобства занесём матрицу в базу данных типа MySQL(или любую другую, можно даже нереляционную) в формате:

letter	x	y
а	3	5
б	3	2
б	4	7
р	12	1

И так далее.

Если в матрице получается найти первую букву - смотрим смежные 4 клетки и ищем в них вторую и так далее. Если текущая буква находится в крайней строке или столбце - то три смежные буквы, если в углу - то две.
Если слово в матрице "ветвится" - обходим все ветви пока не найдём "правильную" или не убедимся в её отсутствии.

Чтобы было проще - разберем алгоритм на небольшой матрице и искать будем только одно слово. Затем написанный код применим на большой матрице.

Попробуйте найти в этой матрице слово компьютер.
Я подкрасил возможные решения. Часть из них "тупиковые"

Матрицу так же занесём в MySQL

Для начала разобьём слово на символы и удалим повторные(если в слове повторяются символы, например телевизор).
Найдём все возможные координаты для каждой буквы. Если для хоть одной буквы нет ни одной пары координат - значит этого слова точно нет в матрице и искать мы его не будем.

Теперь из полученного набора координат возьмём набор координат первой буквы слова, то есть буквы К.
Это буквы с координатами (6;2), (2;5) и (6;8).

Обходить их будем по очереди.
На каждой следующей букве смотрим смежные клетки за исключением "той, с которой пришли".

Начиная с первой клетки не запоминаем предыдущую клетку, затем запоминаем.
Обходим смежные клетки, сначала верхнюю, потом правую, затем нижнюю и левую. Ту, с которой пришли - пропускаем.
Если мы зашли в тупиковую ветвь - уходим назад на одну букву и попробуем найти последнюю найденную букву, только уже "в другом направлении".

Графически это будет выглядеть так:

Будем держать в памяти "направление", по которому мы пошли, по каждой клетке и найденные координаты.

Если в процессе такого "поиска-отката-поиска" удалось дойти до последней буквы слова - значит слово найдено и задача решена.
Если не дошли - значит этого слова нет в матрице.

На словах алгоритм выглядит несложно, а если водить по матрице пальцем - так вообще детская задача. А вот переложить этот алгоритм на код оказалось не такой простой задачей, несколько вечеров я за ней провёл.

Код написан на PHP и помещён в один класс.

Так как слово может быть сколько угодно длинным - функция поиска следующей буквы будет вызываться рекурсивно.

Полностью код класса я приводить не буду, вы можете его скачать по ссылке ниже.

Запуск

Создайте таблицу из дампа
Большая матрица дамп
Маленькая матрица дапм

Скачать класс Airbnb

Репозиторий

В методе __construct класса Airbnb укажите реквизиты доступа к БД и (если вы поменяли имя таблицы с матрицей или у вас их несколько) имя таблицы с матрицей. Если хотите видеть процесс поиска - при создании экземпляра класса передайте ему true.

Запускать его следует следующим образом:

include('./Airbnb.php');

$airbnb = new Airbnb(true);
$airbnb->run('компьютер');
$airbnb->run('квадрокоптер');
$airbnb->run('кошка');
$airbnb->run('диалект');

Запуск на большой матрице:

$airbnb = new Airbnb();
$words = ['машина', 'голос', 'управление', 'блокчейн', 'данные', 'интернет', 'компьютер', 'лом', 'молдованин'];
foreach($words as $word) {
    $airbnb->run($word);
}

На этом всё. Можете проверить данный код на хостинге или на локальной машине.
Материал подготовлен автором @tristamoff