Тест на собеседовании про шахматного коня?

Question

[BonBon Slick]

"You have an infinite chessboard, and a knight. The knight starts at [0, 0] and can move [like a knight moves, skipped for brevity]. Given two coordinates on the board, return the least amount of moves the knight has to make to get to that position"

Как я понимаю тут многомерный массив.
У нас координаты по Х и У.
Варианты ходов просчитать довольно просто их всегда всего лишь 8 где сдвиг +2 и +1 по осям. К примеру конь ходит в право ето Х+2 , если направление вверх У-1, вниз У+1 если стартовая точка левый верхний угол как в cocos2d.
Таким образом можно прикинуть исходя из координат к примеру Х=63 и У=31 что конь сделал минимум ходов 31 в правую сторону т.к. для сдвига в право у нас будет Х+2, и особо не важно У-1 или У+1 до самого конца, где надо поставить коня на точку.

Поетому вот ети 2 момента не понятны мне, как поставить коня на точку когда при таких случаях
1 - X = 99, Y = 100 - чет и не чет
2 - Х = 100, У = 99 -
3 - Х = 99, У = 99
4 - Х = 100, У = 100
И надо посчитать общее количество ходов. Пологаю что есть формула кторая это выполняет просто поделив и премножив координаты как-то.

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


Скажу сразу, по матану у меня 1/12 было в школе.

Comments

[hint000]

1 - X = 99, Y = 100 - чет и не чет
2 - Х = 100, У = 99 -
3 - Х = 99, У = 99
4 - Х = 100, У = 100

1 - 67 ходов
2 - 67 (очевидно же, если X и Y поменять местами, то результат не меняется)
3 - 66 (простейший случай X=Y, кратные трём)
4 - 68
Но поскольку это задание, а не вопрос, то увы. Его удалят, а значит нет смысла тратить время на ответ.

[BonBon Slick]

hint000, привели хотя бы формулу как считали.

Answer 1

[Илья Николаевский]

Решение с небольшим перебором случаев, за константу. Но с кучей математики.

Сначала пара простых наблюдений. Можно взять X и Y по модулю и поменять их местами, чтобы X <= Y. Это как бы повороты и отражения всего поля. Сами ходы тоже поворачиваются, но в задаче нужно лишь их количество да и можно при выводе назад преобразовывать ходы, если запомнить, что мы с входными данными делали.

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

Очевидно, что обратные ходы вы никогда не делаете - т.е. нет смысла делать (+1, +2) а потом (-1, -2).

Т.е. фактически у нас всего 4 переменные - сколько ходов каждого из 4-х типов вы делаете. Возможно отрицательное количество, если мы идем в обратную сторону. Четыре типа - (+2, +1), (+1, +2), (-1, +2), (-2, +1).

Можно составить уравнения:
2a+b-c-2d = X
a+2b+2c+d = Y
|a|+|b|+|c|+|d| -> min

Отсюда
a = (2X-Y+4c+5d)/3
b = (2Y-X-5c-4d)/3

Подходят не любые значение c и d, а только такие, что дают делящееся на 3 число в числителях.

Последнее важное наблюдение - хотя бы одна из переменных не превосходит 3 по модулю в оптимальном ответе. Допустим иначе. Во-первых, очевидно, что sing(a) = sign(b), и sign(c) = sign(d) (иначе 6 ходов 3x(+1,+2)-3x(+2+1) можно заменить на 2 хода (-1,+2)+(-2,1). Аналогично 3x(-1,+2)-3x(-2,+1)=(-1,+2)+(-2,+1)).

В первом случае, все переменные положительные (иначе бы мы не получили Y>=0). Но тогда мы имеем 8 ходов 2x(+2, +1)+2x(+1, +2)+2x(-1, +2)+2x(-2, +1) = (0, 12). Но это можно сделать всего за 6 ходов 3x(-1,+2)+3x(+1,+2). Во втором случае, первые 2 переменные положительные, а вторые 2 отрицательные и мы имеем 8 ходов 2x(+2, +1)+2x(+1, +2)-2x(-1, +2)-2x(-2, +1) = (12, 0). Опять же, эти 8 ходов можно заменить на 6 ходов. Итак, мы уменьшаем количество ходов, пока не получим, что какая-то переменная меньше 3 по модулю.

