Если вы, как и я, устрашились фундаментального двухчастного трактата коллеги@Orazbek_B, возможно вас заинтересует это крохотное эссе. Сперва – код на питоне:
n, m = 5, 8 # высота и ширина матрицы
def draw(title, f):
print(f"\n{title:-^{m * 3 - 1}}")
res = [""] * (n * m)
for i, j in enumerate(sorted(range(n * m), key=lambda i: f(i // m, i % m))):
res[j] = f"{i:>02}"
for i in range(0, n * m, m):
print(*res[i:i + m])
draw("horizontal", lambda y, x: (y, -x if y % 2 else x))
draw("diagonal" , lambda y, x: (y + x, x if (y + x) % 2 else -x))Результатом выполнения этого кода будут две аккуратные змейки:
------horizontal-------
00 01 02 03 04 05 06 07
15 14 13 12 11 10 09 08
16 17 18 19 20 21 22 23
31 30 29 28 27 26 25 24
32 33 34 35 36 37 38 39
-------diagonal--------
00 02 03 09 10 19 20 29
01 04 08 11 18 21 28 30
05 07 12 17 22 27 31 36
06 13 16 23 26 32 35 37
14 15 24 25 33 34 38 39
Наши матрицы не злобные, они мягкие и пушистые. Бонус: они не обязательно квадратные. Можно отрисовать и спиральку, хоть прямоугольную, хоть ромбическую, хоть округлую, можно залить не прямоугольник, а фигуру произвольной формы – было бы желание.
Извинити, что так коротенько: о чём говорить, когда говорить не о чем ????
Комментарии (7)
wataru
20.06.2022 11:43+4Это совсем не то. В оригинальных статьях цель была придумать формулы для подсчета одной клетки матрицы независимо от других за константное время. У вас же заполняется вся матрица итеративно. Хотя циклы хитро спрятаны засчет ввода новой системы координат и перенумерации клеток.
И вообще ваше решение работает за O(nm log(nm)).
Так-то чисто итеративное решение с двумя циклами будет даже покороче вашего. Правда там не удастся переиспользовать код для разных змеек.
longclaps Автор
21.06.2022 12:09-1Не стоит приписывать мне намерения, которых я не выказывал. Я не собирался тягаться с автором трактата в решении придуманой им же задачи, а пожелай я этого – оставил бы комент к его посту с посылом “вот то же самое, только лучше”. Но нет, я создал отдельный пост и назвал его “змейкой здорового человека”.
Авторская задача педантская и заведомо разрешимая, техническая. Я бы заниматься таким по своей воле не стал, разве что по нужде.
А вот для задачи заполнить-отрисовать матрицу я придумал решение с идеей. Да, прямолинейное О(1)*N заведомо её бьёт (там, где оно достижимо) – но она плодотворнее тупого бухгалтерского решения, она естественным образом обобщается, вот я ею и поделился.
Смотрите: я сортирую клетки, приписывая им относительный вес в сравнении с соседями, не парясь о соответствии веса клетки и вписываемого в неё в итоге числа. Я не запариваюсь в поиске границ и точек поворота – те моменты, где ошибиться особенно легко. Задача упрощается до уровня неопытного новичка.
Но не для вашего понимания. У вас взгляд замылился, вы смотрите на код и видите в нём NlogN, а идею не замечаете.
Прицепом обращусь к@amarao– такова уж моя карма. Спасибо что заглянули, спасибо за контрпример, спасибо за напутствие. Числа ваши мне очень понравились, где такие берёте? Пешите ещо, здесь без вас грустно.
wataru
21.06.2022 14:05А зачем тогда ссылаться на "фундаментальный двухчастный трактат"?
но она плодотворнее тупого бухгалтерского решения, она естественным образом обобщается, вот я ею и поделился.
Если бы вы обозвали свою статью "Прикольный метод обобщения некоторых змеек", претензий никаких бы не было.
А так уже на спираль вы ваш метод не обобщите.
Прикольно, но практического применения нет. Медленнее тупого решения, да и длинее. Если оба метода змейки втупую написать — они будут суммарно занимать чуть ли не меньше вашего гениального решения. И при этом будут на порядки читабельнее.
longclaps Автор
22.06.2022 12:20from 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)Покончим с этим разговором.
amarao
20.06.2022 15:57+2sorted(range(n * m))полностью уничтожает исходную идею для доступа за o(1) к ячейке.
Собственно, вот вам контр-пример. Предположим, у вас есть массив
2**32x2**32, вам нужно вывести значение в позиции 42424242, 42424242.Удачи сортировать.
Chuvi
А можно для тех, кто не изучал Питон объяснить, что происходит в коде?
longclaps Автор
Вот это самое и происходит: для каждой ячейки вычисляем ключ, двузначный кортеж, для первой змейки первое число кортежа - номер строки, y (вы там заметили y? так это - номер строки!), второе число - номер столбца, взятый с положительным знаком для четных строк и с отрицательным - для нечетных. Кортежи можно сравнивать, как сравнивают строки, т.е. посимвольно. Список сравнимых значений можно отсортировать. В отсортированные ячейки можно вписать числа по возрастанию.