Ball Sort Puzzle — это популярная мобильная игра на IOS/Android. Суть её заключается в перестановке шариков до тех пор, пока в колбах не будут шарики одного цвета. При этом шарик можно перетаскивать либо в пустую колбу, либо на такой же шарик.
Так случилось, что я в неё залип. Очнулся примерно через месяц, на 725 уровне. Он мне никак не давался — насколько бы глубоко я не пытался продумать свою стратегию. В итоге — с этим вопросом я вышел в интернет, и заодно выяснил несколько интересных особенностей головоломки.
Во-первых, — игра бесконечна почти бесконечна. По крайней мере уже сейчас на YouTube есть прохождения всех уровней в плоть до 5350, а в телеграмме гуляют скриншоты 10к+ уровней. Вторая особенность, и вот это уже некрасиво, — не у всех уровней есть решение.
Ну это ни в какие ворота — против нас играет коварный ИИ. Нужно действовать соответственно!
Под катом мы:
Придумаем алгоритм, решающий эту головоломку (Python)
Научимся парсить скриншот игры, чтобы скармливать алгоритму задачки (OpenCV)
Напишем телеграм бота, который будет принимать скриншоты и возвращать решения
Выстроим CI/CD через GitHub Actions и задеплоим бота на Яндекс.Функции
Погнали!
Решать такую задачу было весьма занимательно. Поэтому предлагаю заинтересованному читателю попробовать решить её самостоятельно.
Я же в первую очередь решил побить проблему на сущности. Это сделает алгоритм чуть более элегантным, а так же поможет в будущем парсить скриншоты игры:
class Colorclass Color:
def __init__(self, symbol, verbose_name, emoji):
self.symbol = symbol
self.verbose_name = verbose_name
self.emoji = emoji
def __repr__(self) -> str:
return f'Color({self})'
def __str__(self) -> str:
return self.emoji
class Ball:
def __init__(self, color: Color):
self.color = color
def __eq__(self, other: 'Ball'):
return self.color is other.color
def __repr__(self):
return f'Ball({self.color.verbose_name})'
def __str__(self) -> str:
return str(self.color)
class Flask:
def __init__(self, column: List[Color], num: int, max_size: int):
self.num = num
self.balls = [Ball(color) for color in column]
self.max_size = max_size
@property
def is_full(self):
return len(self.balls) == self.max_size
@property
def is_empty(self) -> bool:
return not self.balls
def pop(self) -> Ball:
return self.balls.pop(-1)
def push(self, ball: Ball):
self.balls.append(ball)
def __iter__(self):
return iter(self.balls)
def __getitem__(self, item: int) -> Ball:
return self.balls[item]
def __len__(self) -> int:
return len(self.balls)
def __str__(self) -> str:
return str(self.balls)
class Move:
def __init__(self, i, j, i_color: Color):
self.i = i
self.j = j
self.emoji = i_color.emoji
def __eq__(self, other: 'Move') -> bool:
return (self.i, self.j) == (other.i, other.j)
def __repr__(self) -> str:
return f'Ball({self})'
def __str__(self) -> str:
return f'{self.i} -> {self.j}'
Для решения будем использовать метод поиска с возвратом (Backtracking).
Решение задачи методом поиска с возвратом сводится к последовательному расширению частичного решения. Если на очередном шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и продолжают поиск дальше. Данный алгоритм позволяет найти все решения поставленной задачи, если они существуют.
В случае с нашей игрой это метод применяется так: мы рекурсивно обходим все возможные перестановки шариков (move) до тех пор, пока
Либо нас не выкинет наш критерий остановки — решённый пазл
Либо в нашем хранилище состояний (states
) не будет всех возможных перестановок — в таком случае решения нет
def solve(self) -> bool:
if self.is_solved:
return True
for move in self.get_possible_moves():
new_state = self.commit_move(move)
if new_state in self.states: # Cycle!
self.rollback_move(move)
continue
self.states.add(new_state)
if self.solve():
return True
self.rollback_move(move)
return False
Алгоритм достаточно прямолинейный и далеко не всегда выдаёт оптимальное решение. Тем не менее он справляется с решением большинства задачек из игры за 1 сек.
Проверим алгоритм на чём-нибудь попроще:
def test_3x3():
data_in = [
[color.RED, color.GREEN, color.RED],
[color.GREEN, color.RED, color.GREEN],
[],
]
puzzle = BallSortPuzzle(data_in)
result = puzzle.solve()
assert result is True
play_moves(data_in, puzzle.moves)
Полная версия программы доступна на github.
Мы будем работать с .jpg картинками двух видов
Каждый чётный раунд игры состоит из 11 колб и 36 шариков, а нечётный — 14 колб и 48 шариков. Чётные и нечётные раунды отличаются расположением колб, но на счастье всё остальное у них одинаковое — по 4 шарика в колбе, 2 колбы пустые, цвета используются одни и те же.
Первое, что хочется сделать — это обрезать рабочую область, оставив только колбы с шариками. В противном случае наша программа за шарики может принимать элементы управления, фон или рекламу. Для этого отрежем по четверти сверху и снизу изображения.
class ImageParser:
def __init__(self, file_bytes: np.ndarray, debug=False):
self.image_orig = cv2.imdecode(file_bytes, cv2.IMREAD_COLOR)
self.image_cropped = self.get_cropped_image(self.image_orig)
@staticmethod
def get_cropped_image(image):
height, width, _ = image.shape
quarter = int(height / 4)
cropped_img = image[quarter : height - quarter]
return cropped_img
Теперь будем искать кружочки. В библиотеке OpenCV ровно для этих целей существует метод HoughCircles. Чтобы его использовать нужно перевести изображение в чёрно-белый вид, а также “эмпирически подобрать” параметры поиска. Чтобы найденные кружочки потом расфасовать по колбам, нормализуем и отсортируем их.
@staticmethod
def normalize_circles(circles):
last_y = 0
for circle in circles:
if math.isclose(circle[1], last_y, abs_tol=3):
circle[1] = last_y
else:
last_y = circle[1]
return circles
def get_normalized_circles(self) -> List[Any]:
image_cropped_gray = cv2.cvtColor(self.image_cropped, cv2.COLOR_BGR2GRAY)
circles = cv2.HoughCircles(image_cropped_gray, cv2.HOUGH_GRADIENT, 2, 20, maxRadius=27)
if circles is None:
raise ImageParserError("No circles :shrug:")
circles = np.round(circles[0, :]).astype("int16")
ind = np.lexsort((circles[:, 0], circles[:, 1]))
circles = circles[ind]
circles = self.normalize_circles(circles)
ind = np.lexsort((circles[:, 0], circles[:, 1]))
circles = circles[ind]
return circles
Дальше будем определять цвет шарика.
Из-за того, что Telegram жмёт картинки мы не можем просто взять цвет центрального пикселя — он может быть артефактом компрессии. Поэтому найдём доминирующий цвет, — тот который в кружочке встречается чаще всего.
@staticmethod
def get_dominant_color(circle) -> Color:
colors, count = np.unique(circle.reshape(-1, circle.shape[-1]), axis=0, return_counts=True)
dominant = colors[count.argmax()]
return dominant
Этот доминирующий цвет мы будем сравнивать с изначально заданными цветами, и искать ближайший. В данной задаче нам на помощь приходит Евклидово расстояние и теорема Пифагора: если представить цвет точкой в трёхмерном пространстве, то расстояние до любой другой точки этого пространства:
Посчитаем такое расстояние до каждого из изначально заданных цветов и найдём минимальное
RBG_TO_COLOR = {
(147, 42, 115): VIOLET,
(8, 74, 125): BROWN,
(229, 163, 85): L_BLUE,
(68, 140, 234): ORANGE,
(196, 46, 59): BLUE,
(51, 100, 18): GREEN,
(35, 43, 197): RED,
(87, 216, 241): YELLOW,
(125, 214, 97): L_GREEN,
(123, 94, 234): PINK,
(16, 150, 120): LIME,
(102, 100, 99): GRAY,
}
COLORS = np.array(list(RBG_TO_COLOR.keys()))
def get_closest_color(color: np.ndarray) -> Color:
distances = np.sqrt(np.sum((COLORS - color) ** 2, axis=1))
index_of_smallest = np.where(distances == np.amin(distances))
smallest_distance = COLORS[index_of_smallest].flat
return RBG_TO_COLOR[tuple(smallest_distance)] # type: ignore
Далее нам остаётся только распределить шарики по колбам. Итоговый class ImageParser
доступен на github.
Узнать про то, как сделать телеграм бота на Python можно сразу из нескольких статей на хабре. Я лишь опишу пару нюансов, с которыми столкнулся.
Так как наш бот хоститься на Яндекс.Функции — триггером к его запуску будет запрос на заданный нами webhook.
Whenever there is an update for the bot, we will send an HTTPS POST request to the specified url, containing a JSON-serialized Update.
Если в сообщении есть массив photo
, то можно увеличить вероятность распознавания шариков выбрав фотографию с максимальным весом:
if photos := message.get('photo'):
# here photos is an array with same photo of different sizes
# get one with the highest resolution
hd_photo = max(photos, key=lambda x: x['file_size'])
Чтобы скачать картинку, придётся сделать 2 запроса к Telegram API
# Получение данных о файле, нас интересует ключ ответа file_path
GET https://api.telegram.org/bot{BOT_TOKEN}/getFile?file_id={file_id}
# Получение самого файла
GET https://api.telegram.org/file/bot{BOT_TOKEN}/{file_path}
В остальном же всё просто — получаем картинку, скармливаем её парсеру и затем алгоритму-решателю.
main.pydef handler(event: Optional[dict], context: Optional[dict]):
body = json.loads(event['body']) # type: ignore
print(body)
message = body['message']
chat_id = message['chat']['id']
if photos := message.get('photo'):
# here photos is an array with same photo of different sizes
hd_photo = max(photos, key=lambda x: x['file_size']) # get one with the highest resolution
try:
file = telegram_client.download_file(hd_photo['file_id'])
except TelegramClientError:
text = "Cant download the image from TG :("
else:
file_bytes = np.asarray(bytearray(file.read()), dtype=np.uint8)
try:
image_parser = ImageParser(file_bytes)
colors = image_parser.to_colors()
except ImageParserError as exp:
text = f"Cant parse image: {exp}"
else:
puzzle = BallSortPuzzle(colors) # type: ignore
solved = puzzle.solve()
if solved:
text = get_telegram_repr(puzzle)
else:
text = "This lvl don't have a solution"
else:
return {
'statusCode': 200,
'headers': {'Content-Type': 'application/json'},
'body': '',
'isBase64Encoded': False,
}
msg = {
'method': 'sendMessage',
'chat_id': chat_id,
'text': text,
'parse_mode': 'Markdown',
'reply_to_message_id': message['message_id'],
}
return {
'statusCode': 200,
'headers': {'Content-Type': 'application/json'},
'body': json.dumps(msg, ensure_ascii=False),
'isBase64Encoded': False,
}
Отмечу ещё один нюанс: телеграм очень строго следует политике экранирования спецсимволов. Для Markdown это:
To escape characters ‘_’, ‘*’, ‘`’, ‘[‘ outside of an entity, prepend the characters ” before them.
Любой такой неэкранированный символ — и вы не увидите ответа в телеграм-чате. И останется только гадать — является ли это ошибка интеграции или вот такой коварный баг. Будьте осторожны.
Про создание Я.Функции также есть отличная статья от @mzaharov. Там подробно описан процесс заведения функции, а также установки вебхука для телеграмм бота.
Я расскажу как сделал Continuous Delivery при помощи GitHub Actions. Каждая сборка мастера увенчивается деплоем новой версии функции. Такой подход заставляет придерживаться модели разработки GithubFlow с его главным манифестом
Anything in the
master
branch is always deployable.
Каждая сборка мастера состоит из 3ёх этапов
lint (black, flake8, isort, mypy) — проверка кода на соответствие всем стандартам Python 2020
test — тестируем программу с помощью pytest, поддерживая качество и покрытие кода
deploy — непосредственно заливаем новую версию приложения в облако
Деплоить будем с помощью Yandex-Serveless-Action — уже готового Action для использования в своих пайплайнах
deploy:
name: deploy
needs: pytest
runs-on: ubuntu-latest
if: github.ref == 'refs/heads/master'
steps:
- uses: actions/checkout@master
- uses: goodsmileduck/yandex-serverless-action@v1
with:
token: ${{ secrets.YC_TOKEN }}
function_id: ${{ secrets.YC_FUNCTION_ID }}
runtime: 'python38'
memory: '256'
execution_timeout: "120"
entrypoint: 'main.handler'
environment: "
TELEGRAM_BOT_TOKEN=${{ secrets.TELEGRAM_BOT_TOKEN }}"
source: 'app'
Переменные окружения программы и сборки спрячем в GitHub Secrets на уровне репозитория.
Бота можно найти в telegram по позывному @ballsortpuzzlebot.
Все исходники — на Github.
Присоединяйтесь к маленькому community любителей этой игры в telegram. Бот был добавлен в группу и внимательно следит за всеми отправленными картинками.
Бонус! Уровни, у которых нет решенияМой алгоритм умывает руки — говорит что перебрал все возможные комбинации и решения нет. Возможно это баг алгоритма.. или QA-отдел мобильной игры просто забил на эти уровни, так как не предполагал, что кто-то так далеко зайдёт)
Для меня это был интересный опыт скрещивания технологий (Telegram API + Python + OpenCV + Lambda). Надеюсь он окажется полезен кому-нибудь ещё.
Найденные баги, предложения по оптимизации алгоритма, или даже PR в репозиторий крайне приветствуются
С новым годом!
24 апреля 2024 года в Москве состоялась церемония вручения наград международного конкурса Workspace Digital Awards. В этом году участниками стали…
27 июня Яндекс проведет гик-фестиваль Young Con для студентов и молодых специалистов, которые интересуются технологиями и хотят работать в IT.…
Павел Дуров сообщил, что Telegram начнет цензурировать контент по требованию Apple. В противном случае приложение Telegram может быть удалено из…
Реклама. ООО КьюСофт, ИНН 7714594610 Erid: 2SDnjdVN7Cd Теперь в ТИМЛИ можно выстроить полный цикл работы отдела: генерировать идеи и бизнес-цели в интеллект-картах…
Облачная платформа VK Cloud запустила сервис Cloud Kafka. Это решение на базе технологий с открытым исходным кодом Apache Kafka и…
Администрация президента отклонила предложенные Минцифры поправки ко второму чтению законопроекта об оборотных штрафах за утечку персональных данных. Они предусматривали смягчение…