Skip to content

Instantly share code, notes, and snippets.

@kronos
Created April 27, 2012 11:08
  • Star 6 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save kronos/6569ecd7db151afd2cc2 to your computer and use it in GitHub Desktop.

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
Copy link

mikdiet commented Apr 27, 2012

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

@kronos
Copy link
Author

kronos commented Apr 28, 2012

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

@kronos
Copy link
Author

kronos commented Apr 28, 2012

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

@pumbur
Copy link

pumbur commented Apr 28, 2012

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

@kronos
Copy link
Author

kronos commented Apr 28, 2012

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

@kronos
Copy link
Author

kronos commented Apr 28, 2012

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

@pumbur
Copy link

pumbur commented Apr 28, 2012

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

@kronos
Copy link
Author

kronos commented Apr 28, 2012

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

@zsand
Copy link

zsand commented Apr 29, 2012

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

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

@kronos
Copy link
Author

kronos commented Apr 29, 2012 via email

@cheetah
Copy link

cheetah commented May 4, 2012

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

@kronos
Copy link
Author

kronos commented May 5, 2012 via email

@makaroni4
Copy link

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

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

@kronos
Copy link
Author

kronos commented May 7, 2012

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

@makaroni4
Copy link

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

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

@kronos
Copy link
Author

kronos commented May 8, 2012

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

@makaroni4
Copy link

ОК, спасибо.

@dimanon
Copy link

dimanon commented May 14, 2012

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

@kronos
Copy link
Author

kronos commented May 14, 2012

IOS?

@dimanon
Copy link

dimanon commented May 14, 2012

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

@dimanon
Copy link

dimanon commented May 14, 2012

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

@makaroni4
Copy link

Используй оператор 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
Copy link

dimanon commented May 15, 2012

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

@dimanon
Copy link

dimanon commented May 15, 2012

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

@makaroni4
Copy link

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

at_exit do
  output.close
end

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

@dimanon
Copy link

dimanon commented May 17, 2012

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

@kronos
Copy link
Author

kronos commented May 17, 2012

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

@dimanon
Copy link

dimanon commented May 17, 2012

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

@kronos
Copy link
Author

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