Нужно составить алгоритм

[EvroStandart]

Есть кроссворд. Любой. На пример как на картинке.

И есть набор чисел, которых в несколько раз больше, чем поместится в кроссворд. На пример:
92365
13846
4356
128
95
1250
3916735
3594
190346
5843
9571
126534
59
21
39468
593823
96986
9348
594756
33466

Нужно составить алгоритм, который заполняет кроссворд числами из списка. Условие: чтобы сумма цифр из всех квадратов в кроссворде получилась максимальная.
Конкретно я немогу понять через что представлять сам кроссворд (массив? дерево?). И как проверять какие места свободны, какие частично заняты.

И ещё:

Квадрат разбит на девять частей. В каждой части вписана буква:

T __ S __ E

K __ I __ H

U __ R __ A

Нужен алгоритм, выписывающий все возможные комбинации (слова) из этих букв. Условие: минимум четыре буквы, в каждой комбинации должна быть буква I (середина квадрата), каждая буква может присутствовать только один раз.

[kot_]

Под конец рабочего дня уже соображать трудно - но рискну предложить решение по первой части задачи - так как ни каких дополнительных условий не указанно то максимальная сумма кросворда - это сумма всех чисел - минус сумма чисел не вошедших в кроссворд. Хотя в моем понимании - кроссворд - это всеже слова.
И не очень понятно, что имеется ввиду под представлением. Если имеется ввиду хранение результатов - то каждая ячейка описывается положением по горизонтали и по вертикали - то есть, как вариант, для ее хранения можно создать структуру, членами которой является позиция по Х У и собственно значение ячейки. А хранить ее можно или в двумерном массиве - самое простое, но не самое эффективное, или использовать два контейнера с уникальным значением ключа. В качестве ключа использовать соответственно в одном случае Х в другом У.
Я бы сделал это так -

typedef multiset<Struct>Cell;
typedef map<int,multiset<Struct>::iterator>X;
typedef map<int,multiset<Struct>::iterator>Y;

меп ищет по ключу достаточно быстро - решение проблемы, заполнена ли ячейка - поиск по Х или У и т.д. Вобще-то структуру создавать не обязательно - просто так уневерсальней, то есть универсальней я хотел сказать. Все начал заговариваться - пора рулить до хаты.

[EvroStandart]

kot_:
максимальная сумма кросворда - это сумма всех чисел - минус сумма чисел не вошедших в кроссворд.

Ты неправильно понял. Я написал Нужно составить алгоритм, который заполняет кроссворд числами из списка. Условие: чтобы сумма цифр из всех квадратов в кроссворде получилась максимальная.

То есть вписали число 3465, считаем: 3+4+6+5. В кроссворд надо добавлять как слова: если число из трёх цифр, то оно займёт три квадрата. Потом считать сумму всех квадратов. Получившийся алгоритм для заполнения должен работать со словами тоже (может быть при минимальном изменении).
Меня больше всего интересует как сделать перересечение линий в кроссворде. Если в одной линии я вписал 2 7 9 4 2 5, предположим цифра 4 попала на пересечение. Тогда нужно както вычислить, что по другой линии одна цифра уже есть. Соответственно туда надо искать число соответствующее условию.

[kot_]

Сообщение от EvroStandart

Ты неправильно понял. Я написал Нужно составить алгоритм, который заполняет кроссворд числами из списка. Условие: чтобы сумма цифр из всех квадратов в кроссворде получилась максимальная.

То есть вписали число 3465, считаем: 3+4+6+5. В кроссворд надо добавлять как слова: если число из трёх цифр, то оно займёт три квадрата. Потом считать сумму всех квадратов. Получившийся алгоритм для заполнения должен работать со словами тоже (может быть при минимальном изменении).
Меня больше всего интересует как сделать перересечение линий в кроссворде. Если в одной линии я вписал 2 7 9 4 2 5, предположим цифра 4 попала на пересечение. Тогда нужно както вычислить, что по другой линии одна цифра уже есть. Соответственно туда надо искать число соответствующее условию.

