Все статьи | Блог студента

Личный опыт: олимпиадное программирование как способ развития разработчика

Статья написана студентом Хекслета. Мнение автора может не совпадать с позицией редакции
Личный опыт: олимпиадное программирование как способ развития разработчика главное изображение

Всем привет! Хочу поделиться опытом участия в олимпиаде по веб-разработке на PHP «Волга-IT XXI» и рассказать, какую пользу такие мероприятия могут принести начинающим программистам.

Кратко о формате олимпиады

Олимпиада состояла из двух этапов: дистанционного отборочного тура и очного финала, который проходил в Ульяновскому техническом университете. Кроме PHP, проводились соревнования по прикладному программированию на Java и C#, системному программированию на С++ и веб-дизайну. Задачи были максимально приближены к производственным: их составлением занимались программисты и дизайнеры из нескольких IT-компаний.

В отборочном туре участникам нужно было настроить сервер для игры Filler (или 7 colors) — аркады, выпущенной в 80-х годах. На сервере нужно было через фреймворк Laravel реализовать API для создания новой игры, отправки хода и получения текущего состояния. За дополнительные баллы можно было написать тесты, фронтенд и настроить окружение через Docker. Весь текст задания можно посмотреть здесь.

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

Проектирование

Самой сложной задачей на отборочном этапе было проектирование игры — нужно было вникнуть в игровую логику и понять, каким способом реализовать хранение данных. У меня было два варианта:

Сделать одну сущность Game со столбцом game_data, который будет содержать в себе данные о поле, игроках и клетках в формате JSON. Не нарушать принцип единой ответственности и сделать четкое разделение по сущностям: Game, User, Field, Cell.

Первый способ показался мне неправильным: данные при его реализации были бы похожи на один большой ком. С одной стороны, размеры игры по условиями могли быть 99x99 и не факт, что данные уместились бы в базе. С другой, логика операций чтения и записи была бы не понятной. В итоге я остановился на втором варианте с разделением сущностей.

При реализации логики я поместил весь функционал в класс App/Models/Field. Это было не лучшим решением: оно нарушается принцип единой ответственности, поскольку модель отвечает за работу с БД, описание сущности и логику приложения. Правильнее было бы разделить модель App/Models/Field на три части: описание сущности оставить там же, логику работы с БД вынести в App/Repositories/FieldRepository, а игровую логику вынести в App/Services/GameService.

На следующем этапе нужно было определить механизм захвата клеток. Здесь тоже было два варианта:

  1. Захватываются только соседние клетки;
  2. Захватываются все клетки, до которых противник не сможет дотянуться — то есть области, которые полностью перекрыты по периметру нашими клетками.

Я выбрал первый вариант, поскольку реализовать его значительно проще и он более распространен.

Реализация

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

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

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

Мой вариант реализации выглядит так:

public function fillField(int $width, int $height, int $fieldId): void
{
    $cell = new Cell();
    $cellsData = [];

    // create cells and fill field
    for ($y = 0; $y <= $height - 1;  $y++) {
        if ($y % 2 === 0) {
            for ($x = $width * ($y / 2); $x <= (($width - 1) / 2) + $width * ($y / 2); $x++) {
                $cellsData[] = $cell->createCellArray($x, 0, $fieldId);
            }
        } else {
            for ($x = ($width + 1) / 2 + $width * (($y - 1) / 2); $x < $width * (($y + 1) / 2); $x++) 
            {
                $cellsData[] = $cell->createCellArray($x, 0, $fieldId);
            }
        }
    }
    DB::table('cells')->insert($cellsData);
}

Реализация хода построена на рекурсии и выглядит так:

public function assignCellsToPlayerRecursive(Cell $cell, int $playerId): void
{
    ini_set('xdebug.max_nesting_level', 2000);

    $neighboringCells = $this->getNeighboringCells($cell->number, $cell->field->width, $cell->field->id);
    $neighboringCellsNextColor = [];
    foreach ($neighboringCells as $neighboringCell) {
        if ($neighboringCell['color'] == $cell->color) {
            $neighboringCellsNextColor[] = $neighboringCell;
        }
    }

    if (empty($neighboringCellsNextColor)) {
        return;
    }

    foreach ($neighboringCellsNextColor as $neighboringCell) {
        if ($neighboringCell['player_id'] != $playerId) {
            $neighboringCell->update(['player_id' => $playerId]);
            $this->assignCellsToPlayerRecursive($neighboringCell, $playerId);
        }
    }
}

Функция получения соседних клеток выглядит так:

public function getNeighboringCells(int $number, int $width, int $field_id): array
{
    $cells = [];
    $cases = [];
    if (($number - ($width - 1) / 2) % $width !== 0) {
        $cases[] = $number + ($width + 1) / 2;
        $cases[] = $number - ($width - 1) / 2;
    }
    if ($number % $width !== 0) {
         $cases[] = $number + ($width - 1) / 2;
         $cases[] = $number - ($width + 1) / 2;
    }
    foreach ($cases as $case) {
         $cell = Cell::query()
            ->where('number', '=', $case)
            ->where('field_id', '=', $field_id)
            ->first();
         if (!is_null($cell)) {
            $cells[$cell->number] = $cell;
         }
    }

    return $cells;
}

Вывод

Что дало мне участие в олимпиаде?

  • Я прокачал свои знания в Laravel, который изучал до этого несколько месяцев;
  • Сделал хороший кейс для портфолио, который смело можно указывать в резюме;
  • Получил опыт написания юнит- и интеграционных тестов в Laravel;
  • Получил опыт реализации фронтенд-части приложения и улучшил знания в JS. Между этапами я неоднократно возвращался к своей реализации и всячески пытался оптимизировать ее, в результате чего я на порядок увеличил скорость работы приложения.
Рекомендуемые программы

С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.

Иконка программы Фронтенд-разработчик
Профессия
Разработка фронтенд-компонентов веб-приложений
25 мая 10 месяцев
Иконка программы Python-разработчик
Профессия
Разработка веб-приложений на Django
25 мая 10 месяцев
Иконка программы PHP-разработчик
Профессия
Разработка веб-приложений на Laravel
25 мая 10 месяцев
Иконка программы Node.js-разработчик
Профессия
Разработка бэкенд-компонентов веб-приложений
25 мая 10 месяцев
Иконка программы Fullstack-разработчик
Профессия
Новый
Разработка фронтенд и бэкенд компонентов веб-приложений
25 мая 16 месяцев
Иконка программы Верстальщик
Профессия
Вёрстка с использованием последних стандартов CSS
в любое время 5 месяцев
Иконка программы Java-разработчик
Профессия
Разработка приложений на языке Java
25 мая 10 месяцев
Иконка программы Разработчик на Ruby on Rails
Профессия
Создает веб-приложения со скоростью света
25 мая 5 месяцев