Несколько месяцев подряд я был очень занят организационными проблемами, теперь посвободнее и надеюсь писать в блог чаще. А занимался я организацией новой компании-разработчика социальных игр. Теперь эта компания работает, расскажу про нее позже. А пока хочу поделится своей озадаченностью. В моей новой компании открыты вакансии программистов-разработчиков. Кандидатам после собеседования я предлагаю тестовую задачу. На решение задачи я даю сутки, на демонстрацию решения в форме готовой программы еще день. Точнее так, для первых кандидатов я устанавливал такие ограничения, потом снял, потом вместо ограничений я стал давать подсказки… Слушайте какое дело – никто не может эту задачу решить. Между тем у нее есть очень простое, понятное, короткое и эффективное решение. Публикую задачу для всех желающих. Если вам удастся ее решить, и вам нужна работа в игровой компании, свяжитесь со мной, пожалуйста.
Это задача об автоматической генерации кроссворда (ничего неожиданного, не правда ли), но генерировать его необходимо некоторым специальным, описанным ниже способом.
Дано: словарь корректных английских слов.
Получить:
- Структуру данных, реализующую словарь, обеспечивающую достаточно быстрый поиск слова (размер рабочего словаря от 200 тысяч слов).
- Алгоритм построения корректного кроссворда: все слова связаны, нет отдельно стоящих слов или групп слов, не пересекающихся с другими словами. Причем, алгоритм должен работать пошагово следующим образом:
- на первом шаге должен быть построен кроссворд из 6 букв (одно слово из из 6 букв, или одно слово из 3 и одно из 4 букв, и т.д.)
- на каждом следующем шаге кроссворд должен увеличиваться на две буквы
Важно: на каждом шаге должен получаться корректный кроссворд. Понятно, что слова в составе кроссворда при этом будут меняться, иными словами кроссворд перестраивается с добавлением каждых двух букв.
Общее количество букв не имеет значение (очевидно, что оно должно быть четным). Однако, для теста производительности программа должна стоить кроссворды с использованием нескольких тысяч букв.
Дополнительно реализовать простую визуализацию процесса. Т.е. мы должны иметь возможность видеть каждый шаг работы алгоритма до получения финального кроссворда.
В свое время я решил эту задачу и соответствующий алгоритм работает в одной из наших игр, причем очень быстро, поэтому решение будет с чем сравнить. Если есть вопросы по постановке задачи, отвечу на них в комментариях.
#1 by Влад Голощапов on Сентябрь 3, 2010 - 0:16
Неплохо бы ещё добавить условие на плотность кроссворда, то есть желательно, чтобы внутри уже занятого кроссвордом пространства было мало (или не было совсем) мест куда можно что-нибудь добавить. Иначе явным победителем по скорости будет вырожденное решение, когда новые слова достраиваются к возможно более последнему из добавленных (по краям кроссворда меньше запрещённых ходов). Получится такая длинная развесистая конструкция, зато быстро.
#2 by Dex on Сентябрь 3, 2010 - 1:58
“- на каждом следующем шаге кроссворд должен увеличиваться на две буквы”
то есть ,на каждом шаге ,число задействованных клеточек кроссворда должно увеличиваться именно на две? При этом мы не только добавляем слова ,но и заменяем слова уже собранного кроссворда?
#3 by Choock on Сентябрь 3, 2010 - 14:05
Влад, условие о плотности – бонусное условие, для тех, кто хорошо справился с основной задачей
Dex, да, верно.
#4 by Разинков Илья on Сентябрь 18, 2010 - 21:24
Скинул на ящик еще один вариант решения задачки, интересны ваши комментарии
Не уверен насчет оптимальности, но на вид – все достаточно быстро работает
#5 by Всеволод on Сентябрь 22, 2010 - 5:13
“- на каждом следующем шаге кроссворд должен увеличиваться на две буквы”
Не совсем понятно, каким образом после второго шага в кроссворде появятся слова длиннее 3-х букв.?
Или же в процессе формирования кроссворд не является “классическим” кроссвордом – скажем, на картинке в шапке последним шагом будет добавление букв “R” и “Y” внизу. И получим вместо слова “SOA” два новых “SOAR” и “AY”?
#6 by Choock on Сентябрь 22, 2010 - 14:46
Всеволод, не уверен правильно ли я понимаю что Вы подразумеваете под “классическим”. Вот цитата из постановки задачи:
“Важно: на каждом шаге должен получаться корректный кроссворд. Понятно, что слова в составе кроссворда при этом будут меняться, иными словами кроссворд перестраивается с добавлением каждых двух букв.”
Т.е. да, кроссворд можно и нужно перестраивать, не обязательно на следующем шаге сохранять слова, полученные на предыдущем. Важно только чтобы после каждого шага, кроссворд оказывался корректным. Ну и, конечно, чтобы в нем присуствовали только те буквы, которые были получены на всех предыдущих шагах и никакие другие.
Кстати, для информации решающих. На сегодняшний день я получил несколько решений, два из них очень хорошие.
Отличный новый (во всяком случае для меня) алгоритм построения кроссворда с заданными свойствами нашел Михаил, PHP-программист, который, к моему сожалению, не пишет и не собирается писать на AS3. Миша, Вы не хотите опубликовать здесь ссылку на свой результат, кстати?
Второе отличное решения нашел Влад, которого я после этого сразу взял на работу
Его решение особенно ценно своей цельностью и системностью. Алгоритм собственно построения кроссворда, который он предложил, чуть менее элегантен чем алгоритм Михаила, но не менее производителен.
Ну и есть несколько решений на “троечку”. Кстати, удивительно, что затруднение вызывает словарь.. Ребят, ну первый класс, вторая четверть, а? Ок, первый курс, второй семестр. Вспоминаем: хе-ши-ро…
#7 by arkadattx on Октябрь 18, 2010 - 12:57
А можно глянуть на работающий пример? Декомпилл не интересует, просто интересно на работу готового приложения глянуть, если не против. Если вакансии все еще актуальны и пр. (сам не претеную – не из Москвы), то можно было бы (опять же если не сложно) сделать небольшое видео. Спасибо.
#8 by Choock on Октябрь 19, 2010 - 12:39
Да, конечно можно посмотреть на то, как это работает. Сделал два скринкаста. Первый – пошаговая работа алгоритма. Я жму клавишу сначала пореже, потом пощаще, потом просто удерживаю ее нажатой.
Второй – тот же алгоритм строит кроссворд из 10К слов для теста производительности.
Это решение Влада Голощапова, о котором я упоминал выше.
1. Пошаговая работа: http://screencast.com/t/8i2eYq3sw
2. Тест производительности: http://screencast.com/t/ySXlrCeZ4k
#9 by alexli on Декабрь 13, 2010 - 14:51
Выложил свою версию кроссворда на labs.alexli.ru/crossword
Алгоритм, конечно, можно еще усовершенствовать
#10 by Никита on Май 11, 2011 - 13:47
Я тоже отправил вам своё решение. Очень интересная на самом деле задачка.