Треугольное Манхэттенское Расстояние

26

Манхэттен расстояние на регулярной сетке число ортогональных шагов нужно предпринять , чтобы достичь одну клетку от другой. Ортогональные шаги - это те, которые проходят через края ячеек сетки (в отличие от углов, которые дали бы нам расстояние Чебышева ).

Мы можем определить аналогичное расстояние на других сетках, например на треугольной сетке. Мы можем обратиться к отдельным ячейкам в сетке с помощью следующей схемы индексации, где каждая ячейка содержит 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,y1x2,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
Мартин Эндер
источник
Включены ли лазейки, получившие отрицательные рейтинги, в официальные лазейки?
DavidC
@DavidC Нет. Из вопроса о лазейке: «[...] лазейка, описанная в любом ответе, который находится на уровне +5 или выше и имеет как минимум вдвое больше отрицательных голосов, чем отрицательные, может считаться неприемлемой для сообщества. "
Мартин Эндер
Разрешено ли брать пятый вход, который по умолчанию начинается с 0 (результат)? Тогда мне не нужно добавлять (a,b,x,y)->c(a,b,x,y,0)(вызывая разделенный метод cс четырьмя аргументами и в 0качестве пятого аргумента) к моему ответу.
Кевин Круйссен,
3
@KevinCruijssen Нет, извините. Дополнительные фиксированные аргументы слишком легко использовать (и просто использование 0 в качестве особого случая кажется странным).
Мартин Эндер
@MartinEnder Хорошо, подумал, но никогда не помешает спросить. В этом случае мой 190-байтовый ответ остается. Несмотря на то, что я ответил наполовину год назад, один контрольный пример не удался. Только сейчас наткнулся на вопрос и смог исправить ошибку в моем ответе.
Кевин Круйссен,

Ответы:

7

JavaScript (ES6), 84 78 байт

Сохранено 6 байтов благодаря Нейлу

(a,b,c,d,x=a>c?a-c:c-a,y=b>d?b-d:d-b,z=x>y?x:y)=>y+z+(x+z&1?a+b+(b>d)&1||-1:0)

Контрольные примеры

Исходный рекурсивный раствор, 100 88 81

Сохранено 12 байтов благодаря ETHproductions
Сохранено 7 байтов благодаря Нейлу

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

Как это работает

Хотя это по существу относится к текущей версии, следующее объяснение более конкретно относится к начальной версии:

f=(a,b,c,d)=>b-d?a+b+(b>d)&1?f(a+1-2*(a>c),b,c,d)+1:f(a,b+1-2*(b>d),c,d)+1:Math.abs(a-c)

Переход от (x0, y) к (x1, y) тривиален, потому что мы можем пройти через боковые ребра от исходного треугольника до целевого. Манхэттенское расстояние в этом случае составляет | х0 - х1 | ,

Хитрая часть - вертикальные шаги. Чтобы перейти от строки y0 к строке y1 , мы должны принять во внимание эти два параметра:

  • Ориентация текущего треугольника
  • Является ли y0 меньше или больше, чем y1

Ориентация треугольника определяется соотношением x + y :

  • если это даже, треугольник направлен вверх
  • если это нечетно, треугольник направлен вниз

Мы можем пойти вниз от треугольника, направленного вверх (полезно, когда y0 <y1 ), и вверх от треугольника, направленного вниз (полезно, когда y0> y1 ).

Комбинируя ориентацию треугольника со сравнением между y0 и y1 , мы получаем формулу x + y0 + (y0> y1? 1: 0) , результат которой равен четности, если мы можем идти в нужном направлении, и нечетным, если нет.

Если мы не можем напрямую добраться до следующей строки, нам сначала нужно получить правильное выравнивание, обновив x :

  • если x еще не равно x1 , мы определенно хотим двигаться в правильном направлении, поэтому мы увеличиваем его, если x меньше x1, и уменьшаем его, если x больше x1
  • если x уже равен x1 , мы можем увеличить или уменьшить его

Контрольные примеры

Arnauld
источник
Это ... много очень маленьких математических операций ... Но не могли бы вы nвообще пропустить переменную и просто добавить 1 к результату каждой итерации? ( Я думаю, 90 символов )
ETHproductions
@ETHproductions Если честно, я разместил это без какого-либо серьезного гольфа. Но это определенно первое, что нужно сделать. Благодарность!
Арно
1
Кроме того, я думаю, что приоритет оператора &означает, что вы можете сделать, a+b+(b>d)&1чтобы сохранить 2 байта
ETHproductions
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
Нейл
Я думаю, что было бы возможно сохранить другой байт, используя умное каррирование.
Нил
5

Python 2, 74 байта

lambda x,y,X,Y:abs(y-Y)+max(x-X,X-x,abs(y-Y)+((x+y+X+Y)%-2)**(x^y^(Y>=y)))
feersum
источник
1
Вы можете, пожалуйста, объясните эту часть: **(x^y^(Y>=y))?
Мертвый Опоссум
1
@DeadPossum Перемещение на расстояние 1 по вертикали может занять 1 или 3 хода; Невозможно определить, просто взглянув на четности, вы должны сравнить значения y.
feersum
2

