# Отчет по практике. Команда DeepIntoC
## `ссылка на документацию`
## `ссылка на багрепорт`

## Общие моменты выполнения практики
### Используемые ресурсы
1) https://repl.it/ - платформа для совместного написания кода;
2) discord - коммуникация в процессе обдумывания решения и совместного написания кода;
3) telegram - коммуникация, обсуждение мелких моментов;
### Временные рамки
**Начало изучения заданий практики:** 8 мая 2020.
**Начало реализации решений для задач:** 9 мая 2020.
**Последний коммит (все задачи решены):** 18 мая 2020.
**Сопровождение (отслеживание результатов соревнований и готовность совершенствовать реализованные решения):** до 3 июня 2020(конец практики).
### Достижения
+ 5 золотых медалей из 8 на момент написания отчёта (22:00, 3 июня 2020);
+ первыми реализовали решение для STRgame, которое всё ещё лидирует по скорости работы;
+ уверенное лидерство в TEEN48game, при том программа работает не в полную силу (подробнее в последующих разделах отчёта);
+ уверенное лидерство в дивизионе 3 на 3 для XOgame и 1-3 место, разделяемое с командами AlfErTeam и NICE в дивизионе 5 на 5 до появления "груш для битья" от других команд ближе к завершению практики (до 31 мая 2020; причины сдачи позиций освещены в последующих разделах отчёта)
+ все актуальные решения были готовы 18 мая 2020 (с учетом позднего старта 9 мая);
+ малое количество неудачных тестирований (большая часть проваленных job-ов связана с нашими эксперементами в TEEN48game и различиями в компиляции программы с обязательными ключами в нашей и тестовой системе).
### Особенности работы в течение практики
+ Вся работа с кодом осуществлялась на сторонней платформе (repl.it), с чем связанна активность в репозитории только с одного аккаунта и отсутствие промежуточных коммитов.
+ Благодаря использованию сторонней платформы (repl.it) отсутствовала необходимость строго разбивать решения на задачи для каждого члена команды, имелась возможность совместно в реальном времени работать над одной задачей, а использование discord упростило решение "конфликтных" ситуаций и обеспечило оперативность и согласованность в написании кода.
+ Объем совершённой работы примерно поровну разделился между обоими участниками.
+ Решения для NUM63RSgame, 7EQUEENCEgame и STRgame выполнены в виде единственной функции без декомпозиции на каждое задание. Причиной этому послужило то, что мы неправильно поняли пункты "сигнатура" и "Ожидаемый конечный вариант выполнения задания" из раздела "Теория и правила игры" на момент реализации решений для вышеперечисленных задач.
+ Решения для XOgame и TEEN48game содержат примитивный AI (подробнее в разделах, посвященных играм).

## NUM63RSgame
### Идея
Необходимо найти наименьшее общее кратное для всех чисел из интервала `[min, max]`. Наиболее простое и неэффективное решение: перебор всех целых чисел начиная с 0 и до первого числа, которое является НОК. Оптимальное решение: следует из того факта, что `НОК(a, b, c) = НОК (НОК(a, b), c)`. Для поиска НОК двух чисел можно использовать алгоритм Евклида `(НОК(a, b) = a * b / НОД(a, b))`.
### Реализация
Поиск НОК(НОК n-1, n), НОК 1 = НОК (min, min + 1).
#### Первая версия
Используется алгоритм Евклида через вычитание. Проблема - порядок арифметических действий приводит к переполнению при максимальных значениях в рамках игры. Скорость выполнения задачи оставляет желать лучшего.
#### Вторая версия
Изменен тип некоторых переменных (с int на long long). Программа действует корректно в рамках игры, но скорость всё еще плохая.
#### Третья версия
Алгоритм Евклида через вычитание проигрывает алгоритму Евклида через остаток от деления в скорости при работе с большими числами. Соответственно, Алгоритм Евклида внутри программы заменён на свою более эффективную версию. Также изменен порядок действий и присвоения переменных, возврат к переменным int. Достигнут желаемый результат.

## 7EQUEENCEgame
### Идея
Решение в лоб - перебор 988 произведений в цикле, каждый раз элементы перемножаются заново. Оптимальное решение: использование решения наподобие 27 задания из ЕГЭ по информатике - "динамический" массив. Рассматриваем промежуток из 13 элементов, при сдвиге на одну позицию вперед произведение делится на "ушедший" из промежутка элемент и умножается на "вошедший" в промежуток элемент. Проблема данного решения - возможность встретить 0 в массиве `(n * 0 = 0; n / 0 = error)`.
### Реализация
Используется динамический массив "ЕГЭ по информатике", что значительно сокращает время выполнения задачи. Необходимый момент - проверка на вхождение 0 в промежуток. Если программа встречает 0, она перепрыгивает на промежуток сразу за встреченным нулем до тех пор, пока не наткнется на промежуток, не содержащий нули. Данный элемент не только является защитой от ошибки вычисления, но и значительно сокращает время работы программы. (По крайней мере, данное утверждение верно для работы с массивом целых чисел, описанном в problem 8 (https://projecteuler.net/problem=8)). Было выяснено, что ежедневные соревнования проводятся при использовании массивов только с положительными числами (без 0), но проверка на встречу нуля не была исключена из программы, так как, по нашему мнению, сокращение времени обработки массива не стоит того, чтобы урезать функционал.

## STRgame - STRTOK
### Идея
Было принято решение обратиться к проверенным ресурсам для получения имплементации функции strtok с целью написания идеально повторяющей поведение её поведение собственной реализации. Эта идея была обоснована тем фактом, что библиотека `<string.h>` может быть воспроизведена с помощью имеющихся инструментов библиотеки `<stdio.h>` (хоть это и оказалось не совсем так).
(!!! Не для отчёта: https://stackoverflow.com/questions/28931379/implementation-of-strtok-function !!!)
### Реализация
Имплементация показывает, что функция strtok включает в себя другие функции библиотеки `<string.h>`: `strspn` и `strpbrk`, а также `rawmemchr`. "Наблюдение" за первыми двумя функциями и точное воспроизведение их поведения не вызвало проблем, а третья была заменена более простой собственной реализацией, уступающей по скорости, но в данном случае это не было критично.

## STRgame - SPLIT
### Идея
Проблемой реализации является различие входящих и возвращаемых аргументов в питоне и си. Необходимо было самостоятельно догадываться, чего требует задача практики.
### Реализация
#### Первая версия
Начальная реализация split была схожа с многократным вызовом функции strtok. Решение не являлось верным.
#### Вторая версия
Были проведены более детальные наблюдения за поведением split из python. Вывод: решение оказалось куда проще предыдущего, символы, не являющиеся разделителем, записываются в строку: символы, являющиеся разделителем, записывают в строку `'\0'` и переводят указатель массива на следующую строку. Добавлено исключение: `if (str == NULL): words = {""}` Реализация оказалась правильной.

## XOgame
### Идея
Первым приходящим на ум решением является прописывание нужных ходов через ветвление условий (состояния поля на данный момент). К реализации этого варианта не приступали по нескольким причинам:
1) слишком большое дерево ходов (примерно 8 * 6 * 4 * 2 возможных расположений символов на поле при игре программы за X и 9 * 7 * 5 * 3 возможных расположений символов на поле при игре программы за O);
2) Стойкое ощущение, что изучение всех выигрышных комбинаций в игре крестики - нолики не является приоритетным решением в практике по программированию).
Было проведено изучение основных алгоритмов в теории игр. Мы остановились на алгоритме minimax (правило принятия решений для минимизации возможных потерь из тех, которые лицу, принимающему решение, нельзя предотвратить при развитии событий по наихудшему для него сценарию). Главным его преимуществом мы посчитали возможность реализовать бота так, чтобы он не терпел поражений (принципы игры крестики - нолики 3 на 3 и тем более 5 на 5 позволяют это сделать).
### Начальная реализация
Аглгоритм minimax (рекурсивная функция) заключается в том, чтобы выбирать наиболее выгодный для игрока ход при совершении противником наболее выгодного хода для себя. Производится оценка дерева исходов по следующему принципу (описание в теминах крестики - нолики для лучшего понимания): если текущим ветвлением являются ходы ПРОТИВНИКА, то узлу ветвления передается значение НАИМЕНЕЕ выгодного для игрока варианта (Пример: узел ветвления - ход X в угловую ячейку, ветвление: ход O в ячкейку 1 - игра не закончена, ход O в ячкейку 2 - игра не закончена,..., ход O в ячкейку n - победа O, наихудший исход; следовательно ходу X в угловую ячейку соответствует поражение игрока); если текущим ветвлением являются ходы ИГРОКА, то узлу ветвления передается значение НАИБОЛЕЕ выгодного для игрока варианта (Пример: узел ветвления - ход O в угловую ячейку, ветвление: ход X в ячкейку 1 - игра не закончена, ход X в ячкейку 2 - игра не закончена,..., ход X в ячкейку n - победа X, наилучший исход; следовательно ходу O в угловую ячейку соответствует победа игрока). Для оценки ситуации используется специальная check-функция и показатель depth, обозначающий то, при какой заполненности поля достигнут некоторый результат (победа, поражение, ничья, игра не закончена). Изначально check-функция писалась с учетом правила '4 в ряд' для игры на поле 5 на 5, но после изучения материалов проекта в открытом доступе был сделан вывод, что условием победы в игре 5 на 5 являются 5 символов в ряд, что позволило сделать check-функцию универсальной. Как только check-функция сообщает о завершении игры при конкретном исходе, ему присваивается определенное значение: результат(0 - ничья, 1 - победа, -1 - поражение) * depth(для простоты понимания - количество свободных клеток на поле, актуально для победы или поражения) (пример: ход X в угловую ячейку, победа, 4 свободных клетки на поле => результат = 4). В конечном итоге каждому из начальных разветвлений (т. е. текущему ходу программы) присваивается итоговый результат, и основная фунция возвращает координаты для наиболее выгодного хода. (!!! не для отчёта https://www.youtube.com/watch?v=l-hh51ncgDI&feature=youtu.be !!!)
(!!!в самой программе коэф. depth может отличаться на 1 от его описания здесь, но сути это не меняет!!!)
### Проблемы начальной реализации
На поле 3 на 3 программа показывает себя крайне эффективно, но размер дерева вероятности для игры 5 на 5 является слишком большим для обработки программой за адекватное время. Требовалось повышение эффективности алгоритма.
### Улучшения
В ходе более глубокого изучения алгоритма minimax и методов его оптимизации было обнаружено подходящие нам решение: алгоритм alpha beta pruning (Описание сути на русском: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D1%8C%D1%84%D0%B0-%D0%B1%D0%B5%D1%82%D0%B0-%D0%BE%D1%82%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5). Это решение является универсальным для minimax. Частным решением является отсечение дальнейшего поиска по ветвлению, если одно из разветвлений является завершением игры (не ничья) (пример: n возможных ходов, первый приводит к победе, а значит, нет смысла рассматривать остальные, так как мы уже имеем необходимый результат). Совокупность решений для оптимизации minimax всё равно не позволила программе обрабатывать полное дерево исходов для поля 5 на 5, потому было принято решение расширить применение параметра depth. В новой реализации параметр позволяет ограничить глубину/вложенность ветвления (например, чтобы убедиться, что текущий ход не подставит игрока и не приведет к поражению, но сделать это за адекватное время). Технический ресурс нашей команды не позволяет отследить максимально эффективное соотношение "свободные клетки(от этого зависит размер дерева исходов) : глубина изучения дерева исходов", потому глубина в зависимости от количества свободных клеток подбиралась по времени, затрачиваемому на ход. Ограничение глубины приводит к тому, что первые ходы в партии формируют "шахматное поле", что не выглядит эффективным решением. Из-за этого пришлось прописать начальные ходы через ветвление условий.
### Проблемы финальной версии
Алгоритм игры на поле 5 на 5 всё ещё не совершенен, использование minimax приводит к тому, что бот играет от защиты, а не от нападения. Соответственно, вероятность поражения бота крайне мала (или равна нулю), но при этом страдает вероятность победы, так как наиболее вероятным исходом игры от защиты является ничья. Поставленные цели достигнуты - бот не проигрывает, но в соревнованиях часто случается ничья, что не очень благоприятно сказывается на очках в дивизионе.

## TEEN48 GAME
### Идея
Алгоритм minimax продемонстрировал свою эффективность в предыдущей соревновательной игре, но в данном случае игра не предполагает наличие противника в классическом понимании. Присутствие элемента рандома также ставит под сомнение эффективность использования minimax. К тому же, было бы не очень интересно снова использовать тот же метод (больше экспериментов - больше знаний). Исследование секретных тактик тоже не является приоритетным вариантом реализации программы, так как это не является основной целью углубленного изучения языка программирования. В данном случае из множества алгоритмов теории игр нами был выбран monte carlo tree search (далее MC). Его модификация в нашем случае будет рассмотрена в разделе "Реализация"
### Начальная реализация
Важным фактором при выборе метода для нас послужило начальное разветвление дерева исходов - всегда 4 возможных хода/действия. Алгоритм, основанный на MC предполагает проведение некоторого количества случайных игр для каждого из начальных ходов. Результаты игр суммируются для каждого начального направления, а затем сравниваются. (!!! в программе суммарный счет делится на 100 - это артефакт версии со статичным количеством ранов, роли не играет. не важно, что сравнивать : `x и y` или `x/100 и y/100`!!!) Основная функция возвращает символ, соответствующий направлению с наибольшим суммарным счётом. В дальнейшем тесты на поле 4 на 4 показали, что достаточно эффективным количеством случайных игр является 100 (это число и используется в финальной версии для поля 4 на 4). Наиболее тяжёлыми в плане реализации частями алгоритма являются рандомная генерация в Си и модификация копии поля (сдвиги, мерджи; используется копия поля, так как изменения на поле значительно труднее откатить, чем в игре крестики-нолики). Попытки самостоятельно реализовать рандом на Windows с помощью библиотеки time не увенчались успехом, но опытным путём удалось выяснить, что в тестовой системе определена встроенная функция random() (!!!У меня в qt на винде её нет, приходилось писать вслепую!!!). На ней и было решено остановиться. Функции для обработки игрового поля были позаимствованы из открытых источников в главном проекте, адаптированы сначала под синтаксис и функционал Си, а потом и под реализованный в программе рандом. (!!! например: в питоне фунция генерировала рандомную точку до тех пор, пока она не попадет в пустую клетку, я же считаю N = количество пустых клеток, генерирую число в промежутке от нуля до N - 1 включительно, потом по порядку перебираю пустые клетки и в нужном месте вставляю точку !!!) Рациональным решением является то, что все смещения и объединения производятся свайпом влево, но перед этим матрица поворачвается(транспонируется и/или отражается) так, чтобы привести любой ход к ходу влево. (!!!Пояснения к функциям, которые я "одолжил" https://git.iu7.bmstu.ru/IU7-Projects/iu7games/-/blob/master/games/teen48/teen48_runner.py !!!)
### Проблемы начальной реализации
Программа не проходила тесты, так как время тестирование ограничено (1 час), исходя из информации в открытом доступе, условием успешного завершения тестирования является получение финального счёта обеих игр (4 на 4, 6 на 6) и демонстрация пользователю конечного состояния поля. Дело в том, что алгоритм оказался достаточно эффективным, чтобы после часа игры на поле 6 на 6 так и не встретить поражение.
### Улучшения
Первым делом мы пердположили, что на совершение одного хода программа затрачивает слишком много времени (примерно 0.5 с для поля 6 на 6). Дальнейшие изменения касаются только версии 6 на 6. Время, затрачиваемое на ход, было сокращено примерно в 10 раз за счет уменьшения количества рандомных игр. Ситуация с тестами повторилась, а легкореализуемых возможностей уменьшить время на ход у нас не было. Одной из идей было обратиться к организаторам для решения спорной ситуации, однако после некоторых размышлений нам показалось интересным принять это дополнительное условие и выжать из отведённого нам часа всё возможное. Опытным путем мы приблизились к результату 330 тысяч (в виде условия, приводящего бота к нерациональному поведению и скорому завершению игры) за 50 минут (10 оставшихся минут - "пространство для манёвра").
### Проблемы финальной версии
Невозможность продемонстрировать реальную эффективность программы на игровом поле 6 на 6.

# ВВОД задание 2

int str_input(char *string)
{
    int ch, i = 0;

    while ((ch = getchar()) != EOF && ch != '\n' && ch != '\r' && ch != '\0' && i <= MAX_STR_LEN)
    {
        string[i] = ch;
        i++;
    }
    if (i <= MAX_STR_LEN)
        string[i] = '\0';
    else
        i = 0;

    return i;
}

в main:

int str_len1 = str_input(string1), str_len2 = str_input(string2);

    if (str_len1 && str_len2)
    {
        ...
    }
    else
    {
        //printf("Error!");
        r = 1;
    }

# Ввод 3 задание

int str_input(char *str)
{
    int ch_check = 1, cycle_flag = 1;
    int i = 0;

    for (i = 0; i < MAX_STR_LEN + 1 && cycle_flag && ch_check && ch_check != EOF; i++)
    {
        ch_check = scanf("%c", str + i);
        if (ch_check && ch_check != EOF && (str[i] == '\0' || str[i] == '\n'))
            cycle_flag = 0;
    }
    if (i == MAX_STR_LEN + 1)
        ch_check = 0;
    *(str + --i) = '\0';

    return i * ch_check;
}

в main

int str_len = str_input(str);
    if (str_len > 0 && str_len < MAX_STR_LEN + 1)
    {....

# Функции
# XO
## check_result
### принимаемые параметры
матрица игрового поля, размер игрового поля, наш символ, символ противника
### возвращаемые параметры
field_size - игра не окончена
-1 - поражение
0 - ничья
1 - победа
(несколько точек выхода в функции, возвращаемые значения являются множителями для подсчета очков)
## minimax
### in
поле, размер, свой символ, чужой символ, глубина(вложенность) (сомножитель при подсчете результата) alpha, beta - флаги a b pruning улучшения алгоритма, режим максимизации (1 - максимизация, выбор наиболее удачной ветки; 0 - минимизация - выбор наименее удачной ветки.
### out
счёт (лучший или худший, по ситуации)

# MAIN

#include <stdio.h>
#include "my_string.h"

int main()
{
    int r = 0;
    char string1[MAX_STR_LEN + 1], string2[MAX_STR_LEN + 1];
    int str_len1 = str_input(string1), str_len2 = str_input(string2);

    if (str_len1 && str_len2)
    {
        int words_count1 = 0, words_count2 = 0;
        int *p1, *p2;
        p1 = &words_count1;
        p2 = &words_count2;
        if (str_check(string1, str_len1, p1) && str_check(string2, str_len2, p2))
        {
            char buffer1[WORDS_TOTAL][MAX_WORD_LEN + 1], buffer2[WORDS_TOTAL][MAX_WORD_LEN + 1];
            char *words1[WORDS_TOTAL], *words2[WORDS_TOTAL];
            transform(words1, *buffer1);
            transform(words2, *buffer2);

            get_words_from_str(words1, string1, p1);
            get_words_from_str(words2, string2, p2);
            mark_duplicates(words1, p1);
            find_duplicates_between_strs(words1, p1, words2, p2);
        }
        else
        {
            //printf("Error!");
            r = 1;
        }
    }
    else
    {
        //printf("Error!");
        r = 1;
    }

    return r;
}

# func.h

#ifndef _MY_STRING_H_

#define _MY_STRING_H_
#define MAX_STR_LEN 256
#define MAX_WORD_LEN 16
#define WORDS_TOTAL 16
// MAX_STR_LEN / MAX_WORD_LEN

int separation_char(char ch);
int compare_words(char *word1, char *word2);
int str_input(char *string);
int str_check(char *string, int i, int *words_count);
void transform(char **words, char *buffer);
void get_words_from_str(char **words, char *string, int *p);
void mark_duplicates(char **words, int *p);
void find_duplicates_between_strs(char **words1, int *p1, char **words2, int *p2);

#endif

# func.c

#include <stdio.h>
#include "my_string.h"

int separation_char(char c)
{
    int sep_check = 0;

    if (c == ',' || c == ';' || c == ':' || c == '-' || c == '.' || c == '!' || c == '?' || c == ' ')
        sep_check = 1;

    return sep_check;
}

int compare_words(char *word1, char *word2)
{
    int check = 1;

    for (int i = 0; i < MAX_WORD_LEN; i++)
        if (word1[i] != word2[i])
            check = 0;

    return check;
}

int str_input(char *string)
{
    int ch, i = 0;

    while ((ch = getchar()) != EOF && ch != '\n' && ch != '\r' && ch != '\0' && i <= MAX_STR_LEN)
    {
        string[i] = ch;
        i++;
    }
    if (i <= MAX_STR_LEN)
        string[i] = '\0';
    else
        i = 0;

    return i;
}

int str_check(char *string, int i, int *words_count)
{
    int word_check = 0, word_len_check = 1, total_check = 0;
    int word_len = 0;

    for (int j = 0; j < i; j++)
    {
        if (separation_char(string[j]))
            word_len = 0;
        else
        {
            if (word_len == 0)
                *words_count += 1;
            word_len += 1;
            if (word_len > MAX_WORD_LEN)
                word_len_check = 0;
            word_check = 1;
        }
    }
    if (word_check && word_len_check)
        total_check = 1;

    return total_check;
}

void transform(char **words, char *buffer)
{
    for (int i = 0; i < WORDS_TOTAL; i++)
        words[i] = buffer + i * (MAX_WORD_LEN + 1);
}

void get_words_from_str(char **words, char *string, int *p)
{
    int ch = 0;
    for (int i = 0; i < *p; i++)
    {
        while (separation_char(string[ch]))
            ch++;
        int j = 0;
        while (!separation_char(string[ch]) && string[ch] != '\0')
        {
            words[i][j] = string[ch];
            ch++;
            j++;
        }
        while (j <= MAX_WORD_LEN)
        {
            words[i][j] = '\0';
            j++;
        }
    }
    for (int i = *p; i < WORDS_TOTAL; i++)
        for (int j = 0; j < MAX_WORD_LEN; j++)
            words[i][j] = '\0';
}

void mark_duplicates(char **words, int *p)
{
    for (int i = 0; i < *p; i++)
        if (words[i][0] != '\0')
            for (int j = i + 1; j < *p; j++)
                if (compare_words(words[i], words[j]))
                    words[j][0] = '\0';
}

void find_duplicates_between_strs(char **words1, int *p1, char **words2, int *p2)
{
    printf("Result:");
    for (int i = 0; i < *p1; i++)
        if (words1[i][0] != '\0')
        {
            int current_d_check = 0;
            for (int j = 0; j < *p2; j++)
                if (!current_d_check && compare_words(words1[i], words2[j]))
                {
                    current_d_check = 1;
                }
            printf("\n%s ", words1[i]);
            if (current_d_check)
                printf("yes");
            else
                printf("no");
        }
}