Опять же я бы использовал для этих целей преобразование числа в строку - длина строки=количество клеток. Тогда ты легко можешь работать как со строками так и с цифрами. Единственное - возникнут накладные расходы на преобразование цифры в строку и обратно - но не настолько уж большие. Используя предложеную связку контейнеров ты можешь легко определить наличие или отсутствие букв в строке пересечения - все что для этого тебе необходимо - написать шаблон функции поиска которая возвращает количество элементов имеющих У (или Х смотря какое пересечение) одинаковый с искомой позицией (блин как завернул) и валюе которых не пусто или в противном случае ноль. Но при этом важно не забыть проверять на наличие разрывов между ячейками. Кстати, я немного не сообразил вчера, для связки нужно использовать не 3 а 2 контейнера - в одной хранится уникальный идентификатор ячейки и итератор на элемент второго контейнера. А во втором хранится структура, полями которой являются - ид, Х,У, признак первой или последней ячейки и значение. Так же здесь может хранится идентификатор следующей и предыдущей ячейки по вертикали, горизонтали и верхней нижней. Можно использовать и просто массив - но у контейнера есть преимущество - стандартная библиотека функций. Можно использовать и один контейнер - но это решение мне нравится меньше.
То есть в первом приближении алгоритм выглядит так:
1. Шаг первый - инициализируешь сетку кроссворда - т.е. заполняешь массивы структурами с установленным значением Х и У и присваеваешь им уникальный идентификатор.
2. Получаешь длину строки которую необходимо заполнить.
3. Находишь число совпадающее с длиной строки.
4. Раскладываешь его на составляющие и получаешь сумму.
5. Проверяешь на соответствие условиям.
6. Помещаешь в ячейки.
7.Повторяешь со 2 до тех пор пока не дойдешь до последней ячейки.

[Drakosha]

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

Kot (Sorrryyyy!) предложил по крайней мере O(n*n)

[kot_]

Male - это кто? У меня вроде ник есть...
Конечно, приведеныый алгоритм может быть оптимизирован, но по сути он все же сводится к О(n*n).
Возможно повышение эффективности и свдение задачи к алгоритму поиска в бинарном дереве (блин хочется и котелок уже не варит) но в таком случае необходима оптимизация словаря, введение частот и возможно создание объектов типа строк - как совокупность ячеек. Это позволит получить гораздо более быстрый алгоритм и избежать перелопачивания массивов. Но эту мысль я еще не додумал по причине вышеуказанной.

[Drakosha]

проблема в том что кроме перебора (оптимизированного по частотам и т.д.), т.е. greedy никаких идей нету. К тому же ето не обеспечивает ОПТИМАЛьНОГО заполнения. Можно подумать о каких нибудь генетических алгоритмах... но как найти оптималный ответ???

[kot_]

Сообщение от Drakosha

проблема в том что кроме перебора (оптимизированного по частотам и т.д.), т.е. greedy никаких идей нету. К тому же ето не обеспечивает ОПТИМАЛьНОГО заполнения. Можно подумать о каких нибудь генетических алгоритмах... но как найти оптималный ответ???

Оптимизированный по частотам - это уже не перебор. Если провести оптимизацию словарей хотя бы по двум критериям - размер слова и, в случае цифрового кросворда, сумма - это уже бинарное дерево. То есть скорость выборки словаря может быть оптимизирована и сведена к поиску в бинарном дереве, что эффективней перебора. Соответственно сетка кросворда так же может быть оптимизирована, только критерий оптимизации должен совпадать с критериями словаря.

[EvroStandart]

То, что числа надо в строки переделать - это понятно. Идея с контейнерами интересная. А как со второй задачей? Предложения будут?

[kot_]

Сообщение от EvroStandart

То, что числа надо в строки переделать - это понятно. Идея с контейнерами интересная. А как со второй задачей? Предложения будут?

Если нет ограничений на позицию I в слове - то задачу я бы предложил алгоритм - разделить гласные и согласные, выделить букву I отдельно - выделить сочетания в которых буквы из первого массива находятся в первой, второй позиции и четвертой, I в третьей. В получившихся сочетаниях последовательно заменить первую позицию буквами из второго массива, потом вторую.
Поместить в массив - заканчивается на согласную.
Выделить сочетания в которых буквы из первого массива находятся в первой, третьей позиции и четвертой, I во второй.
В получившихся сочетаниях последовательно заменить третью позицию буквами из второго массива, потом четвертую.
Поместить - заканчиваются на гласную.
Полученные сочетания из заканчивается на первом этапе добавить пятой из массива гласных сравнив с первой и второй позицией.
И так до конца.
То есть предполагается что сочетаний типа TSHKIUAE быть не должно.