Итак, мы точно знаем, что в оптимальном ответе хотя бы одна переменная не превосходит 3 по модулю. Переберем, что это за переменная и ее значение. Пусть это c=-3..3. Воспользуемся формулами выше:
a = (2X-Y+4c+5d)/3
b = (2Y-X-5c-4d)/3

Тут c - фиксировано и только d - неизвестная.
Остаток от деления на 3 у d известен, это r=(2Y-X-5c)%3, иначе бы второе уравнение не делилось нацело. Еще надо проверить, что этот остаток подходит в первое уравнение. Перепишем d = 3k+r. Подставим:
a = (2X-Y+4c+5r)/3 + 5k
b = (2Y-X-5c-4r)/3 - 4k
c = -3..3
d = 3k+r
|a|+|b|+3|k| -> min

Можно тупо перебрать k (ведь любое целое k дает какой-то ответ).

А можно нанести на ось 3 значения 0, -(2X-Y+4c+5r)/15, (2Y-X-5c-4r)/12. Отсортировать, получить 4 интервала.
На каждом интервале посмотреть, как раскрывается |a|, |b| и |k|. В итоге вы получите коэффициент перед k +-5+-4+-1. В зависимости от знака нужно брать или левый или правый конец интервала (округленный до целого внутрь интервала - левый вверх, а правый вниз). Не забудьте проверить, что этот интервал вообще содержит целые числа. Подставляете k во все уравнения и находите a, b и d, сравниваете с текущим оптимальным ответом, запоминаете, если надо.

По идее, надо перебрать еще 3 варианта, когда фиксирована a, b или d. Но есть упрощение. Можно же вращать доску как мы хотим, меняя местами X и Y и их знаки. Можно всегда считать, что фиксированная переменная - именно с. Но надо выбрать минимум из ответов для (X,Y), (-X,Y), (Y,X), (-Y, X).

Решение за O(1).

Еще раз, решаем для 4-х или 8-ми вариантов (чтобы не думать) расположения X, Y.
Там перебираем c от -3 до 3. Находим r. Проверяем, что оно подходит в оба уравнения (делится нацело).
Находим 3 точки смены знаков |a|, |b|, |k|, сортируем, смотрим на 4 отрезка. Можно, чтобы не разбирать случаи бесконечности, дописать в сортированный массив points[] любое значение, меньше первого, в начало и любое значение, больше последнего, в конец. Потом смотрим на 4 интервала, считаем знак коэффициента перед k в целевой функции и берем самую левую или самую правую целую точку на интервале в качестве кандидата на ответ. Считаем |a|, |b|, |d|.

Comments

[BonBon Slick]

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

[Илья Николаевский]

Andrew Stark, А толку вам с этого кода? Ну, сдадите вы задание где-то копи-пастой. Я его за вас решать не хочу. А без уравнений и математики вы этот код вообще никак не поймете. Зачем-то функция вызывается 4 раза с параметрами (X, Y), (-X,Y), (Y,X), (-Y,X). Ну есть там какой-то цикл от -3 до 3 (А почему не до 33?). Потом какие-то страшные формулы, сортировка, какие-то непонятные условия. Округление, деление на 3 нацело и остатки от деления на 3... Собственно, ходов (+2,+1) в коде вообще не будет.

[Илья Николаевский]

Andrew Stark, Но, если сами не можете написать, то вот код:

