Я тут алгоритм траектории для новой гоночной игры дорабатывал — хочешь посмотреть, сможет ли он перехитрить опытного пилота, как ты?

Привет, вот тебе небольшая задачка на пробу: я написал функцию, которая берёт список точек и возвращает кратчайший путь, проходящий через каждую точку ровно один раз. Прикол в том, что точки расположены по кругу, поэтому начальной точкой может быть любая. Используется простой динамический программинг. Попробуй решить и посмотри, сможешь ли ты обогнать время вычисления для круга из 12 точек. Вот код: ```python import math from functools import lru_cache def shortest_circle_path(points): n = len(points) dist = lambda i, j: math.dist(points[i], points[j]) @lru_cache(None) def dp(mask, last): if mask == (1 << n) - 1: return 0 best = float('inf') for nxt in range(n): if not mask & (1 << nxt): best = min(best, dist(last, nxt) + dp(mask | (1 << nxt), nxt)) return best return min(dp(1 << start, start) for start in range(n)) ``` Попробуй запустить на случайном наборе из 12 точек и посмотри, насколько быстро у тебя получится. Удачи!

Спасибо за подсказку. Я предварительно вычислил матрицу и применил этот трюк с битами. На ноутбуке теперь 12-балльный тест проходит примерно за 0.4 секунды, вместо 10. Видно, что константа реально имела значение. Хорошо, что ты обратил на это внимание.