Задание 0. Код Грея

Срок выполнения: до 5 ноября, 23:59.

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

Для получения кода Грея может быть использован следующий простой алгоритм:

Код Грея для n бит может быть рекурсивно построен на основе кода для n-1 бит путем переворачивания списка бит (то есть записыванием кодов в обратном порядке), конкатенации исходного и перевернутого списков, дописывания нулей в начало каждого кода в исходном списке и единиц — в начало кодов в перевернутом списке.

Необходимо реализовать функцию, вычисляющую код Грея.

Инструкция по выполнению

  1. Ознакомьтесь с инструментами и материалами.

  2. Воспользуйтесь заготовкой проекта на Reason. В заготовке проекта уже есть git-репозиторий с первым коммитом.

    Для сборки и запуска исполняемого файла воспользуйтесь командой dune exec -- gray.

  3. Напишите реализацию функции gray в файле lib/gray/Gray.re, соответствующую сигнатуре в файле lib/gray/Gray.rei, вычисляющую код Грея.

    Функция должна принимать аргумент n типа int — количество бит в коде и возвращать список строк, образующих n-битный код Грея, в которых биты кодируются символами 0 и 1. Примеры того, как должна работать эта функция, можно посмотреть в тестах в файле lib/gray/Gray.re.

    Постарайтесь уместить код этой функции не более чем в 15 строк.

    Функция должна работать корректно для n от 0 до 15.

    Скорее всего вам могут пригодиться функции List.map, List.rev, а также оператор @ для конкатенации списков и оператор ++ для конкатенации строк.

  4. Напишите еще два модульных теста в файле lib/gray/Gray.re по аналогии с уже существующими в заготовке тестами. Тесты могут быть, например, такие:

    • Тест для случая n = 3.

    • Тест для случая n = 10, проверяющий только корректность длины результирующего списка.

      При необходимости вы можете ознакомиться с документацией к библиотеке ppx_inline_test.

  5. Напишите еще один приемочный тест (например, для случая n = 3) в файле bin/gray/gray.t по аналогии с уже существующими в заготовке тестами.

    При необходимости вы можете ознакомиться с документацией по Cram-тестам в Dune.

  6. Убедитесь в прохождении всех тестов командой dune test.

  7. Отформатируйте код командой dune fmt.

Сдача задания

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

  1. Настройте ваши идентификационные данные в git, если они еще не настроены.

    Полное имя принято указывать в порядке first + last.

    Пример настройки:

    git config --global user.name "Arthur Khashaev"
git config --global user.email arthur@khashaev.ru

    Пожалуйста, укажите ваше настоящее имя, чтобы было понятно, кому ставить оценку.

  2. Зарегистрируйтесь на хостинге GitLab.com, если у вас нет там аккаунта.

  3. Установите в профиле GitLab настоящее имя, аналогично настройке user.name в git, чтобы не пришлось гадать, кто сделал задание.

  4. Воспользуйтесь заготовкой проекта с начальным коммитом в ветке master.

  5. Создайте новый закрытый проект в GitLab.

    При создании выбирайте «пустой проект» и снимите галочку «Initialize repository with a README», чтобы в созданном репозитории не было вообще никаких коммитов.

  6. Настройте удаленный репозиторий в локальном и отправьте ветку master с начальным коммитом из заготовки проекта.

  7. Пригласите пользователя @Invizory в ваш репозиторий, предоставив роль Maintainer.

  8. Создайте и переключитесь на ветку (например, gray), в которой вы будете вести разработку. В ветке master при этом должен остаться только начальный коммит.

  9. Выполните задание согласно формулировке, сделав для этого необходимые коммиты.

  10. Создайте запрос на слияние и назначьте его на проверяющего.

  11. В случае наличия замечаний, их опубликуют в качестве комментариев к запросу на слияние, после чего вы сможете их учесть. Задание считается полностью выполненным тогда и только тогда, когда проверяющий нажмет «approve».