Пакетный, 99 байтов

@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

Пояснение: Движение только по горизонтали просто принимает абсолютную разницу по оси X. Для достаточно большого x вертикальное движение требует только одного дополнительного шага на абсолютную разницу y-координат, но для малого x требуется четыре дополнительных шага на две разности y-координат плюс один или три шага для нечетной разности. Это рассчитывается как два шага на разницу плюс поправочный коэффициент. В результате получается больший из исправленных двух шагов и сумма абсолютных разностей, хотя сам он вычисляется как большее из исправленной абсолютной разности по координате y и абсолютного расстояния по координате x, добавленной к неисправленной абсолютной разности по координате y ,

  • @cmd/cset/a" - Оценивает разделенные запятыми выражения и печатает последнее
  • x=%3-%1,x*=x>>31|1x=|x2x1|
  • y=%4-%2,w=y>>31,y*=w|1w=y1>y2y=|y2y1|
  • z=x+(y+x&1)*(-(%1+%2+w&1)|1)-yc=(y+(xmod2))(12((x1+y1+w)mod2)),z=x+cy
  • z*=z>>31,x+y+zВычисляетmax(x,yc)+y=x+ymin(0,x+cy)
Нил
источник
2

Желе , 24 байта

⁴<³¬Ḋ;³S
SḂN*¢+ḊḤ$
ạµS»Ç

Попробуйте онлайн!

Давайте назовем вход . Я работал по формуле Feersum:(x,y),(X,Y)

d=|yY|+max(|xX|,|yY|+((x+y+X+Y)mod2)xy(Yy))=|yY|+max(|xX|,|yY|+[(|xX|+|yY|mod2)]x+y+(Yy))=max(|xX|+|yY|,2|yY|+[(|xX|+|yY|mod2)](Yy)+x+y).

В первой строке вычисляется , показатель степени в формуле.¢=(Yy)+x+y

Последняя строка сначала вычисляет а затем вычисляет максимум из и , где - функция в средней строке.L=[|xX|,|yY|]sum(L)f(L)f

Средняя линия, при , вычисляет , принимает , что к «й степени, а затем добавляет .L=[a,b]((a+b)mod2)¢2b

Линн
источник
2

ракетка / схема, 214 байт

(define(f x y X Y)(let m((p x)(q y)(c 0))
(let((k(+ c 1))(d(- Y q)))
(cond((= 0(- X p)d)c)
((and(> d 0)(even?(+ p q)))(m p(+ q 1)k))
((and(< d 0)(odd?(+ p q)))(m p(- q 1)k))
((< p X)(m(+ p 1)q k))
(else(m(- p 1)q k))))))
Kevin
источник
2

05AB1E , 24 байта

Порт моего Pyth-ответа , который, в свою очередь, использует примерно такой же подход, как и Feersum's Python-ответ . Вводит в виде списка пар координат, . Исправлена ​​ошибка для +1 байта, затем исправлена ​​еще одна ошибка для +1, но которая давала правильный результат для всех тестовых случаев ...(x1,x2),(y1,y2)

