Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Update 3

Прием работ продлен до 20 мая

Update 2

Опять новый линк на исправленный словарь: убраны слова ИҐA, ЙЄЛЛОУСТОН, КАТАЛЕПCИЧЕСКИЙ, О'ГЕНРИ, О'КЕЙСИ, С/Х, ФІЛАТОВ, ФІЛАТОВА.

Update

Новый линк на исправленный словарь: слова отсортированы, записаны в верхнем регистре, убраны слова с "ё", "-", ".".

Конкурс RubyNoName подкаста

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

Постановка задачи

На игровом поле представлена сетка 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
@mikdiet

This comment has been minimized.

Copy link

@mikdiet mikdiet commented Apr 27, 2012

словарь плохо сортирован и слова в нем повторяются - специально?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented Apr 28, 2012

Не специально, проверю и исправлю сегодня

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented Apr 28, 2012

Добавил новый файл

@pumbur

This comment has been minimized.

Copy link

@pumbur pumbur commented Apr 28, 2012

какое примерно будет время работы?
можно ли использовать сторонние гемы? модули из стандартной библиотеки?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented Apr 28, 2012

Думаю, от 10 секунд до пары минут.

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented Apr 28, 2012

Стандартную библиотеку однозначно да. Про гемы вопрос хитрый: они должны удовлетворять условиям конкурсной программы (без тредов и C расширений), ну и не должны за вас решать поставленную задачу: решение find_words(table, dictionary), где find_words это метод из гема будет отмечено как "халявное". А так библиотеки с графами, деревьями, алгоритмами используйте свободно.

@pumbur

This comment has been minimized.

Copy link

@pumbur pumbur commented Apr 28, 2012

от трёх символов включительно?
разрешены ли самопересечения (например, слово "ШОРКАНЬЕ" к примеру в задании)?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented Apr 28, 2012

Включительно, разрешены.

@zsand

This comment has been minimized.

Copy link

@zsand zsand commented Apr 29, 2012

В словаре встречаются левые символы, вот полный отсортированный список символов из него:

["'", "/", "A", "C", "Є", "І", "А", "Б", "В", "Г", "Д", "Е", "Ж", "З", "И", "Й", "К", "Л", "М", "Н", "О", "П", "Р", "С", "Т", "У", "Ф", "Х", "Ц", "Ч", "Ш", "Щ", "Ъ", "Ы", "Ь", "Э", "Ю", "Я", "Ґ"]

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented Apr 29, 2012

@cheetah

This comment has been minimized.

Copy link

@cheetah cheetah commented May 4, 2012

Будут ли считаться дублирующими одинаковые слова c отличными координатами как минимум одной из букв? «Волна» из примера, можно взять «а» на (2, 2), а можно на (1, 3)

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented May 5, 2012

@makaroni4

This comment has been minimized.

Copy link

@makaroni4 makaroni4 commented May 7, 2012

ФАНГ
ГДОВ
ГАНАШ
ДЛАНЬ
ДОРОЖКА
ДОРОШКО
ДОЛГАН
ВОРОНКА
ВОРОНКО
ВОРОНА
ВОРОНЬЕ
ВОЛОКНО
ВОЛАН
ВОЛНА
ВОЛГА
НОРКА
НОША
ЛОКОН
ЛОШАК
ЛАНОК
ЛАНЬ
ЛАНА
ЛАНДО
ОРОК
ОРЛАН
ОДНАКО
ОКНО
ОКАНЬЕ
ОКРОЛ
РОНА
РОНДО
РОЛАН
РОЛАНД
БЬЕФ
ШКОЛА
ШАНДОР
ШОРКАНЬЕ
КАБОШОН
КАЛОНГ
КАЛГАН
КОНДОР
КРОНА
ВОШКА
ВОШЬ
НОЖКА

Вот что находит алгоритм для тестового входа из описания. Как теперь отсортировать слова? Ведь нужно чтобы их было и больше и они были длиннее. Какая пропорция?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented May 7, 2012

Сортировать не надо. Про пропорцию не понял

@makaroni4

This comment has been minimized.

Copy link

@makaroni4 makaroni4 commented May 7, 2012

Т.к. использовать букву можно один раз, то через одну букву может проходить несколько слов. Нужно выбрать, какое из них записать в output.txt Выбор зависит от того, что лучше - слова, которые длиннее или больше слов, но которые короче.

Это я и имел в виду под сортировкой. Слово не самое удачное)

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented May 8, 2012

Одну и ту же букву для разных слов использовать можно

@makaroni4

This comment has been minimized.

Copy link

@makaroni4 makaroni4 commented May 8, 2012

ОК, спасибо.

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 14, 2012

А пример в шаблоне только в IOS используется, как я понял?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented May 14, 2012

IOS?

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 14, 2012

я не совсем понял, как использовать шаблон, новичек...

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 14, 2012

там читал, но все равно не понял.
например я так пишу в фаил: output = File.open('output.txt', 'w'){|file| file.puts a.output}
как тогда должно быть?

@makaroni4

This comment has been minimized.

Copy link

@makaroni4 makaroni4 commented May 14, 2012

Используй оператор IO#write:

http://www.ruby-doc.org/core-1.9.3/IO.html#method-i-write

Вот пример:

output = File.open('output.txt', 'w')

at_exit do
  output.flush
  output.close
end

0.upto 1000 do |i|
  output.write "#{i}\n"
  sleep 0.1
end

Запусти скрипт и кильни процесс, выполнится блок метода at_exit и в файле output.txt будет несколько десятков чисел, для которых был вызван метод write.

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 15, 2012

makaroni4: у тебя сколько времени на тестовом файле проходит?

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 15, 2012

я запись вставил в блок at_exit, вроде работает.

@makaroni4

This comment has been minimized.

Copy link

@makaroni4 makaroni4 commented May 15, 2012

Можно даже делать

at_exit do
  output.close
end

т.к. close делает flush.

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 17, 2012

Добрый день, есть какие нибудь промежуточные результаты?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented May 17, 2012

Добрый, мы прием работ продлили до 20го. Результатов пока нет.

@dimanon

This comment has been minimized.

Copy link

@dimanon dimanon commented May 17, 2012

А я поторопился, можно было по оптимизировать еще... Много конкурсантов?

@kronos

This comment has been minimized.

Copy link
Owner Author

@kronos kronos commented May 17, 2012

Меняй свой gist сколько хочешь до 20-го включительно, я последнюю версию возьму.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment