Прием работ продлен до 20 мая
Опять новый линк на исправленный словарь: убраны слова ИҐA, ЙЄЛЛОУСТОН, КАТАЛЕПCИЧЕСКИЙ, О'ГЕНРИ, О'КЕЙСИ, С/Х, ФІЛАТОВ, ФІЛАТОВА.
Новый линк на исправленный словарь: слова отсортированы, записаны в верхнем регистре, убраны слова с "ё", "-", ".".
Итак, конкурсная задача будет несколько сложнее, но все-таки не архисложная. Недавно коллега выложил пост про игру словомания. Так как мы стали "более лучше программировать", попробуем написать более удачное решение.
На игровом поле представлена сетка NxN (5 <= N <= 100), состоящая из русских букв в верхнем регистре, требуется собирать слова последовательно соединяя буквы по горизонтали, вертикали и диагонали. Для каждого слова можно использовать одну букву один раз, то есть для сетки 5 на 5 максимальная возможная длина слова - 25 символов.
- решение должно представлять из себя один *.rb файл, написанный исключительно на Ruby, без использования многопоточности;
- решение будет проверяться на Ruby 1.9.2;
- при тестировании в одну папку с приложением будут помещены файлы input.txt и words.txt (слова отсортированы);
- оцениватся будут количество найденных слов (без повторений и присутствующих в словаре), длинной от 3 символов, чем длинее слово тем "ценнее" оно;
- решения (в виде приватных ссылок на gist с решением) принимаются до 20 мая на почту hronya@gmail.com.
Наиболее интересные и шустрые решения будут опубликованы, а самого-самого крутого рубиста мы пригласим к нам в подкаст.
input.txt
Первой строчкой идет число N - размер таблицы, далее следует N строк состоящих из N заглавных русских букв.
5
ВОРОН
ДЛОКЖ
ГНАШЩ
ФАЬБО
ЙЕИУВ
output.txt
В выходной файл нужно записать все слова, которые удалось найти (чем больше - тем лучше, чем скорее - тем лучше).
ВОРОН
ВОРОНКА
Будет подготовлено некоторое количество таблиц разной размерности. Работы запускаются по очереди; каждой из них будет выделено некое время на исполнение, затем, если они не завершаются раньше определенного времени, они прерываются kill-ом (мы ожидаем, что не все разработчики могут знать, что такое сигналы и как с ними работать, поэтому ниже приведен шаблон программы, на который следует ориентироваться). Работы, выдающие некорректные ответы (нет в словаре, дублирующиеся слова) будут дисквалифицированы.
В случае часто задаваемых вопросов данный gist будет обновляться. Следует принять во внимание, что авторы подкаста ни разу не проводили никаких конкурсов, поэтому большая просьба относиться к контесту лишь как к способу лишний раз потренировать мозги. Даже простая полнопереборная задача может победить: совершенно не факт, что кому-то будет не лень делать что-то более сложное.
output = File.open('output.txt', 'w')
at_exit do
output.flush
output.close
end
# your solution here
ФАНГ
ГДОВ
ГАНАШ
ДЛАНЬ
ДОРОЖКА
ДОРОШКО
ДОЛГАН
ВОРОНКА
ВОРОНКО
ВОРОНА
ВОРОНЬЕ
ВОЛОКНО
ВОЛАН
ВОЛНА
ВОЛГА
НОРКА
НОША
ЛОКОН
ЛОШАК
ЛАНОК
ЛАНЬ
ЛАНА
ЛАНДО
ОРОК
ОРЛАН
ОДНАКО
ОКНО
ОКАНЬЕ
ОКРОЛ
РОНА
РОНДО
РОЛАН
РОЛАНД
БЬЕФ
ШКОЛА
ШАНДОР
ШОРКАНЬЕ
КАБОШОН
КАЛОНГ
КАЛГАН
КОНДОР
КРОНА
ВОШКА
ВОШЬ
НОЖКА
Вот что находит алгоритм для тестового входа из описания. Как теперь отсортировать слова? Ведь нужно чтобы их было и больше и они были длиннее. Какая пропорция?