А кто нить делал сканворды?

← →
Polkin © (2010-10-26 12:27) [0]

Добрый день!

Никто случаем не разрабатывал построение сетки скандвордной. А то случайно буркнул тему диплома... А задача оказалась не такой легкой.

Вроде порылся по инету, почитал, алгоритма построения сетки как такового нету. Мож кто нить делал?

← →
Mystic © (2010-10-26 12:49) [1]

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

← →
Dennis I. Komarov © (2010-10-26 12:49) [2]

А в чем проблема то? И чего там на диплом такого?

← →
И. Павел © (2010-10-26 12:58) [3]

Программа должна обеспечивать интерфейс для разработки сканворда, или шаблон наполнять словами, или и то, и другое?
И еще не понятно, в чем возникла сложность. ИМХО, тут могут быть 2 основные проблемы:
1. Не знаете, как этот перебор сделать - тогда берите тему попроще.
2. Знаете, как сделать, но не устраивает производительность. Тут можно покопаться. Например: подставлять сперва слова, имеющие на перекрестках часто встречающиеся буквы ("о", "а" и т.д.). Или генерировать кросворд не по заданному шаблону, а как получиться по ходу перебора, лишь бы симметрично. Ну или просто делать кроссворды поменьше размером :)

← →
TUser © (2010-10-26 13:29) [4]

А на вход - что поступает? Словарь или словарь+сетка?

← →
vajo (2010-10-26 13:33) [5]

http://forum.vingrad.ru/topic-136778/kw-%EA%F0%EE%F1%F1%E2%EE%F0%E4.html

← →
Polkin © (2010-10-26 13:58) [6]

> И. Павел © (26.10.10 12:58) [3]

В проге есть словарь (неск десятков тыс. слов). Она должна генерировать сетку и туда пихать слова.

1. С темой поздняк
2. Производительность не важна.

> Mystic © (26.10.10 12:49) [1]

Можно поподробнее

> vajo (26.10.10 13:33) [5]

Тут немного другое - кроссворды, их то полегче буит... А скандинавские - жуть

← →
polkin (2010-10-26 22:10) [7]

ээхх...ну если и тут не помогут, значит нигде (((

> Мож кто нить делал?

Это ты замахнулся, конечно. Соболезную. Я только Эрудита писал.

> [6] Polkin © (26.10.10 13:58)

Вряд ли тема диплома отчетливо говорит, что речь идет об абсолютной автоматике. Можно сделать просто систему, упрощающую составления сканворда. Тоесть она будет обеспечивать пользователю интерфейс построения, сохранение, печать и т.д. Плюс можно будет выделить несколько клеток (часть из которых может быть уже заполнена) и попросить систему найти ряд слов, подходящих под эти клетки. Плюс еще ряд полезных функций. Все равно полностью автоматический генератор сканвордов на практике врят ли кому-нибудь будет нужен (разве что там будет миллион различных настроек).

> Можно поподробнее

А что подробнее? Cтроим битовые маски. Например, битовая маска всех слов, где первая буква "a", где вторая буква "a", ..., где N-я буква "a", где N-1-я буква а. Если максимальная длина слова 12, то всего получаем 24 * 32 = 768 разных битовых маск. Если слов 100 000, то получаем 768 * 100 000 / 8 ~= 10 M индекса.

Далее, например, у нас есть нечто такое

......= ......c ......у ......н =баунти ...=кот

Смотрим, куда мы можем прилеплять слова. У нас есть двубуквенные сочетания *нк и *то. Соответственно, делая AND для битовых масок, где последняя "к" и где последняя "к" мы получаем битовую маску слов, которые можно впендюрить по вертикали. То же самое и в случае окончания *то. Потом выбираем тот вариант, где меньше слов возможно, и перебираем его в случайном порядке). И так пока не дойдем до финиша.

А кто нить делал сканворды? Найти похожие ветки