Задача с перемещением по квадрату 10х10 между точками
Дан список с 4-мя значениями в виде [53, 38, 35, 56] (координаты на квадрате, которые эквивалентны (5, 3) (3, 8), (3, 5) и (5, 6) соответственно). Если первая цифра (вертикаль x) равна 0, то пишется только координата y, то есть если мы имеем (0, 5) - она будет записываться в виде: 5. Необходимо написать функцию, которая принимает этот список, в котором первый элемент - это точка старта, второй, третий и четвертый - это пункты, которые мнимый объект должен пересечь (в порядке размещения элементов). Функция должна вернуть список из элементов, которые будут отображать пошаговое перемещение.
Технические подробности:
- Путь должен проходить через каждый пункт один раз и в порядке возрастания.
- Путь не должен пересекаться / накладываться друг на друга.
- Расстояние, преодолеваемое путем, должно быть минимально необходимым для выполнения задачи.
- Полный набор 30 тестов : фиксированные тесты, 100: случайные тесты
- Входные данные всегда будут действительны, и каждый тест будет иметь ноль или более возможных решений.
Иллюстрированный пример:
Входной список на данном примере: [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])
