Comments 17
При наличии в ЯП из коробки комплексных чисел, перебирать соседние 4 клетки можно было бы с помощью умножения на i (мнимую единицу). Или на -i, чтобы в другую сторону.
С учетом надвигающегося Advent of Code это и правда может быть полезно. Но иногда там бывают задачки, где интересны соседи не на плоскости, а в трех (а однажды было и четырех) измерениях. В этом случае если нужны совсем все соседи, то можно оставить решение с "начать от центра", но когда нужны только ортогональные соседи (т.е. манхеттенская дистанция 1), то формулами уже не очень получается.
За напоминание спасибо :)
Насчет "не очень получается" - скорее правильно сказать "не приходит сразу в голову". Интересно отметить что "диагональных" а не "ортогональных" соседей в пространстве любой размерности перечислить легко. Подумаем на досуге :)
Для обхода всех соседей можно использовать такой код:
r = (-1, 0, 1)
for dx in r:
for dy in r:
if dx or dy:
paint_it_black(x + dx, y + dy)Можно сделать код лаконичнее (убрав несколько уровней вложенности):
r = (-1, 0, 1)
neighbors = [
(dx, dy)
for dx in r
for dy in r
if dx or dy
]
for dx, dy in neighbors:
paint_it_black(x + dx, y + dy)Ну и, как мне кажется, самый изящный способ, который можно использовать для любого количества измерений, следующий:
import itertools
dims = 2
neighbors = [
n
for n in itertools.product((-1, 0, 1), repeat=dims)
if any(n)
]
for dx, dy in neighbors:
paint_it_black(x + dx, y + dy)P.S. во всех трех вариантах можно убрать if ("if dx or dy" и "if any(n)")и тогда будут не только соседи, но и точка (x, y).
neighbors = [n for n in itertools.product((-1, 0, 1), repeat=dims)]
# or
neighbors = list(itertools.product((-1, 0, 1), repeat=dims))P.P.S. Для ортогональных соседей ((-1, 0), (0, -1), (0, 1), (1, 0)) можно "if any(n)" заменить на "if sum(abs(x) for x in n) == 1" или "sum(map(abs, n)) == 1" (кому что больше нравится), а "if dx or dy" заменить, например, на "if dx + dy in (-1, 1)" или "if abs(dx + dy) == 1":
neighbors = [
n
for n in itertools.product((-1, 0, 1), repeat=dims)
if sum(map(abs, n)) == 1
]P.P.P.S. Для диагональных соседей ((-1, -1), (-1, 1), (1, -1) и (1, 1)) можно в коде выше заменить (-1, 0, 1) на (-1, 1) и убрать if, так как он будет не нужен.
neighbors = [n for n in itertools.product((-1, 1), repeat=dims)]
# or
neighbors = list(itertools.product((-1, 1), repeat=dims))
Можно без делений и взятия остатков, на битовой арифметике, например так:
for i in range(8):
... paint_it_black(x + ((148>>i)&1) - ((41>>i)&1) , y + ((224>>i)&1) - ((7>>i)&1)))
Можно и в одно число закодировать вместо двух :)
Правда как и с массивами, и с косинусами у этого подхода некоторый недостаток - со стороны довольно трудно понять что это за ересь автор написал.
Есть однако и одно важное преимущество - можно задать вообще любой порядок обхода любого количества соседей в пространстве любой размерности (главное чтобы бит хватило).
Но правда это именно не формула а "кодирование" порядка.
Правда как и с массивами, и с косинусами у этого подхода некоторый недостаток - со стороны довольно трудно понять что это за ересь автор написал.
Вот уж не знаю, почему на хабре это кажется дичью (см. коммент ниже), но когда задача формулируется так, что нужно найти координаты точек на окружности, синус и косинус - это первое что приходит в голову.
А таблица смещений - это просто затабулированные значения синусов и косинусов, чтобы считать быстрее. Вообще никто не заставляет использовать значение угла в радианах или градусах, в примере с 8 соседями, значение угла - целое число от 0 до 7.
Использование синусов-косинусов и полярных координат кажется дичью и экзотикой, но есть на Хабре отличная статья "Рисуем картинки с помощью кривой Гильберта". Всё хорошо, но медленно работает. Глянул в код, а там повороты на 90 градусов вычисляются через тригонометрические функции.
Небольшая хитрость для 8 соседей: можно итерировать i от 5 до 12.
Было бы интересно дополнить примерами, когда точка находится на границе (нет соседей с одной стороны) или в углу (нет соседей с двух стороны).
а как вы это хотите задавать? ну вот в функцию get_neighbors передавать например какие-то дополнительные параметры чтобы показать что точка в углу или на краю? выглядит не очень хорошо
да и необязательно края вообще есть (та же игра Жизнь в идеале про бесконечное поле)
на мой взгляд такие проверки обычно "снаружи" происходят - мы координаты сгенерировали - а снаружи можно или доп.условиями, или дополнительными клетками в матрице определить что часть координат невалидна
Можно добавить проверку в духе
for dx, dy in neigbours:
if (xx := x + dx) in range(w) and (yy := y + dy) in range(h):
paint_it_black(xx, yy)где w - ширина области, h - высота
можно но по-хорошему этот код внутри paint_it_black должен быть (за границей не рисуем)
он просто к "перечислению" не относится - вы не можете сказать "не глядя" сколько точек попадает в область - или например функция get_neighbor перестаёт работать понятно (какие точки теперь становятся первой, второй, последней)
т.е. я не говорю что это плохо, просто это уже про другое :)
Перебор Соседних Клеток — забавные формулы