int MinNumberOfMovesInternal(int x, int y) {
  int best = -1;
  for (int c = -3; c <=3; ++c) {
    int r =(2*y-x-5*c) % 3;
    if ((2*x-y+4*c+5*r) % 3) continue;
    std::vector<double> borders;
    borders.push_back(-r/3.0);
    borders.push_back(-(2*x-y+4*c+5*r)/15.0);
    borders.push_back((2*y-x-5*c-4*r)/12.0);
    std::sort(borders.begin(), borders.end());
    borders.insert(borders.begin(), borders[0]-10);
    borders.push_back(borders.back() + 10);
    for (int i = 1; i <= 4; ++i) {
      double cur = (borders[i-1] + borders[i]) / 2;
      int cnt = 0;
      if ((2*x-y+4*c+5*r)/3.0 + 5*cur > 0) cnt+= 5;
      else cnt -= 5;
      if ((2*y-x-5*c-4*r)/3.0 - 4*cur > 0) cnt-= 4;
      else cnt += 4;
      if (cur > 0) cnt += 3;
      else cnt -= 3;
      int k;
      if (cnt < 0) { 
        k = floor(borders[i]);
      }
      else {
        k = ceil(borders[i-1]);
      }
      if (k < borders[i-1] || k > borders[i]) continue;
      int a = (2*x-y+4*c+5*r)/3 + 5*k;
      int b = (2*y-x-5*c-4*r)/3 - 4*k;
      int d = 3*k+r;
      int cur_ans = abs(a)+abs(b)+abs(c)+abs(d);
      if (best == -1 || cur_ans < best) {
        best = cur_ans;
      }
    }
  }
  return best;
} 

int MinNumberOfMoves(int x, int y) {
  return std::min(std::min(MinNumberOfMovesInternal(x ,y), MinNumberOfMovesInternal(x, -y)),
                          std::min(MinNumberOfMovesInternal(y, x),MinNumberOfMovesInternal(-y, x)));
}

Выдает идентичные ответы тупому перебору всех четырех переменных четырьмя вложенными циклами для |X|<30, |Y|<30, дальше надоело ждать.

[BonBon Slick]

Илья Николаевский, О, круто! Спасибо.
Вот еще и еще. Первый линк на С++ пример, там как-то попроще будет, возможно вам интересно будет. Я потратил весь день на разбор, нужен же код который смогут прочитать и понять другие. Проверяют ведь и кодсайтл, масштабирование и прочее. ))

И нет, я не буду использовать ваш код. Смысл? Решение все-равно другое использую.

Квик линк

use PHPUnit\Framework\TestCase;

final class TheKnightsWhoSayNiTest extends TestCase {
    /**
     * @test
     */
    public function cases(): void {
        self::assertEquals(2, $this->check(1, 1));
        self::assertEquals(3, $this->check(4, 5));
        self::assertEquals(3, $this->check(1, 0));
        self::assertEquals(4, $this->check(2, 2));
        self::assertEquals(4, $this->check(4, 4));
        self::assertEquals(6, $this->check(8, 8));
        self::assertEquals(6, $this->check(9, 9));
        self::assertEquals(14, $this->check(20, 20));
    }

    private function check(int $x, int $y): int {
        $limit = 100000000;
        if ($limit < abs($x) || $limit < abs($y)) {
            return -1;
        }
        // axes symmetry
        $x = abs($x);
        $y = abs($y);
        // diagonal symmetry
        if ($x < $y) {
            $t = $x;
            $x = $y;
            $y = $t;
        }

        // 2 corner cases
        if (1 === $x && 0 === $y) {
            return 3;
        }
        if (2 === $x && 2 === $y) {
            return 4;
        }

        $delta = $x - $y;

        $divider = $y > $delta ? 3 : 4;
        return (int)($delta - 2 * floor(($delta - $y) / $divider));
    }
}

Вы сильны, умны. Но слишком сложные :3

[Илья Николаевский]

Первая ссылка на другую задачу. Там поле конечное NxN и предположительно маленькое. Решение за O(N^2) - простейший обход в ширину.

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

[BonBon Slick]

Там наглядно описана формула. Почему делим на 3 или 4, наглядно и понятно все.

[BonBon Slick]

Илья Николаевский, я создал тест кейсы вверху и сидел вручную считал)

[BonBon Slick]

Илья Николаевский, Можете попробовать запустить в онлайн РНР или посчитать по ассертам. Они везде проходят.
Хотя судя по всему нет онлайн тестов и надо будет все же выкачать библиотеку или вот

[Илья Николаевский]

Andrew Stark, А вдруг оно не работает на 10000001,9999999? Без доказательства я не считаю задачу решенной. Мне не понятно, почему эта формула работает, как ее вывести или доказать.

Ваша ссылка лишь приводит код и дает ссылку на какую-то олимпиаду (ссылка у меня не работает). Но если погуглить, но находится вот эта pdf-ка, но там нет доказательства.