ÆÄ`©I˜OÉ(IøнOIθD{Q+m+M®+

Попробуйте онлайн!

Сломать

IÄ` © I˜OÉ (IøнOIθD {Q + m + M® + Полная программа. I представляет оцененный ввод.
ReduÄ Уменьшите пары путем вычитания, возьмите абсолютные значения.
  `© Сбросьте их отдельно в стек и сохраните второе
                            один, | y1-y2 | в реестре С.
    I˜O Вставьте сумму сглаженного ввода в стек.
       Э (Возьмите его паритет и отрицайте его.
         Iøn Push [x1, y1].
            O Возьмите x1 + y1 (сложите их).
             IθD {Q Затем проверьте, отсортирована ли вторая пара (y1 ≤ y2).
                  + И суммируем это с x1 + y1.
                   м экспонат. Нажмите паритет выше ** результат.
                    + И добавьте к этому вторую абсолютную разницу.
                     M® + В результате выведите наибольшее число в стек
                            плюс значение, хранящееся в регистре C.
Мистер Xcoder
источник
Я не 100% уверен, но вы не можете изменить , ©чтобы Dи удалить ®? Кажется, это работает для дела, которое в настоящее время находится в вашем TIO, но я не уверен, что оно следует одному и тому же пути для каждого дела.
Кевин Круйссен
1
@KevinCruijssen РЕДАКТИРОВАТЬ : Нет, потому что Mэто будет влиять на поведение. Терпит неудачу за [[0, 127], [0, 0]].
г-н Xcoder
2

Python 2 , 74 72 71 байт

lambda c,a,d,b:abs(a-b)+abs(a+(-c-a)/2-b-(-d-b)/2)+abs((c+a)/2-(d+b)/2)

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Изменить: 2 байта сохранены благодаря @JoKing. Сохранено еще один байт благодаря @ Mr.Xcoder. Основываясь на следующей формуле, я нашел в этом вопросе :

|aibi|+|(aiaj2)(bibj2)|+|aj+12bj+12|

Системы координат различаются тремя способами; меняются координаты (что объясняет мой несколько странный порядок имен параметров), координаты расположены под углом а не (что объясняет два дополнения), а координаты в связанном вопросе используют низкое индексирование 1. Поскольку мы принимаем различия, это отменяет большую часть времени, и у нас остается:12090

|aibi|+|(aiaj+12)(bibj+12)|+|aj2bj2|

Затем это можно сделать, заметив, что .aj+12=aj2

Нил
источник
Вы можете сделать его однострочным, удалив новую строку
Джо Кинг
1
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 байта.
Мистер Кскодер
1

Pyth , 31 28 байт

Использует примерно тот же подход, что и в ответе Питера feersum . Вводит в виде списка пар координат, . Исправлена ​​ошибка для -1 байта.(x1,x2),(y1,y2)

+eKaMQg#hK+eK^%ssQ_2+shCQSIe

Попробуй это здесь! или попробуйте тестовый набор!

Сломать

+ eKaMQg # hK + eK ^% ssQ_2xxFhCQSIe Полная программа. Q = eval (input ()).
  KaMQ Сохраните различия [| x1-x2 |, | y1-y2 |] в K.
 e Получить последнее (| y1-y2 |).
+ g # И добавить его к наибольшему значению между:
        hK - глава K (| x1-x2 |)
          + - И результат добавления:
           eK Конец K (| y1-y2 |).
             ^ - с результатом возведения в степень:
              % ssQ_2 Сумма сглаженного Q, по модулю -2.
                                        Выход -1, если x1 + x2 + y1 + y2 нечетно, иначе 0.
                    xxFhCQSIe - по результату этого выражения:
                       hCQ Переставьте Q и получите голову (x1, y1).
                     xF Уменьшить поразрядным XOR.
                          И проверьте, отсортирован ли список [y1, y2].
                    x После чего xor результат с помощью bool (0/1).
Мистер Xcoder
источник
1

05AB1E , 16 байтов

Использует измененную версию ответа Нила , оптимизированную для стековых языков, таких как 05AB1E. Вводит в виде двух пар координат , разделенных новой строкой из STDIN. Первоначально я объединил это с другим ответом 05AB1E, но затем решил опубликовать его отдельно, потому что он очень, очень отличается.(x1,x2),(y1,y2)

+D(‚2÷Æ`²Æ©+®)ÄO

Попробуйте онлайн! или попробуйте тестовый набор! (Использует слегка измененную версию кода ( ®вместо ²), любезно предоставлено Кевином Круйссеном )

Мистер Xcoder
источник
Хороший ответ! Это не то, что нужно для игры в гольф, но когда вы переходите ©+®на DŠ+игру, проще настроить тестовый набор. ;) Вот этот набор тестов, и все тестовые примеры действительно выполняются успешно (игнорируйте грязный заголовок; p).
Кевин Круйссен
@KevinCruijssen У меня было это как альтернативная версия, но мне не пришло в голову, что я могу написать набор тестов ... Спасибо, я добавлю это
Mr. Xcoder
1
@KevinCruijssen Я проиграл еще два (очень очевидных ...!) Байта и преуспел в нарушении совместимости набора тестов, поэтому я сохранил его как есть: P Кстати, спасибо за редактирование.
г-н Xcoder
1

Ява 8, 157 190 188 144 142 141 127 байт

(a,b,x,y)->{int r=0,c=1,z=1;for(;(c|z)!=0;r--){c=x-a;z=y-b;if((z<0?-z:z)<(c<0?-c:c)|a%2!=b%2?z<0:z>0)b+=z<0?-1:1;else a+=c<0?-1:1;}return~r;}

+33 байта (157 → 190) из-за исправления ошибки.
-44 байта (188 → 144) для преобразования рекурсивного метода в метод с одним циклом.
-14 байт благодаря @ceilingcat .

Объяснение:

Попробуй это здесь.

(a,b,x,y)->{          // Method with four integers as parameter and integer return-type
                      // (a=x1; b=y1; x=x2; y=y2)
  int r=0,            //  Result-integer `r`, starting at 0
      c=1,z=1;        //  Temp integers for the differences, starting at 1 for now
  for(;(c|z)!=0;      //  Loop until both differences are 0
      r--){           //    After every iteration: decrease the result `r` by 1
    c=x-a;            //   Set `c` to x2 minus x1
    z=y-b;            //   Set `z` to y2 minus y1
    if(z*Z            //   If the absolute difference between y2 and y1
       <c*c)          //   is smaller than the absolute difference between x2 and x1
       |a%2!=b%2?     //   OR if the triangle at the current location is facing downwards
         z<0          //       and we have to go upwards,
        :z>0)         //      or it's facing upwards and we have to go downwards
      b+=z<0?-1:1;    //    In/decrease y1 by 1 depending on where we have to go
    else              //   Else:
     a+=c<0?-1:1;}    //    In/decrease x1 by 1 depending on where we have to go
  return~r;           //  Return `-r-1` as result
Кевин Круйссен
источник
1
Предложить z*z<c*cвместо(z<0?-z:z)<(c<0?-c:c)
потолок кошка
@ceilingcat Ах, хорошо. Благодарность!
Кевин Круйссен