VPF::Кроссворд - Форум программистов

mr.Anderson

Дата 8.4.2009, 19:36 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: нет
Всего: 128

Очень прошу модераторов пока тему никуда не переносить...

Суть программы: она должна по заданному списку слов составлять максимально связную кроссвордную сетку. Нумеровать строки и столбцы не надо, просто составить сетку. Это уровень лабораторной считается, поэтому метод решения предложен как полный перебор, хотя что конкретно пересчитывать - непонятно, препод ничего внятного не сказал. Завтра мне эту вещь сдавать, я месяц проломал над задачей голову, но ничего толком сделать не смог.

Алгоритм у меня такой:

Код


//Собственно алгоритм работы.
//
//Получаем наши слова. Затем заполним вспомогательный массив русскими буквами,
//каждой букве будет соответствовать некоторое количество слов, в которых она
//есть, номера этих слов, количество совпадений по каждому слову и сами позиции,
//в которых есть совпадение.
//
//Далее. Пробегаемся по всем словам в поисках слова, где больше всего пересечений.
//Это делает функция findMaxCrossedWord(). Его ставим как основное по горизонтали.
//Затем ищем одну из двух удобных позиций (с разным шагом), в какой из них больше
//несмежных пересечений, ту берем за основу, пристраиваем к ней по вертикали все
//наши слова.
//
//Что значит пристраиваем? То есть берем слово, по вертикали его рисуем
//в нужном месте, потом пробегаемся по всем буквам и в том месте, где это слово
//имело пересечения, убираем его оттуда (просто зануляем строку), попутно уменьшая
//количество совпадений. В позицию ПИШЕМ -1, чтобы потом ее не трогать при пересчете.
//Также при этом проходе убираем и основное слово, к которому идет пристыковка. После
//всех этих манипуляций снова ищем максимальные пересечения со словами, но уже
//с учетом удаленных элементов.

Вот что у меня написано на текущий момент:

Код


#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <alloc.h>
#include <mem.h>
//#include <graph.h>

//Собственно алгоритм работы.
//
//Получаем наши слова. Затем заполним вспомогательный массив русскими буквами,
//каждой букве будет соответствовать некоторое количество слов, в которых она
//есть, номера этих слов, количество совпадений по каждому слову и сами позиции,
//в которых есть совпадение.
//
//Далее. Пробегаемся по всем словам в поисках слова, где больше всего пересечений.
//Это делает функция findMaxCrossedWord(). Его ставим как основное по горизонтали.
//Затем ищем одну из двух удобных позиций (с разным шагом), в какой из них больше
//несмежных пересечений, ту берем за основу, пристраиваем к ней по вертикали все
//наши слова.
//
//Что значит пристраиваем? То есть берем слово, по вертикали его рисуем
//в нужном месте, потом пробегаемся по всем буквам и в том месте, где это слово
//имело пересечения, убираем его оттуда (просто зануляем строку), попутно уменьшая
//количество совпадений. В позицию ПИШЕМ -1, чтобы потом ее не трогать при пересчете.
//Также при этом проходе убираем и основное слово, к которому идет пристыковка. После
//всех этих манипуляций снова ищем максимальные пересечения со словами, но уже
//с учетом удаленных элементов.

typedef struct {
    char Letter;
    int wCount;
    int pCount;
    int *words;
    int *positions;
} TLetter;

typedef struct {
    char *word;
    int *allow;
    int index;
} TWord;

const LMAX = 33;

//-----------------------------------------------------------------------------
//ищет букву в массиве букв
TLetter findLetter(TLetter *Letters, char letter);
//считает пересечения по слову
int countCrossesOfWord(TLetter *Letters, int index, TWord *words);
//ищет максимально пересеченное слово, вернет его индекс
int findMaxCrossedWord(TLetter *Letters, TWord *words, int n);
//void delWord(char *mainWord, char *word, int pos,

//GRAPHIC MODE
const sq_x = 4;
const sq_y = 4;
void drawSquare(int x, int y);
void drawWordGrid(char *word, int horizontal);
//-----------------------------------------------------------------------------

TLetter findLetter(TLetter *Letters, char letter)
{
    int i;
    for (i=0; i<LMAX; i++)
      if (Letters[i].Letter == letter)
        return Letters[i];

    return Letters[0];
}

int findMaxCrossedWord(TLetter *Letters, TWord *words, int n)
{
    int i;
    int memCount;
    int count;
    int memIndex;

    for (i=0, memCount=0, memIndex=-1; i<n; i++)
    {
        count = countCrossesOfWord(Letters, i, words);
        if (count > memCount)
        {
            memCount = count;
            memIndex = i;
        }
    }

    return memIndex;
}

int countCrossesOfWord(TLetter *Letters, int index, TWord *words)
{
    //надо посчитать количество пересечений других слов с данным.
    //как сделать? Проходим по слову, берем каждую его букву, ищем
    //ее в нашем массиве буковок через findLetter(). Поиск производим
    //с некоторым шагом, изначально равным 0, если нашли совпадение с буквой
    // - ставим шаг в 1, и сбросим его на следующем шаге. Это обеспечит
    //отбрасывание случаев, когда совпадение букв может быть одно за другим
    //(смежные совпадения не приветствуются).
    int i, j;
    int step;
    int memory;
    TLetter Letter;
    int result = 0;

    for (i=0, step=0; i<strlen(words[index].word); i++) //идем по слову
    {
        if (step)
        {
            step--;
            continue;
        }

        //пройдемся по всем словам в этой букве в поисках нашего
        Letter = findLetter(Letters, words[index].word[i]);
        for (j=0; j<Letter.wCount; j++)
        {
            if (stricmp(words[Letter.words[j]].word, words[index].word) == 0)
            {
                result++; //нашли наше слово - увеличим количество совпадений
                step++;
            }
        }
    }
    memory = result;
    //повторим то же самое второй раз, но с другим начальным шагом
    result = 0;
    for (i=0, step=1; i<strlen(words[index].word); i++) //идем по слову
    {
        if ((i > 0) && (step))
        {
            step--;
            continue;
        }

        //пройдемся по всем словам в этой букве в поисках нашего
        Letter = findLetter(Letters, words[index].word[i]);
        for (j=0; j<Letter.wCount; j++)
        {
            if (stricmp(words[Letter.words[j]].word, words[index].word) == 0)
            {
                result++; //нашли наше слово - увеличим количество совпадений
                step++;
            }
        }
    }

    if (result > memory)
    {
        return result;
    }
    else
    {
        return memory;
    }
}

void drawSquare(int x, int y)
{

}

void main()
{
    int wCount; //количество слов
    int i, j; //счетчики
    TWord *Words; //главный массив со словами
    TLetter Letters[33]; //массив с русскими буквами (160-175, 224-239)
    int rCode; //код русской буквы (нужен при заполнении Letters)
    int wMaxLen; //макс. длина слова
    int maxCrossedIdx; //индекс максимально пересеченного слова

    printf("Enter count of words: ");
    scanf("%d", &wCount);
    Words = (TWord *)malloc(sizeof(TWord)*wCount);
    for (i=0; i<wCount; i++)
    {
      Words[i].index = i;
      Words[i].word = (char *)malloc(sizeof(char)*51); //max 50 symbols
    }

    //заполняем массив букв
    rCode = 160;
    for (i=0; i<LMAX; i++)
    {
        Letters[i].Letter = rCode;
        if (rCode == 175)
            rCode = 223;

        Letters[i].wCount = 0;
        Letters[i].pCount = 0;
        Letters[i].words = (int *)malloc(sizeof(int) * wCount);
        rCode++;
    }

    //получаем слова
    wMaxLen = 0; //попутно считаем максимальную длину слова
    for (i=0; i<wCount; i++)
    {
        printf("Word %d: ", i+1);
        scanf("%s", Words[i].word);
        //пока что все позиции в слове доступны для анализа, покажем это
        Words[i].allow = (int *)malloc(sizeof(int) * strlen(Words[i].word));
        for (j=0; j<strlen(Words[i].word); j++)
          Words[i].allow[j] = 1;

        //и еще пропишем такого же размера массив в буквах
        Letters[i].positions = (int *)malloc(sizeof(int)*strlen(Words[i].word));
    }

    /* sample of memory dump
       -----------------------
       words:
           [0]: "безымянный"
           [1]: "игра"
                             2 words|1w: 10 letters|2w: 4 letters
       letters:               vvvvv    vvvvvvvvvv    vvvv
           [0]: 'а', 0, 0, { (0, 0), ("0000000000", "0000") }
           [1]: 'б', 0, 0, { (0, 0), ("0000000000", "0000") }
    */

//    maxCrossedIdx = findMaxCrossedWord(letters, words, wCount);
}

Я очень прошу помочь с реализацией этого алгоритма, я путаюсь, что где хранить, что искать... Пожалуйста, помогите, эта лабораторная очень много решает.

Это сообщение отредактировал(а) mr.Anderson - 8.4.2009, 19:38

--------------------

zim22

Дата 8.4.2009, 20:16 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

http://www.puzzle-maker.com/CW/

введи туда это:

Код


dinosaur / d
google / s
invader / dd
crisscross / dds
session / sss
help / aaa
vingrad / aa
abirvalg / a

title: hihihi
"Create Puzzle" потом нажми
потом клацни на слове "solution" в предложении Click solution to see and print a draft of the solution.

круто, да? smile

Добавлено @ 20:21
здесь есть исходники на си.
http://pdos.csail.mit.edu/cgi-bin/theme-cword

и здесь open source кроссворд-генераторы

Это сообщение отредактировал(а) zim22 - 8.4.2009, 20:27

--------------------

C++ FAQ Lite

mr.Anderson

Дата 8.4.2009, 20:32 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: нет
Всего: 128

Круто-то оно круто, и даже работает... Да вот только не разберусь я за 6 часов в таком коде... Блин...

Это сообщение отредактировал(а) mr.Anderson - 8.4.2009, 20:32

--------------------

zim22

