Змейка здорового человека

Если вы, как и я, устрашились фундаментального двухчастного трактата коллеги@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


В алгоритме ничего сложного: каждой его ячейке ставим в соответствие такой ключ, чтобы, будучи отсортированы по ключам, ячейки заполнялись бы в нужном порядке.

Наши матрицы не злобные, они мягкие и пушистые. Бонус: они не обязательно квадратные. Можно отрисовать и спиральку, хоть прямоугольную, хоть ромбическую, хоть округлую, можно залить не прямоугольник, а фигуру произвольной формы – было бы желание.

Извинити, что так коротенько: о чём говорить, когда говорить не о чем ?

@longclaps
20.06.2022 07:44 UTC
Первоисточник

Комментарии

@Chuvi
20.06.2022 07:50 UTC
+2

А можно для тех, кто не изучал Питон объяснить, что происходит в коде?

@longclaps
20.06.2022 08:12 UTC
0

В алгоритме ничего сложного: каждой ячейке ставим в соответствие такой ключ, чтобы, будучи отсортированы по ключам, ячейки заполнялись бы в нужном порядке.

Вот это самое и происходит: для каждой ячейки вычисляем ключ, двузначный кортеж, для первой змейки первое число кортежа - номер строки, y (вы там заметили y? так это - номер строки!), второе число - номер столбца, взятый с положительным знаком для четных строк и с отрицательным - для нечетных. Кортежи можно сравнивать, как сравнивают строки, т.е. посимвольно. Список сравнимых значений можно отсортировать. В отсортированные ячейки можно вписать числа по возрастанию.

@wataru
20.06.2022 08:43 UTC
+5

Это совсем не то. В оригинальных статьях цель была придумать формулы для подсчета одной клетки матрицы независимо от других за константное время. У вас же заполняется вся матрица итеративно. Хотя циклы хитро спрятаны засчет ввода новой системы координат и перенумерации клеток.


И вообще ваше решение работает за O(nm log(nm)).


Так-то чисто итеративное решение с двумя циклами будет даже покороче вашего. Правда там не удастся переиспользовать код для разных змеек.

@longclaps
21.06.2022 09:09 UTC
-2

Не стоит приписывать мне намерения, которых я не выказывал. Я не собирался тягаться с автором трактата в решении придуманой им же задачи, а пожелай я этого – оставил бы комент к его посту с посылом “вот то же самое, только лучше”. Но нет, я создал отдельный пост и назвал его “змейкой здорового человека”.

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

А вот для задачи заполнить-отрисовать матрицу я придумал решение с идеей. Да, прямолинейное О(1)*N заведомо её бьёт (там, где оно достижимо) – но она плодотворнее тупого бухгалтерского решения, она естественным образом обобщается, вот я ею и поделился.

Смотрите: я сортирую клетки, приписывая им относительный вес в сравнении с соседями, не парясь о соответствии веса клетки и вписываемого в неё в итоге числа. Я не запариваюсь в поиске границ и точек поворота – те моменты, где ошибиться особенно легко. Задача упрощается до уровня неопытного новичка.

Но не для вашего понимания. У вас взгляд замылился, вы смотрите на код и видите в нём NlogN, а идею не замечаете.

Прицепом обращусь к@amarao– такова уж моя карма. Спасибо что заглянули, спасибо за контрпример, спасибо за напутствие. Числа ваши мне очень понравились, где такие берёте? Пешите ещо, здесь без вас грустно.

21.06.2022 11:05 UTC
0

А зачем тогда ссылаться на "фундаментальный двухчастный трактат"?


но она плодотворнее тупого бухгалтерского решения, она естественным образом обобщается, вот я ею и поделился.

Если бы вы обозвали свою статью "Прикольный метод обобщения некоторых змеек", претензий никаких бы не было.


А так уже на спираль вы ваш метод не обобщите.


Прикольно, но практического применения нет. Медленнее тупого решения, да и длинее. Если оба метода змейки втупую написать — они будут суммарно занимать чуть ли не меньше вашего гениального решения. И при этом будут на порядки читабельнее.

22.06.2022 09:20 UTC
0
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)

Покончим с этим разговором.

@amarao
20.06.2022 12:57 UTC
+2

sorted(range(n * m))

полностью уничтожает исходную идею для доступа за o(1) к ячейке.

Собственно, вот вам контр-пример. Предположим, у вас есть массив 2**32 x 2**32, вам нужно вывести значение в позиции 42424242, 42424242.

Удачи сортировать.