Задача с перемещением по квадрату 10х10 между точками

Дан список с 4-мя значениями в виде [53, 38, 35, 56] (координаты на квадрате, которые эквивалентны (5, 3) (3, 8), (3, 5) и (5, 6) соответственно). Если первая цифра (вертикаль x) равна 0, то пишется только координата y, то есть если мы имеем (0, 5) - она будет записываться в виде: 5. Необходимо написать функцию, которая принимает этот список, в котором первый элемент - это точка старта, второй, третий и четвертый - это пункты, которые мнимый объект должен пересечь (в порядке размещения элементов). Функция должна вернуть список из элементов, которые будут отображать пошаговое перемещение.

Технические подробности:

  1. Путь должен проходить через каждый пункт ​​один раз и в порядке возрастания.
  2. Путь не должен пересекаться / накладываться друг на друга.
  3. Расстояние, преодолеваемое путем, должно быть минимально необходимым для выполнения задачи.
  4. Полный набор 30 тестов : фиксированные тесты, 100: случайные тесты
  5. Входные данные всегда будут действительны, и каждый тест будет иметь ноль или более возможных решений.

Иллюстрированный пример:

введите сюда описание изображения

Входной список на данном примере: [0, 65, 93, 36].

Выходной список для рисунка B: [0, 1, 2, 3, 4, 5, 15, 25, 35, 45, 55, 65, 64, 63, 73, 83, 93, 94, 95, 96, 86, 76, 66, 56, 46, 36].

Набросал код, в итоге из 30 тестов проходит только 10-15. И я понимаю из-за чего. Дело в том, что такой простой логики здесь недостаточно, необходимо как-то решить проблему с пересечениями, например если взять такой список: [53, 38, 35, 56], путь начинает накладываться сам на себя, и я до сих пор не могу решить эту проблему.

Непосредственно мой код:

def four_pass(stations):
    x = stations[0]
    points = [x]

    for y in range(1, 4):
        while x != stations[y]:
            if 0 > x > 9:
                break
            if x % 10 < stations[y] % 10 and x + 1 not in points:
                if x + 1 not in stations[y+1:]:
                    x += 1
                    points.append(x)
                else:
                    if x - 10 not in stations[y+1:]:
                        x -= 10
                        points.append(x)
                    else:
                        x += 10
                        points.append(x)
            elif x % 10 > stations[y] % 10 and x - 1 not in points:
                if x - 1 not in stations[y + 1:]:
                    x -= 1
                    points.append(x)
                else:
                    if x - 10 not in stations[y + 1:]:
                        x -= 10
                        points.append(x)
                    else:
                        x += 10
                        points.append(x)
            elif x // 10 < stations[y] // 10 and x + 10 not in points:
                if x + 10 not in stations[y + 1:]:
                    x += 10
                    points.append(x)
                else:
                    if x - 1 not in stations[y + 1:]:
                        x -= 1
                        points.append(x)
                    else:
                        x += 1
                        points.append(x)
            elif x // 10 > stations[y] // 10 and x - 10 not in points:
                if x - 10 not in stations[y + 1:]:
                    x -= 10
                    points.append(x)
                else:
                    if x - 1 not in stations[y + 1:]:
                        x -= 1
                        points.append(x)
                    else:
                        x += 1
                        points.append(x)
            else:
                break

    print(points)


four_pass([37,61,92,36])

Ответы (0 шт):