Отбор на кафедру 1С в МФТИ.
На вход программе подаётся изображение игрового поля в крестики-нолики.
Необходимо обработать его и провести "победную" линию (перечёркивающую три одинаковых символа по правилам игры). Игровое поле может не содержать победителя (Тогда никакую линию проводить не надо). Гарантируется, что существует только одна победная линия.
Формат изображения -- png. Игровое поле находится в произвольном месте изображения, однако гарантируется, что все символы имеют одинаковый размер/толщину и центрированы относительно секторов. Линии игрового поля проведены параллельно краям изображения. Если алгоритм решения будет требовать определённого размера/толщины фигур -- отразите это в документации.
По суть решение задачи состоит из следующих частей:
- Перевести картинку в двумерный массив
- Перевести цвета картинки в черно белый (True или False)
- Определить границы игрового поля и размер сетки
- Распознать фигуры на поле (крестик, нолик или пусто)
- Определить "победную" линию или указать на ее отсутствие
- Нарисовать победную линию на той же картинке
Я реализовал все эти этапы кроме последнего, зато написал документацию, тесты и комментарии в коде, чтобы вам было удобнее читать.
Теперь про решение каждого из этапов:
"Перевести картинку в двумерный массив", "Перевести цвета картинки в черно белый (True или False)" - тривиально
"Определить границы игрового поля и размер сетки" - нахожу левую и правую границу сетки, из них вычисляю остальное.
"Определить "победную" линию или указать на ее отсутствие" - тоже просто. достаточно пройтись по всем строкам и диагоналям
Мы знаем границы каждой секции поля. Для каждой секции решаем задачу независимо.
Осталось для каждой секции запустить функцию, которая будет вычислять тип фигуры в этой секции - крестик, нулик или пусто.
Пустоту определить довольно просто :)
Крестик от нолика на самом деле отличить тоже несложно. Мы знаем, что символы центрированны относительно секторов. Тогда, если мы проведем вертикальную линию, соединяющую середины верхней и нижней сторон, он поможет нам отличить круг от крестика. Крестик будет пересекать эту линию один раз, а круг - два раза.
Это тоже тривиальная задача, но доделать ее я не успел. Зная координаты отрезка, который мы хотим нарисовать, сделать это очень просто.
Для этого бы берем старый numpy массив, проходимся там по ячейкам от одного конца отрезка до другого и красим их в черный цвет.
Важно, что красить надо не линию в один пиксель, а сразу полоску, чтобы линию на картинке было видно.
Имея новый numpy массив мы просто переводим его обратно в png и получаем картинку. Готово!
Наверное пока я так подробно это рассказывал, мог бы уже и написать...
pip3 install -r requirements.txtpython3 main.pypython3 -m unittest tests/*Тестами покрыта следующая функциональность: поиск границ игрового поля и распознавание фигуры внутри ячейки.
- Не полностью покрыл тестами. Да и в челом решение слабо протестировано
- Местами код плохой, было мало времени
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent