Для тестирования на платформе CodinGame нужно вставить содержимое файла pch.h в начало программы.
Компиляция исходных файлов происходит с параметром принудительного включения заголовочного файла pch.h. В данных примерах этот файл заменяет предварительно cкомпилированный заголовок.
msvc /FI pch.h program.cpp -o program (для msvc)
gcc -include pch.h (для gcc)
В рамках тестового задания было выполнено 9 задач различной сложности:
- Power of Thor - Episode 1
- Temperatures
- The descent
- Onboarding
- ASCII art
- Unary
- MIME Type
- Defibrillators
- Mars Lander - Episode 1
В коде реализован алгоритм поиска пути A* для перемещения Тора к молнии на сетке 40x18. Для движения в 8 направлениях в качестве эвристики используется расстояние Чебышева. Алгоритм строит путь от начальной позиции к цели, сохраняя направления перемещения между соседними клетками в вектор directions.
Предварительный расчет всего пути до молнии перед началом движения. Для этого применяется приоритетная очередь для выбора оптимальных узлов, проверка границ сетки и предотвращение повторного посещения клеток через closedSet. На каждом шаге главный цикл выводит направление из заранее рассчитанного маршрута, потому что по условию задачи положение молнии статично.
Реализация алгоритма поиска кратчайшего пути на плоскости.
Поиск температуры, наиболее близкой к нулю, с учётом особого случая, когда две температуры имеют одинаковое абсолютное значение (например, -5 и 5). В такой ситуации выбирается положительная температура. Алгоритм заключается в последовательном переборе и сравнении абсолютных значений.
Сначала обрабатывает случай отсутствия температур, в таком случае выводится 0. Затем значения считываются в вектор, после чего в цикле сравниваются абсолютные величины температур. Если абсолютное значение текущего элемента меньше текущего ближайшего, оно становится новым кандидатом. При равенстве абсолютных значений выбирается положительное число.
Цель игры — уничтожать горы по очереди, начиная с наибольшей. Идея заключалась в определении на каждом шаге самой высокой горы и её атаки. Набор высот гор меняются после каждого выстрела, потому что наибольшие горы уничтожаются.
В коде реализован бесконечный цикл, который на каждом ходе считывает высоты восьми гор в вектор. С помощью std::max_element находится итератор на максимальный элемент, а std::distance вычисляет его индекс. Этот индекс сразу выводится как цель для атаки. Алгоритм не хранит состояния между ходами, так как актуальные данные поступают каждый раз.
В рамках задачи требовалось непрерывно определять ближайшего противника из двух доступных на каждом игровом цикле. Алгоритм заключается в сравнении расстояний до двух врагов и выборе имени того, кто находится ближе к игроку. Для этого использовался условный оператор.
Код реализует бесконечный цикл, в котором считываются попарно имя и расстояние до двух противников. Данные сохраняются в структуры Enemy, после чего расстояния сравниваются условными оператором. Результат — имя противника с меньшим расстоянием — выводится на каждом шаге.
Алгоритм заключается в преобразовании входного текста в ASCII-графику с использованием заранее заданного шрифта, который поступает пользовательским вводом. Для этого разбиваются символы шрифта на блоки фиксированной ширины, сохраняются в структуре данных для быстрого доступа и построчно собирается итоговое изображение. Особыми случаями была обработка нестандартных символов, заменяя их на символ "?", и приведение текста к верхнему регистру для приведение вывода к единому виду.
В коде реализовано чтение высоты и ширины шрифта и входной строки, после чего символы шрифта сохраняются в std::map, где ключ — буква, а значение — вектор строк ASCII-графики. Для вывода программа проходит по каждой строке высоты и для каждого символа входного текста выводит соответствующий фрагмент ASCII-арта, заменяя некорректные символы на "?". Это построчное формирование итогового изображение без предварительного хранения всего вывода в памяти.
Преобразование текста в последовательность битов ASCII (7 бит на символ) с последующей группировкой одинаковых битов в блоки. Для кодирования используется система, где единицы представляются как "0" + n нулей, а нули — как "00" + n нулей.
Алгоритм корректно преобразует строку в массив битов, группирует последовательные одинаковые биты и формирует блоки согласно правилам задачи.
Сопоставлении MIME-типов с расширениями файлов через словарь, предварительно приведя данные к нижнему регистру. Для обработки файлов извлекается расширение из имени, учитывая крайние случаи: отсутствие точек или завершающую точку.
Код считывает пары «расширение — MIME-тип» в std::map, приводит расширения к нижнему регистру. Для каждого файла проверяется наличие точек: если точек нет или имя оканчивается на точку, выводится UNKNOWN. В остальных случаях извлекается последняя часть после точки, ищется в словаре и выводится соответствующий MIME-тип (или UNKNOWN при отсутствии).
Обработка особых случаев. Этот код не прошёл по времени последний тест "Large Data". На форуме CodinGame пользователи жаловались на слишком малое ограничение по времени. Код, написанный на чистом C, также не проходил этот тест. Аналогичный код на Rust смог пройти все тесты.
Поиск ближайшего дефибриллятора к заданным координатам пользователя, для чего нужно парсить входные данные с корректировкой десятичных разделителей, преобразовывать координаты в радианы и использовать формулу, предложенную в задаче, для вычисления расстояний.
В коде реализована структура Defibrillator для хранения данных, функция для преобразования градусов в радианы. Числа с плавающей точкой разделены запятой, встроенная std функция перевода строки в число stod не работает с данным типом разделителя, поэтому была создана функция для замены разделителей. Данные парсятся через stringstream, заполняется вектор дефибрилляторов и ищется минимум расстояния через расчёт проекций x и y.
Представим марсоход в виде САУ, в которой движение происходит по целевым точкам. Регуляторы отвечают за изменения мощности двигателей. В данном случае рассматривается первая производная перемещения - скорость. Создадим регулятор для управления вертикальной скоростью марсохода с помощью осцилляторного подхода, сочетающего пропорциональную, интегральную и производную составляющие. Была реализована синусоидальная осцилляция для плавного изменения тяги. Это могло быть попыткой избежать резких колебаний и стабилизировать посадку за счёт периодического регулирования. Это экспериментальное решение для движения по вертикальной оси.
Был реализован класс OscillatoryRegulator, вычисляющий мощность двигателя на основе текущей вертикальной скорости. Код считывает данные о поверхности и находит горизонтальную площадку, что необходимо для 2 части этой задачи. В цикле регулятор получает ошибку, которая является разницей между желаемой нулевой и текущей вертикальной скоростью, и возвращает значение тяги от 0 до 4, комбинируя синусоидальный сигнал, интеграл и производную.
Подбор параметров регулятора для мягкой посадки. Для 2 части этой задачи нужно написать оптимизатор параметров регулятора.