Наивный грубый подход
Одним из способов будет рекурсивное исследование каждого возможного хода, пока вы не достигнете цели.
Следует учесть, что робот может продолжать двигаться бесконечно (никогда не достигая цели), поэтому вам нужен конечный случай, чтобы функция завершилась. К счастью, положение всегда увеличивается по оси x и y, поэтому, когда координата x или y больше цели, вы можете отказаться от исследования этого пути.
Так что-то вроде:
def can_reach_target(pos, target):
if pos == target:
return True
if pos[0] > target[0] or pos[1] > target[1]:
return False
return can_reach_target((pos[0], sum(pos)), target) or \
can_reach_target((sum(pos), pos[1]), target)
И это работает:
>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False
Ограничение состоит в том, что это не работает для отрицательных координат - не уверен, является ли это требованием, просто дайте мне знать, если это так, и я адаптирую ответ.
Bactracking
С другой стороны, если отрицательные координаты недопустимы, мы также можем подойти к этому, как Дейв предлагает . Это гораздо эффективнее, поскольку осознание того, что робот может добраться до каждой координаты одним-единственным способом.
Метод основан на том, что мы можем определить, каким путем мы шагнули: либо увеличить x-координату, либо y-координату. Мы можем определить, какая координата была изменена последней, выбрав большую из двух. Следующее доказательство гарантирует, что это так.
Возможны изменения состояния:
1. (a, b) => (a+b, b) a x-coordinate change
и
2. (a, b) => (a, a+b) a y-coordinate change
В случае (1) координата x теперь больше, поскольку:
a > 0
a + b > b (add b to both sides)
и аналогично, поскольку b также > 0, мы можем сделать вывод, что a+b есть > a.
Теперь мы можем начать с цели и спросить: какая координата привела нас сюда? И ответ прост. Если x-координата больше, чем y-координата, вычтите y-координату из x-координаты, в противном случае вычтите x-координату из y-координаты.
То есть для координаты (x,y), если x > y, то мы пришли из (x-y,y) в противном случае (x,y-x).
Первый код теперь можно адаптировать к:
def can_reach_target(pos, target):
if pos == target:
return True
if target[0] < pos[0] or target[1] < pos[1]:
return False
x, y = target
return can_reach_target(pos, (x-y,y) if x > y else (x,y-x))
, который работает как ожидалось:
>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False
Задержка
>>> timeit.timeit('brute_force((2,3),(62,3))',globals=locals(),number=10**5)
3.41243960801512
>>> timeit.timeit('backtracker((2,3),(62,3))',globals=locals(),number=10**5)
1.4046142909792252
>>> timeit.timeit('brute_force((2,3),(602,3))',globals=locals(),number=10**4)
3.518286211998202
>>> timeit.timeit('backtracker((2,3),(602,3))',globals=locals(),number=10**4)
1.4182081500184722
Итак, вы можете видеть, что бэктрекер почти в три раза быстрее в обоих случаях.