Взламываем Ball Sort Puzzle
Ball Sort Puzzle — это популярная мобильная игра на IOS/Android. Суть её заключается в перестановке шариков до тех пор, пока в колбах не будут шарики одного цвета. При этом шарик можно перетаскивать либо в пустую колбу, либо на такой же шарик.
Так случилось, что я в неё залип. Очнулся примерно через месяц, на 725 уровне. Он мне никак не давался — насколько бы глубоко я ни пытался продумать свою стратегию. В итоге — с этим вопросом я вышел в интернет, и заодно выяснил несколько интересных особенностей головоломки.
Во-первых, — игра бесконечна почти бесконечна. По крайней мере уже сейчас на YouTube есть прохождения всех уровней вплоть до 5350, а в телеграмме гуляют скриншоты 10к+ уровней. Вторая особенность, и вот это уже некрасиво, — не у всех уровней есть решение.
Ну это ни в какие ворота — против нас играет коварный ИИ. Нужно действовать соответственно!
- Придумаем алгоритм, решающий эту головоломку (Python)
- Научимся парсить скриншот игры, чтобы скармливать алгоритму задачки (OpenCV)
- Напишем телеграм бота, который будет принимать скриншоты и возвращать решения
- Выстроим CI/CD через GitHub Actions и задеплоим бота на Яндекс.Функции
Алгоритмическое решение задачи
Решать такую задачу было весьма занимательно. Поэтому предлагаю заинтересованному читателю попробовать решить её самостоятельно.
Я же в первую очередь решил побить проблему на сущности. Это сделает алгоритм чуть более элегантным, а также поможет в будущем парсить скриншоты игры:
class 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()' def __str__(self) -> str: return self.emoji
class Ball
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()' def __str__(self) -> str: return str(self.color)class Flask
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
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()' def __str__(self) -> str: return f' -> ' Для решения будем использовать метод поиска с возвратом (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.
Преобразуем программу в Telegram Bot
Узнать про то, как сделать телеграм бота на 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/getFile?file_id= # Получение самого файла GET https://api.telegram.org/file/bot/
В остальном же всё просто — получаем картинку, скармливаем её парсеру и затем алгоритму-решателю.
def 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: " 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': , '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': , '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: $> function_id: $> runtime: 'python38' memory: '256' execution_timeout: "120" entrypoint: 'main.handler' environment: "\ TELEGRAM_BOT_TOKEN=$>" source: 'app'
Переменные окружения программы и сборки спрячем в GitHub Secrets на уровне репозитория.
Результат
Бота можно найти в telegram по позывному @ballsortpuzzlebot.
Присоединяйтесь к маленькому community любителей этой игры в telegram. Бот был добавлен в группу и внимательно следит за всеми отправленными картинками.
Бонус! Уровни, у которых нет решения
Мой алгоритм умывает руки — говорит что перебрал все возможные комбинации и решения нет. Возможно это баг алгоритма.. или QA-отдел мобильной игры просто забил на эти уровни, так как не предполагал, что кто-то так далеко зайдёт)
Заключение
Для меня это был интересный опыт скрещивания технологий (Telegram API + Python + OpenCV + Lambda). Надеюсь он окажется полезен кому-нибудь ещё.
Найденные баги, предложения по оптимизации алгоритма, или даже PR в репозиторий крайне приветствуются
Размеры шариков подшипников
Изготовление качественных шариков для подшипников — технологически сложный процесс, требующий высокой точности и использования современных инженерных решений. В целом его можно разделить на несколько этапов, от каждого из которых зависит прочность, долговечность и физические свойства будущего изделия.
Первый шаг в изготовлении шариков — выбор подходящего материала. Чаще всего используются хромистые стали, но в зависимости от условий эксплуатации элементы качения могут изготавливаться из керамики и нержавеющей стали.
Способы изготовления
Выбранный материал преобразуется в начальную форму через процесс штамповки на прессе. Это позволяет создать заготовку, которая затем подвергается обдиру и другим технологическим этапам. Важно, чтобы размеры и форма были максимально точными, так как это обеспечит правильное функционирование подшипника. Отклонение даже в один микрон при воздействии на шарик может сократить срок службы изделия или ухудшить плавность хода.
Прошедшие штамповку заготовки подвергаются термической обработке. Этот этап включает нагревание до определенной температуры, после чего следует контролируемое охлаждение. Такой процесс изменяет микроструктуру сырья, улучшая твердость и прочность металла, а также совершенствует физические свойства материала. Далее шарики проходят процесс шлифовки, который придает поверхности гладкость и непревзойденную точность. Технологии шлифовки включает ручные и автоматизированные методы в зависимости от уровня необходимой обработки. Это обязательно для уменьшения трения и обеспечения плавного вращения подшипника.
Изготовление шариков сопровождается строгим контролем и оценкой соответствия качества, что включает в себя измерение размеров, проверку твердости и гладкости поверхности. Только шарики, отвечающие строгим стандартам, отправляются на последующие этапы сборки подшипника.
Материалы
Как мы указывали выше, материал изготовления имеет важное значение при создании элементов качения. Так, например, хромистая сталь остается самым популярным материалом при изготовлении шариков. Ее три основных преимущества -прочность, твердость и коррозийная стойкость. Такие положительные качества продлевают срок службы изделия даже при высоких нагрузках в агрессивной среде. При этом твердость обеспечивает устойчивость к износу, а благодаря содержанию хрома повышается невосприимчивость к коррозии, что особенно важно в условиях повышенной влажности.
Современные подшипники часто используют в качестве элементов качения шарики из керамики. В виде таких соединений, как нитрид кремния и оксид алюминия. Изделия, на вооружении которых стоят сферы из керамических материалов, имеют следующие физические свойства:
- Легче шариков из стали и других металлов, что уменьшает нагрузку и улучшает эффективность подшипника.
- Высокая твердость, помогает повысить устойчивость к износу и продлить срок службы.
- Эффективная теплопроводность керамики позволяет лучше рассеивать тепло, что особенно важно, если тела качения задействованы в движении на большой скорости вращения.
- Устойчивы к электрохимической коррозии.
И наконец, шарики из титана совмещают в себе высокую прочность и низкий вес, что является критически важным преимуществом в условиях, где важны оба эти критерия. При этом низкая плотность материала улучшает технические свойства подшипника и снижает требования к смазке.
Сферы применения
Производители постоянно исследуют новые материалы и технологии, чтобы предложить решения, соответствующие всем вызовам современной промышленной индустрии. Так, в автомобилестроении шарики из керамики применяют в разных узлах, начиная от колесных систем и заканчивая двигателями и трансмиссией. Они могут выдержать серьезные нагрузки и обеспечить плавность хода, что является ключевым аспектом долговечности автомобилей. В аэрокосмической индустрии за удивительную стойкость к экстремальным условиям и точность используются элементы качения из титана. Изделия из износостойких сплавов широко применяются в энергетической индустрии, например, в турбинах и генераторах. Их устойчивость к постоянным вибрациям и экстремальным температурам делает их обязательным компонентами в производстве энергии. Сферы применения стальных шариков охватывают практически все области современной техники, демонстрируя их важное значение в обеспечении эффективности и надежности различных технологий.
Таблица размеров шариков подшипников
Научный форум dxdy
Привет!
Решаю следующую задачу из международной олимпиады школьников по математике.
Цитата:
Какое максимальное количество шаров диаметра 1 можно уложить в коробку размерами 10х10х1?
Сначала подумал, что в ответе 100. Но это неправильный ответ.
Потом, подумал, что, если крышка коробки не закрыта, а, вернее, ее просто
нет?И смысл задачи сводится к построению «горки» из шариков до последнего.
Порядок действий таков:
первый уровень — 10 на 10 шариков.
второй уровень — 9 на 9 шариков.
и так далее до.
9 уровень — 2 на 2 шарика.
10 уровень — 1 шарик.
Ответ получается -385 шариков.
Но он тоже неправильный.
В чем я ошибаюсь? Как решить эту задачу?
Re: Шары в коробке
06.07.2009, 00:52
а какой ответ считается правильным?
Re: Шары в коробке
06.07.2009, 01:06
Это ссылка на задачу.
Ответ не известен))
Еще пробовал ставить 11 на 11 шаров на второй уровень, но тоже не так((
Re: Шары в коробке
06.07.2009, 01:46
гм. но если размеры корочки заданы 3-х мерные, то все-таки наверное она типа с крышкой, т.е. помещать надо в эти размеры, иначе зачем указывать это 1?! с толку сбить? вряд ли, я думаю.
Если плотно класть шары по диагонали, получается 61, но это меньше 100.
— Пн июл 06, 2009 02:49:35 —
да, а их можно на кусочки резать? или ногами утаптывать?
— Пн июл 06, 2009 03:30:21 —
А, дошло! 105, верно?
Кладутся первые 10 шаров, следующие 9 в точности касаются с шарами из 1-го ряда, всего — 11 рядов, 6 — по 10, 5 — по 9, итого — 105, но я не знаю, как доказать, что нельзя больше.
Re: Шары в коробке
06.07.2009, 04:59
Да вот, походу, неправильно.
Я указал ссылку. на сайте проверяют ответ.
Уже кучу вариантов перебробовал, но все равно не то.
Не знаю, может ошибка в проверочной системе.
Мой ответ пока что — 385. Делаем пирамиду до последнего шарика.
Буду благодарен человеку, который сможет решить и доказать ,что его ответ единственно правилен))
Re: Шары в коробке
06.07.2009, 07:37
| Заслуженный участник |
Как минимум 105 (если укладывать шары шестиугольной мозаикой; получится 11 рядов по 9-10 шаров в каждом). Но за последним рядом остается еще достаточно места, чтобы, перетасовав шары последнего ряда, «втиснуть» туда еще несколько шаров (сколько — не знаю).
Re: Шары в коробке
06.07.2009, 08:14
| Заслуженный участник |
Последний раз редактировалось venco 06.07.2009, 08:51, всего редактировалось 1 раз.
Высота не зря задана.
В прямоугольник 8х10 вмещаются 5 рядов по 10 и между ними 4 ряда по 9 в гексагональной упаковке. Плюс ещё 2 ряда по 10.
Всего — 106.
Re: Шары в коробке
06.07.2009, 08:45
| Заслуженный участник |
EtCetera в сообщении #226763 писал(а):
Как минимум 105 (если укладывать шары шестиугольной мозаикой; получится 11 рядов по 9-10 шаров в каждом). Но за последним рядом остается еще достаточно места, чтобы, перетасовав шары последнего ряда, «втиснуть» туда еще несколько шаров (сколько — не знаю).
Как минимум 106: запаса хватит, чтобы один ряд по 9 превратить в по 10, а вот дальше ресурсов вроде не видать.
Re: Шары в коробке
06.07.2009, 10:18
Рассмотрим сечение коробки на высоте 
.5$» />. Каждый шар там дает круг диаметра 1. Поэтому из соображений площади получим 