На изображении выше показана гексагональная сетка из шестиугольников. Каждой ячейке в сетке присваивается индекс, начиная с центра и вращаясь против часовой стрелки, как показано. Обратите внимание, что сетка будет продолжаться бесконечно - изображение выше - просто первый раздел. Следующий шестиугольник будет смежным с 60 и 37.
Ваша задача - определить, являются ли две заданные ячейки в этой сетке соседними.
Напишите программу или функцию, которая с учетом двух индексов ячеек печатает / возвращает истинное значение, если две ячейки смежны, и ложное значение, если нет.
Если это не ограничено практическими соображениями, ваш код теоретически должен работать для входных данных любого размера.
Правдивые тесты:
0, 1
7, 18
8, 22
24, 45
40, 64
64, 65
Контрольные примеры Falsey:
6, 57
29, 90
21, 38
38, 60
40, 63
41, 39
40, 40
Это код-гольф, поэтому выигрывает самый короткий ответ в байтах. Пояснения, даже для неэзотерических языков, приветствуются.
источник
MATL ,
4745444341 байтПопробуйте онлайн! Или проверьте все тестовые случаи .
В качестве бонуса код генерирует гексагональную спираль, которая отслеживает положения центров ячеек, что можно увидеть графически в MATL Online , изменив последнюю часть кода.
объяснение
Общая идея Код сначала строит достаточно большую гексагональную спираль с шагом в единицу. Спираль определяется как вектор комплексных чисел, представляющих положения центров клеток. Индексирование в этот вектор с помощью входных чисел и вычисление абсолютной разницы дает расстояние между двумя указанными ячейками. Ячейки являются смежными, если и только если результат равен 1. Однако из-за неточностей с плавающей запятой, округление необходимо перед сравнением с 1.
Построение спирали Спираль будет иметь количество «слоев», равное сумме двух входов. Это (намного) больше, чем необходимо, и гарантирует, что входные ячейки будут присутствовать в спирали.
Чтобы построить спираль, сначала вычисляется комплексное число j 2/3 (где j - мнимая единица). Повышение этого показателя до показателей 1–6 дает базовый набор смещений, так что следование за этими смещениями по порядку будет отслеживать шестиугольник. Этот шестиугольник будет образовывать самый внутренний слой спирали, за исключением того, что он будет «закрыт». На самом деле, мы хотим, чтобы этот шестиугольник «рос» на последнем шаге, а затем мы прослеживаем больший шестиугольник с вдвое большим количеством точек (выровненных в группы по две), чтобы сформировать следующий слой спирали; см. иллюстрацию здесь . Следующий слой будет иметь в три раза больше очков, чем первый (в группах по три); смотрите здесь .
Для этого в качестве «растущего» шага выбрано пятое смещение от базового набора (которое указывает в юго-восточном направлении). Уровень k начинается с этого шага, за которым следуют первые пять основных шагов, повторяемых k раз, а затем шестой шаг (в восточном направлении), повторяемый k -1 раз. Надеюсь, это станет яснее, если взглянуть на две цифры, связанные выше.
Результирующий вектор, включая все слои, представляет собой сложные смещения, которые будут отслеживать спираль. Накопленная сумма дает фактические координаты центров клеток.
Наконец, начальная ячейка, расположенная в 0, прикреплена к концу этого вектора. Это связано с тем, что MATL использует модульное индексирование на основе 1, а индекс 0 ссылается на эту последнюю запись массива.
Проверка на смежность Две ячейки, заданные входными числами, выбираются, их координаты вычитаются, а абсолютное значение округляется и сравнивается с 1.
Код комментария
источник
05AB1E (наследие) ,
302927 байтовПопробуйте онлайн!
Объяснение кода:
Объяснение математики:
Я "впустую" около 5 часов, делая этот гольф. Короче говоря, я начал делать двухмерный график входов и рисовал
X
там, где они были смежны друг с другом. Тогда я нашел образец. Я искал это на OEIS и бинго! Я нашел эту последовательность и использовал формулу, приведенную на сайте.источник
C (gcc) ,
175173 байтаСпасибо Питеру Тейлору за обнаружение ошибки.
Благодаря потолку кошки за -2 байта. Этот оператор продолжает оставаться моей главной слепой точкой.
Попробуйте онлайн!
Этот подход ориентирован на поиск строки и столбца двух ячеек и сравнение их; любые соседи не могут иметь соответствующие координаты, отличающиеся более чем на 1. Перемещаясь от центра наружу, мы видим, что каждый слой имеет на 6 ячеек больше, чем предыдущий. Это означает, что самый высокий «индекс» в каждом слое L находится в форме 6 * (L * (L - 1) * (L - 2) ...), или C = 6 * (L 2 + L) / 2 где C - это «глобальный» номер ячейки. Перемешивая вещи, мы получаем L 2 + L - C / 3 = 0, что дает воспоминания о старшей школе по математике. Отсюда получаем формулу ceil (sqrt (1/4 + C / 3) + 0,5). Подключив к нему глобальный индекс ячейки, мы получим, в каком слое находится ячейка.
Поскольку первая ячейка в каждом слое, естественно, на одну высшую, чем самая высокая в предыдущем слое, мы находим L start = (6 * (L - 1) 2 + (L - 1)) / 2, что упрощается до 3 * (L 2 - л). Отсюда получаем индекс слоя L index = C - L start .
Далее мы видим, что каждый слой состоит из шести секций, каждая длиной L. Начиная с северо-востока и против часовой стрелки, мы видим, что для первых двух секций (1 <= L index <= 2 * L) мы получаем столбец из L - L индекса . В следующем разделе L * 2 <L index <= L * 3 все ячейки имеют общий столбец -L. Два следующих раздела - это L * 3 <L index <= L * 5 с их столбцами в соответствии с L index - L * 4. И, наконец, шестой раздел имеет все ячейки в столбце L. Мы можем сдвинуть верхние границы на один шаг вперед сохранить несколько байтов в коде.
Так что же насчет строк? Чтобы повторно использовать код, мы поворачиваем сетку так, чтобы ячейка 44 находилась прямо вверх. Затем мы запускаем ту же логику, что и для столбцов, но на этот раз называем результаты «строками». Конечно, вместо того, чтобы фактически поворачивать сетку, мы просто обходим ее на 1/6 круга.
источник
Python 3, 150 байт
Мое решение в основном следует той же мысли, что и Луис Мендо выше. Если написано более читабельно, код довольно понятен:
h
делает следующее:i
это номер звонка.l
представляет собой объединение 6 списков len (i), умноженных на вектор шага, где вектор шага равен 1j ** (2/3) до некоторой степени. Диапазон начинается не с 0, а с 4, что вызывает вращение всей сетки. Это позволяет мне сделать:l[0]+=1
в строке 6, которая является шагом от одного кольца к следующему.L+=l
объединяет полный список и список звонков.h(0,0)
или h (0,1) позаботился неявно, потому что сумма пустого списка равна нулю. Если бы я мог быть уверенa<b
, что аргументы будут приходить в возрастающем порядке, я мог бы сбрить еще 14 байтов, заменив ихL[min(a,b):max(a,b)]
наL[a:b]
, но, увы!PS: я не знал, что это был такой старый вызов, он появился на вершине несколько дней назад, и с тех пор продолжал давить на меня :)
источник
Mathematica,
111105104 байтаОбъяснение:
r=Floor[(1+Sqrt[(4#-1)/3])/2]&
определяет функцию,r
которая принимает входные данные#
и вычисляет расстояние (в количестве ячеек) до ячейки 0. Это делается путем использования шаблона в последних ячейках каждого расстояния / кольца: 0 = 3 (0 ^ 2 + 0), 6 = 3 (1 ^ 2 + 1), 18 = 3 (2 ^ 2 + 2), 36 = 3 (3 ^ 2 + 3), ... и инвертируя формулу для этого шаблона. Обратите внимание, что для ячейки 0 она фактически принимает значение (1/2) + i * (sqrt (3) / 6), которое вычисляется по компонентам, чтобы получить 0 + 0 * i = 0.С
r
определяется,r@#
является кольцо для ячейки#
(внутри определения другой функции).#+3r@#-3(r@#)^2&
не появляется в коде точно, но он берет номер ячейки и вычитает наибольшее число ячеек в следующем внутреннем кольце, так что это дает ответ на вопрос "какая ячейка текущего кольца это?" Например, ячейка 9 - это третья ячейка кольца 2, поэтомуr[9]
выведите 2 и#+3r@#-3(r@#)^2&[9]
выведите 3.Что мы можем сделать с помощью функции выше, так это использовать ее для нахождения полярного угла , угла против часовой стрелки от луча «ячейка 0, ячейка 17, ячейка 58» к рассматриваемой ячейке. Последняя ячейка каждого кольца всегда находится под углом Pi / 6, и мы обходим кольцо с шагом Pi / (3 * ring_number). Итак, теоретически нам нужно вычислить что-то вроде Pi / 6 + (which_cell_of_the_current_ring) * Pi / (3 * ring_number). Однако поворот изображения ни на что не влияет, поэтому мы можем отбросить часть Pi / 6 (чтобы сохранить 6 байт). Объединяя это с предыдущей формулой и упрощая, мы получаем
Pi(#/(3r@#)+1-r@#)&
К сожалению, это не определено для ячейки 0, так как ее номер звонка равен 0, поэтому нам нужно обойти это. Естественное решение было бы что-то вроде
t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&
. Но так как нас не волнует угол для ячейки 0 и посколькуr@#
он повторяется, мы можем сохранить здесь байт с помощьюt=Limit[Pi(#/(3x)+1-x),x->r@#]&
Теперь, когда у нас есть номер кольца и угол, мы можем найти положение ячейки (центра), чтобы мы могли проверить смежность. Поиск фактической позиции раздражает, потому что кольца гексагональные, но мы можем просто притвориться, что кольца являются идеальными кругами, так что мы рассматриваем число колец как расстояние до центра ячейки 0. Это не будет проблемой, так как приближение довольно близко. Используя полярную форму комплексного числа , мы можем представить это приблизительное положение в комплексной плоскости с помощью простой функции:
p = r@#*Exp[I*t@#] &;
Расстояние между двумя комплексными числами на комплексной плоскости определяется абсолютной величиной их разности, и затем мы можем округлить результат, чтобы учесть любые ошибки из аппроксимации, и проверить, равно ли это 1. Функция, которая в конечном итоге У этой работы нет имени, но есть
Round@Abs[p@#-p@#2]==1&
.Вы можете попробовать его онлайн в песочнице Wolfram Cloud , вставив код, подобный приведенному ниже, и щелкнув Gear -> «Оценить ячейку» или нажав Shift + Enter или цифровую клавишу Enter:
Или для всех тестовых случаев:
источник