Манхэттен расстояние на регулярной сетке число ортогональных шагов нужно предпринять , чтобы достичь одну клетку от другой. Ортогональные шаги - это те, которые проходят через края ячеек сетки (в отличие от углов, которые дали бы нам расстояние Чебышева ).
Мы можем определить аналогичное расстояние на других сетках, например на треугольной сетке. Мы можем обратиться к отдельным ячейкам в сетке с помощью следующей схемы индексации, где каждая ячейка содержит x,y
пару:
____________________________________...
/\ /\ /\ /\ /\
/ \ 1,0/ \ 3,0/ \ 5,0/ \ 7,0/ \
/ 0,0\ / 2,0\ / 4,0\ / 6,0\ / 8,0\
/______\/______\/______\/______\/______\...
\ /\ /\ /\ /\ /
\ 0,1/ \ 2,1/ \ 4,1/ \ 6,1/ \ 8,1/
\ / 1,1\ / 3,1\ / 5,1\ / 7,1\ /
\/______\/______\/______\/______\/___...
/\ /\ /\ /\ /\
/ \ 1,2/ \ 3,2/ \ 5,2/ \ 7,2/ \
/ 0,2\ / 2,2\ / 4,2\ / 6,2\ / 8,2\
/______\/______\/______\/______\/______\...
\ /\ /\ /\ /\ /
\ 0,3/ \ 2,3/ \ 4,3/ \ 6,3/ \ 8,3/
\ / 1,3\ / 3,3\ / 5,3\ / 7,3\ /
\/______\/______\/______\/______\/___...
/\ /\ /\ /\ /\
. . . . . . . . . .
. . . . . . . . . .
Теперь Манхэттенское расстояние на этой сетке опять равно минимальному количеству шагов по краям, чтобы добраться из одной ячейки в другую. Таким образом , вы можете перейти от 3,1
к 2,1
, 4,1
или 3,2
, а не какой - либо другой треугольник, так как те будут пересекать точки , а не края.
Так , например, расстояние от 2,1
до 5,2
это 4
. Кратчайший путь, как правило, не уникален, но один из способов сделать расстояние за 4 шага:
2,1 --> 3,1 --> 3,2 --> 4,2 --> 5,2
Соревнование
Учитывая две пары координат и из приведенной выше схемы адресации, верните манхэттенское расстояние между ними.x1,y1
x2,y2
Вы можете предположить, что все четыре входа являются неотрицательными целыми числами, каждое из которых меньше 128. Вы можете взять их в любом порядке и произвольно сгруппировать (четыре отдельных аргумента, список из четырех целых чисел, две пары целых чисел, матрица 2x2, .. .).
Вы можете написать программу или функцию и использовать любой из стандартных методов получения ввода и предоставления вывода.
Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.
Это код-гольф , поэтому самый короткий действительный ответ - измеренный в байтах - выигрывает.
Тестовые случаи
Каждый тестовый пример дается как .x1,y1 x2,y2 => result
1,2 1,2 => 0
0,1 1,1 => 1
1,0 1,1 => 3
2,1 5,2 => 4
0,0 0,127 => 253
0,0 127,0 => 127
0,0 127,127 => 254
0,127 127,0 => 254
0,127 127,127 => 127
127,0 127,127 => 255
75,7 69,2 => 11
47,58 36,79 => 42
77,9 111,23 => 48
123,100 111,60 => 80
120,23 55,41 => 83
28,20 91,68 => 111
85,107 69,46 => 123
16,25 100,100 => 159
62,85 22,5 => 160
92,26 59,113 => 174
62,22 35,125 => 206
источник
(a,b,x,y)->c(a,b,x,y,0)
(вызывая разделенный методc
с четырьмя аргументами и в0
качестве пятого аргумента) к моему ответу.Ответы:
JavaScript (ES6),
8478 байтСохранено 6 байтов благодаря Нейлу
Контрольные примеры
Показать фрагмент кода
Исходный рекурсивный раствор,
1008881Сохранено 12 байтов благодаря ETHproductions
Сохранено 7 байтов благодаря Нейлу
Как это работает
Хотя это по существу относится к текущей версии, следующее объяснение более конкретно относится к начальной версии:
Переход от (x0, y) к (x1, y) тривиален, потому что мы можем пройти через боковые ребра от исходного треугольника до целевого. Манхэттенское расстояние в этом случае составляет | х0 - х1 | ,
Хитрая часть - вертикальные шаги. Чтобы перейти от строки y0 к строке y1 , мы должны принять во внимание эти два параметра:
Ориентация треугольника определяется соотношением x + y :
Мы можем пойти вниз от треугольника, направленного вверх (полезно, когда y0 <y1 ), и вверх от треугольника, направленного вниз (полезно, когда y0> y1 ).
Комбинируя ориентацию треугольника со сравнением между y0 и y1 , мы получаем формулу x + y0 + (y0> y1? 1: 0) , результат которой равен четности, если мы можем идти в нужном направлении, и нечетным, если нет.
Если мы не можем напрямую добраться до следующей строки, нам сначала нужно получить правильное выравнивание, обновив x :
Контрольные примеры
Показать фрагмент кода
источник
n
вообще пропустить переменную и просто добавить 1 к результату каждой итерации? ( Я думаю, 90 символов )&
означает, что вы можете сделать,a+b+(b>d)&1
чтобы сохранить 2 байтаf=(a,b,c,d,e=b==d|a+b+(b>d)&1)=>a-c|b-d&&f(e?a+1-2*(a>c):a,e?b:b+1-2*(b>d),c,d)+1
Python 2, 74 байта
источник
**(x^y^(Y>=y))
?Пакетный, 99 байтов
Пояснение: Движение только по горизонтали просто принимает абсолютную разницу по оси X. Для достаточно большого x вертикальное движение требует только одного дополнительного шага на абсолютную разницу y-координат, но для малого x требуется четыре дополнительных шага на две разности y-координат плюс один или три шага для нечетной разности. Это рассчитывается как два шага на разницу плюс поправочный коэффициент. В результате получается больший из исправленных двух шагов и сумма абсолютных разностей, хотя сам он вычисляется как большее из исправленной абсолютной разности по координате y и абсолютного расстояния по координате x, добавленной к неисправленной абсолютной разности по координате y ,
@cmd/cset/a"
- Оценивает разделенные запятыми выражения и печатает последнееx=%3-%1,x*=x>>31|1
y=%4-%2,w=y>>31,y*=w|1
z=x+(y+x&1)*(-(%1+%2+w&1)|1)-y
z*=z>>31,x+y+z
Вычисляетисточник
Желе , 24 байта
Попробуйте онлайн!
Давайте назовем вход . Я работал по формуле Feersum:(x,y),(X,Y)
В первой строке вычисляется , показатель степени в формуле.¢=(Y≮y)+x+y
Последняя строка сначала вычисляет а затем вычисляет максимум из и , где - функция в средней строке.L=[|x−X|,|y−Y|] sum(L) f(L) f
Средняя линия, при , вычисляет , принимает , что к «й степени, а затем добавляет .L=[a,b] −((a+b)mod2) ¢ 2b
источник
ракетка / схема, 214 байт
источник
05AB1E , 24 байта
Порт моего Pyth-ответа , который, в свою очередь, использует примерно такой же подход, как и Feersum's Python-ответ . Вводит в виде списка пар координат, . Исправлена ошибка для +1 байта, затем исправлена еще одна ошибка для +1, но которая давала правильный результат для всех тестовых случаев ...(x1,x2),(y1,y2)
Попробуйте онлайн!
Сломать
источник
©
чтобыD
и удалить®
? Кажется, это работает для дела, которое в настоящее время находится в вашем TIO, но я не уверен, что оно следует одному и тому же пути для каждого дела.M
это будет влиять на поведение. Терпит неудачу за[[0, 127], [0, 0]]
.Python 2 ,
747271 байтПопробуйте онлайн! Ссылка включает в себя тестовые случаи. Изменить: 2 байта сохранены благодаря @JoKing. Сохранено еще один байт благодаря @ Mr.Xcoder. Основываясь на следующей формуле, я нашел в этом вопросе :
Системы координат различаются тремя способами; меняются координаты (что объясняет мой несколько странный порядок имен параметров), координаты расположены под углом а не (что объясняет два дополнения), а координаты в связанном вопросе используют низкое индексирование 1. Поскольку мы принимаем различия, это отменяет большую часть времени, и у нас остается:120∘ 90∘
Затем это можно сделать, заметив, что .−⌊aj+12⌋=⌊−aj2⌋
источник
lambda c,a,d,b:abs(a-b)+abs(a+-(c+a)/2-b--(d+b)/2)+abs((c+a)/2-(d+b)/2)
должен сохранить 3 байта.Pyth ,
3128 байтИспользует примерно тот же подход, что и в ответе Питера feersum . Вводит в виде списка пар координат, . Исправлена ошибка для -1 байта.(x1,x2),(y1,y2)
Попробуй это здесь! или попробуйте тестовый набор!
Сломать
источник
05AB1E , 16 байтов
Использует измененную версию ответа Нила , оптимизированную для стековых языков, таких как 05AB1E. Вводит в виде двух пар координат , разделенных новой строкой из STDIN. Первоначально я объединил это с другим ответом 05AB1E, но затем решил опубликовать его отдельно, потому что он очень, очень отличается.(x1,x2),(y1,y2)
Попробуйте онлайн! или попробуйте тестовый набор! (Использует слегка измененную версию кода (
®
вместо²
), любезно предоставлено Кевином Круйссеном )источник
©+®
наDŠ+
игру, проще настроить тестовый набор. ;) Вот этот набор тестов, и все тестовые примеры действительно выполняются успешно (игнорируйте грязный заголовок; p).Желе ,
22 .. 1615 байтПопробуйте онлайн!
Попробуйте все тестовые случаи.
В этом ответе используется метод @ Neil, который использует модифицированную формулу из этого вопроса math.SE.
Принимает координаты в качестве аргументов
y1, y2
иx1, x2
.источник
Ява 8,
157190188144142141127 байт+33 байта (157 → 190) из-за исправления ошибки.
-44 байта (188 → 144) для преобразования рекурсивного метода в метод с одним циклом.
-14 байт благодаря @ceilingcat .
Объяснение:
Попробуй это здесь.
источник
z*z<c*c
вместо(z<0?-z:z)<(c<0?-c:c)