[EvroStandart]

А надо все сочетания. и такие:

kot_:
TSHKIUAE

тоже...

[Drakosha]

Так вторая задача ето действительно просто перебор: все слова по 4 буквы, по 5 букв, и до 9 букв. Кстати по моим посчетам ето 876624 слов

А на первую оптимального решения не видно...

[kot_]

EvroStandart:
А надо все сочетания. и такие:
Цитата:
kot_:
TSHKIUAE
тоже...

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

[EvroStandart]

Только я чтото недогоняю как алгоритм для такого перебора составить?
Набросайте, если не влом...

[kot_]

Сообщение от EvroStandart

Только я чтото недогоняю как алгоритм для такого перебора составить?
Набросайте, если не влом...

В алгоритме ничего сложного нет. У тебя есть символ который обязательно должен присутствовать - значит начинаешь с того, что устанавливаешь его в первую позицию - после начинаешь перебор. В массиве каждая буква у тебя встречается один раз - это нужно использовать - то есть каждую позицию массива помещаешь один раз в в свободную позицию слова - для 4-х буквенного слова это будет примерно так:
- скопировать первые три элемента в слово
-записать
- скопировать следующие три элемента
-пункт 2
-скопировать первый второй и четвертый
-пункт два
-скопировать первый второй и пятый
-пункт два
-скопировать первый второй и шестой
...
-скопировать первый третий и четвертый
и так далее.
Потом первый элемент массива копируется во вторую позицию второй в первую. Выполняешь последовательно теже шаги.
Затем третий элемент копируется в первую. Опять прогоняешь
Когда все элементы массива пройдут первую позицию смещаешь второй на место третьего и опять итерация. То есть выполняешь все шаги до тех пор, пока первый элемент массива не вернется в начало.
То же самое используешь для 5 и более буквенных. Но здесь возможны два варианта - с одной строны у тебя уже есть 4-х буквенные слова - можно использовать их - но тогда на этом этапе должна быть добавлена функция проверки на наличие буквы - мне кажется это может усложнить работу с алгоритмом. И по этому, я бы использовал тот же принцип что и для 4-х буквенных но соответственно копировал просто большее колво элементов.

[kot_]

Могу добавить, что имеет смысл не забывать о нумерации с нуля. Это упростит работу с постоянным символом - его позиция в массиве - это количество символов перед ним. Что позволяет избежать кучи if() else - я имею ввиду, что нет нужды проверять в какой позиции находится постоянная буква - нужно просто использовать позицию ее цикла итерации - например если в текущей итерации буква I находится в первой позиции - ее номер 0 - если в во второй и больше - позиция каждой вычисляется следующим образом - для букв перед - (индекс буквы+1)-(индекс постоянной буквы в массиве - количество букв перед) -1. Для букв после (индекс буквы+1)-(индекс постоянной буквы в массиве - количество букв перед).
Фу еле написал. Но на самом деле это позволяет неплохо оптимизировать алгоритм и ускорить его работу.

[EvroStandart]

Спасибо!

[/7y3uK]

Маленькое предположение - а не получится разложить или развернуть квадрат в дерево с корнем в I, а потом просто различные обходы делать??? ИМХО если получится, то тогда можно опять же стандартными контейнерами решить, что в разы быстрее тривиального перебора...
Не утверждаю что так получится, но вдруг

[kot_]

/7y3uK:
Маленькое предположение - а не получится разложить или развернуть квадрат в дерево с корнем в I, а потом просто различные обходы делать??? ИМХО если получится, то тогда можно опять же стандартными контейнерами решить, что в разы быстрее тривиального перебора...
Не утверждаю что так получится, но вдруг

Брутфорсе он и есть брутфорсе То что ты предлагаешь - это называется атака по словарю. То есть, предполагается, что у нас уже есть массивы всех возможных сочетаний и мы просто подставляем их в нужное место. А задача вроде как обратная - есть набор символов - и необходимо создать словарь. Или может я просто неверно понял твою идею?

[Drakosha]

быстрее тривиального перебора не может быть быстрее по определению - все равно все решения надо найти