Дата 8.4.2009, 20:35 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

Цитата(mr.Anderson @ 8.4.2009, 20:32

)

Да вот только не разберусь я за 6 часов в таком коде

кода нет. оно на стороне сервера работает.
исходники на си - то к другому кроссворду smile

***
mr.Anderson, не хочешь смухлевать? взять готовую прогу и скормить её свой список слов. Т.е. твоя программа будет оболочкой для другой smile

***
здесь используя генетические алгоритмы кроссворд строили
***
йес! я нашёл исходники! правда на delphi. но можно на С++ переписать, не проблема. с тебя пицот миллионов долларов!
http://www.delphiforfun.org/Programs/CrosswordGen0.htm
(там ссылка будет Download source)

Это сообщение отредактировал(а) zim22 - 8.4.2009, 20:52

--------------------

C++ FAQ Lite

mr.Anderson

Дата 8.4.2009, 21:38 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: нет
Всего: 128

Мухлеж не прокатит, объяснять-то принцип работы все равно мне придется.
За исходники спасибо, пригодятся, хотя как лаба не пойдет, там не консоль, + тоже тонны кода, разбирать нет времени.
За линк тоже спасибо. Короче + в репу. )))

Попробую решить сам. Что будет, то будет.

--------------------

Anikmar

Дата 8.4.2009, 22:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(mr.Anderson @ 8.4.2009, 19:36

)

составлять максимально связную кроссвордную сетку

А кто эту макимальность будет оценивать? Препод? Какими методами?

Мне кажется нужно посчитать кол-во повторений букв во всех словах, затем, начиная с максимального пересекать слова. ЧТо-нибудь получится, наверное...

mr.Anderson

Дата 9.4.2009, 04:44 (ссылка)

(нет голосов)

Загрузка ...

iOS Lead Developer

Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: нет
Всего: 128

Anikmar, я так пробовал, запутался))) Ща после семичасового кодинга и нуля часов спанья я уже вообще ничего не соображаю почти... Алгоритм-то есть... Нормальный... А вот сделать его - проблемка... Буду как-то выкручиваься завтра... Эм, сегодня то есть уже.

--------------------

Anikmar

Дата 9.4.2009, 07:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(mr.Anderson @ 9.4.2009, 04:44

)

Anikmar, я так пробовал, запутался))) Ща после семичасового кодинга и нуля часов спанья я уже вообще ничего не соображаю почти... Алгоритм-то есть... Нормальный... А вот сделать его - проблемка... Буду как-то выкручиваься завтра... Эм, сегодня то есть уже.

Вот так всегда - месяц думаем, надеемся, что родим шедевр. А в результате за одну ночь рожаем уродца - только бы сдать.

zim22

Дата 9.4.2009, 07:46 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

Цитата(Anikmar @ 9.4.2009, 07:41

)

поэтому надо учиться программировать в стиле eXtreme Programming.

--------------------

C++ FAQ Lite

Anikmar

Дата 9.4.2009, 07:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(zim22 @ 9.4.2009, 07:46

)

поэтому надо учиться программировать в стиле eXtreme Programming

Это что такое? Придти к преподу с бейсбольной битой и попросить по-хорошему написать за себя прогу? smile

zim22

Дата 9.4.2009, 08:36 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

Цитата(Anikmar @ 9.4.2009, 07:48

)

Это что такое? Придти к преподу с бейсбольной битой и попросить по-хорошему написать за себя прогу?

я думаю вы знаете, что такое XP, так что не буду утруждать себя объяснениями smile

--------------------

C++ FAQ Lite

Anikmar

Дата 9.4.2009, 09:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(zim22 @ 9.4.2009, 08:36

)

я думаю вы знаете, что такое XP, так что не буду утруждать себя объяснениями

Касательно к данной задаче - покупается в ларьке сборник кроссвордов и отдается преподу. Типа - это моя прога составила. Если в серединку буклетика вложить 50 баксов - поверит smile

зы.
Честно говоря, я только сегодня узнал, что то чем я занимаюсь по-научному называется XP-программирование. smile

Это сообщение отредактировал(а) Anikmar - 9.4.2009, 09:10

zim22

Дата 9.4.2009, 09:35 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

Цитата(Anikmar @ 9.4.2009, 09:05

)

Касательно к данной задаче - покупается в ларьке сборник кроссвордов и отдается преподу. Типа - это моя прога составила. Если в серединку буклетика вложить 50 баксов - поверит

спасибо, поднял настроение! smile

--------------------

C++ FAQ Lite

Albor

Дата 9.4.2009, 14:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: нет
Всего: 9

А почему бы не попробовать поступить проще, например "склеить" последовательно слова, по принципу игры в города, а всё что не "приклеилось" пустить отростками от полученной склейки. Чем не кроссворд? Зато быстро.
Упс. Хотя, конечно, в условии сетка.

Это сообщение отредактировал(а) Albor - 9.4.2009, 14:13

Anikmar

Дата 9.4.2009, 14:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(Albor @ 9.4.2009, 14:05

)

Там слов-то десяток. Не склеятся.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »