Comments 7
А можно для тех, кто не изучал Питон объяснить, что происходит в коде?
В алгоритме ничего сложного: каждой ячейке ставим в соответствие такой ключ, чтобы, будучи отсортированы по ключам, ячейки заполнялись бы в нужном порядке.
Вот это самое и происходит: для каждой ячейки вычисляем ключ, двузначный кортеж, для первой змейки первое число кортежа - номер строки, y (вы там заметили y? так это - номер строки!), второе число - номер столбца, взятый с положительным знаком для четных строк и с отрицательным - для нечетных. Кортежи можно сравнивать, как сравнивают строки, т.е. посимвольно. Список сравнимых значений можно отсортировать. В отсортированные ячейки можно вписать числа по возрастанию.
Это совсем не то. В оригинальных статьях цель была придумать формулы для подсчета одной клетки матрицы независимо от других за константное время. У вас же заполняется вся матрица итеративно. Хотя циклы хитро спрятаны засчет ввода новой системы координат и перенумерации клеток.
И вообще ваше решение работает за O(nm log(nm)).
Так-то чисто итеративное решение с двумя циклами будет даже покороче вашего. Правда там не удастся переиспользовать код для разных змеек.
Не стоит приписывать мне намерения, которых я не выказывал. Я не собирался тягаться с автором трактата в решении придуманой им же задачи, а пожелай я этого – оставил бы комент к его посту с посылом “вот то же самое, только лучше”. Но нет, я создал отдельный пост и назвал его “змейкой здорового человека”.
Авторская задача педантская и заведомо разрешимая, техническая. Я бы заниматься таким по своей воле не стал, разве что по нужде.
А вот для задачи заполнить-отрисовать матрицу я придумал решение с идеей. Да, прямолинейное О(1)*N заведомо её бьёт (там, где оно достижимо) – но она плодотворнее тупого бухгалтерского решения, она естественным образом обобщается, вот я ею и поделился.
Смотрите: я сортирую клетки, приписывая им относительный вес в сравнении с соседями, не парясь о соответствии веса клетки и вписываемого в неё в итоге числа. Я не запариваюсь в поиске границ и точек поворота – те моменты, где ошибиться особенно легко. Задача упрощается до уровня неопытного новичка.
Но не для вашего понимания. У вас взгляд замылился, вы смотрите на код и видите в нём NlogN, а идею не замечаете.
Прицепом обращусь к@amarao– такова уж моя карма. Спасибо что заглянули, спасибо за контрпример, спасибо за напутствие. Числа ваши мне очень понравились, где такие берёте? Пешите ещо, здесь без вас грустно.
А зачем тогда ссылаться на "фундаментальный двухчастный трактат"?
но она плодотворнее тупого бухгалтерского решения, она естественным образом обобщается, вот я ею и поделился.
Если бы вы обозвали свою статью "Прикольный метод обобщения некоторых змеек", претензий никаких бы не было.
А так уже на спираль вы ваш метод не обобщите.
Прикольно, но практического применения нет. Медленнее тупого решения, да и длинее. Если оба метода змейки втупую написать — они будут суммарно занимать чуть ли не меньше вашего гениального решения. И при этом будут на порядки читабельнее.
from math import atan2
def draw(title, n, m, f):
y0, x0 = (n - 1) / 2, (m - 1) / 2 # нужен центр
print(f"\n{title:-^{m * 3 - 1}}")
res = [0] * (n * m)
for i, j in enumerate(sorted(range(n * m),
key=lambda i: f(i // m - y0, i % m - x0))):
res[j] = f"{i:>02}"
for i in range(0, n * m, m):
print(*res[i:i + m])
f = lambda y, x: (max(abs(y), abs(x)), atan2(x, y))
# высота и ширина матрицы должны быть одной четности,
# или центр нужно сдвинуть - для изотропности
draw("spiral", 4, 6, f)
draw("spiral", 5, 5, f)Покончим с этим разговором.
sorted(range(n * m))
полностью уничтожает исходную идею для доступа за o(1) к ячейке.
Собственно, вот вам контр-пример. Предположим, у вас есть массив 2**32 x 2**32, вам нужно вывести значение в позиции 42424242, 42424242.
Удачи сортировать.
Змейка здорового человека