На стэковерфлоу там кто-то, кстати, утверждает, что это решение не работает и приводит его модификацию с большим количеством случаев. А так, там только ссылка на ту же олимпиаду, и один короткий коммент с интуитивным объяснением деления на 3 или 2, но не доказательством. То, что формула дает ассимптотически ответ, я согласен, но почему она дает точный ответ - не ясно.

[BonBon Slick]

Илья Николаевский,

saco 2007 day 1 solutions

все верно, олимпиадное решение.

Я вот хз как проверить ваши координаты. Но как узнать что ваш код будет работать на 10000001+?))
Там есть лимит же предложенном мною решении $limit = 100000000;
Поетому

if ($limit < abs($x) || $limit < abs($y)) {
            return -1;
        }

Увы, пруфов там нет. Однако говорю, тесты вверху проходят, на реальной доске шахматной можно визуально вручную проверить и посчитать, что и делал.

Можно линк на стек

кстати, утверждает, что это решение не работает и приводит его модификацию с большим количеством случаев. А т

пожулайста?

[BonBon Slick]

Я то найду, но вот если кто читать будет, секономит время всем.

[Илья Николаевский]

Andrew Stark,

Можно линк на стек

Вот ссылка на stackoverflow.

Но как узнать что ваш код будет работать на 10000001+

Решение - логика и математика. Я логически его вывел и доказал, что оно работает для любых значений.

Остается возможность опечаток, переполнений, неверной реализации формул. Но раз оно совпадает с тупым решением для всех значений до 30 по модулю, то опечаток, почти наверняка, нет. Про переполнения - надо смотреть в код, но там нигде умножений двух потенциально больших чисел нет. Только на константы 2...5. И суммы, вычетания. Можно было бы волноваться при значениях порядка двух миллиардов (~2^31). Но и там все фиксится увеличением использованного типа до 64-х битного.

[BonBon Slick]

Илья Николаевский, ето уже детали конкретного языка. Думаю вы правы что при огромных сумах формула может давать сбой, но как проверить, доказать или опровергнуть я без понятия. Прочитал ответы со стека и линки что там были. Судя по кометариям, ответ который дан в олимпиаде неверный немного. Тот что я использую немного отличается. Посмотрите вот сюда

if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );

а теперь мой

$delta   = $x - $y;
        $divider = $y > $delta ? 3 : 4;
        return (int)($delta - 2 * floor(($delta - $y) / $divider));

Мы всегда отнимаем от дельты, как за скобками так и в них.
Собственно вот фикс был предоставлен ниже как и сделано в моем примере.
Формула не покрывает 2 случай при 1 0 и 2 2, поетому там 2 проверки для исключений. Там так же вроде что-то было похожее на ваше решение. В самом конце вопроса уже началась какая-то дичь, сложно разобрать, за 20-30 минут ето написать и отдебажить нереально. Хотя есть ответ на С с тестами примерно выбранного мною решения.

Answer 2

[Denioo]

Первый же запрос в яндекс выдает видео в подробным решением.

Comments

[Александр]

кто-то по мимо женщин за 50 пользуется яндексом?

[BonBon Slick]

Вы вопрос читали? Видео смотрели все? Я же описал что найти позиции куда конь может ходить могу и так, там нет ничего сложного.
В текущей задаче идет расчет наиболее короткого маршрута, за сколько ходов конь допрыгнет до точки.

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

Почему люди лайкают, я не понимаю, пускай и на другом языке но видно, чт оесть формула с расчетом ABS каких-то. Но я не математик, поетому без подготовки конкретно к етой задачи и ее подробного разбора, никогда бы не выполнил.
Не могу выбрать ваш ответ но и задачу уже решил.
Стоит упомянуть, что у меня в старне весь .RU домен ЗАБАНЕН,

[Denioo]

Andrew Stark,

Стоит упомянуть, что у меня в старне весь .RU домен ЗАБАНЕН,

Youtube, google тоже недоступен? А вы видео смотрели? Там всего-то нужно подумать, потому что конь ходит только как конь (ауф). Как королева или слон он ходить не может. Математика школьного уровня, вам выше описали ответ.

[BonBon Slick]

Denioo, читайте коментарии выше в ответе. И то явно не матан школьного уровня как и решение предложенное Ильей)

Answer 3

[Homemade]

Я думаю, тут нужна динамика.