A6.7 Limits of computation: tractable and intractable problems

Plan and drive a route to all five drop points, using the heuristic, and compare it with the best route. - The drop points are in drops: a dictionary from a letter to an (x, y) position on the mat in cm. The robot starts at START. Distances are straight lines: use math.dist. - drive_to(x, y) is written for you: it slides the robot to that mat position. - Write tour_length(order): order is a sequence of letters; return the total distance from START through each point in that order, without coming back. - Write nearest_neighbour(): return a list of the five letters in the order the nearest neighbour heuristic visits them, starting from START. - Print nearest neighbour: then the letters separated by single spaces, a space, then the length to 1 decimal place and cm. For example nearest neighbour: A B C D E 123.4 cm. - Find the shortest order by brute force over every order (itertools.permutations) and print it the same way, starting best: . - Then drive the nearest neighbour route, visiting the points in that order. Do not type any orders or lengths in; work them out.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import math
from itertools import permutations

START = (50, 10)
drops = {"A": (80, 45), "B": (65, 70), "C": (85, 85), "D": (20, 20), "E": (55, 35)}

def wrapped(h):
    return (h + 180) % 360 - 180

def drive_to(x, y, speed=70):
    # slide to the mat point (x, y), holding heading 0, until within 3 cm
    while True:
        px, py = position()
        dx, dy = x - START[0] - px, y - START[1] - py
        if math.hypot(dx, dy) < 3:
            break
        a = math.radians(wrapped(math.degrees(math.atan2(dx, dy)) - heading()))
        drive(speed * math.cos(a), speed * math.sin(a), wrapped(0 - heading()) * 3)
        wait(0.1)
    stop()

The hint students can ask for: For the heuristic, keep a list of the points not yet visited and where you are now; each step, pick the unvisited point closest to where you are, move there and cross it off. For brute force, find the order whose tour length is smallest. Only drive once both have been printed.

A solution

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import math
from itertools import permutations

START = (50, 10)
drops = {"A": (80, 45), "B": (65, 70), "C": (85, 85), "D": (20, 20), "E": (55, 35)}

def wrapped(h):
    return (h + 180) % 360 - 180

def drive_to(x, y, speed=70):
    # slide to the mat point (x, y), holding heading 0, until within 3 cm
    while True:
        px, py = position()
        dx, dy = x - START[0] - px, y - START[1] - py
        if math.hypot(dx, dy) < 3:
            break
        a = math.radians(wrapped(math.degrees(math.atan2(dx, dy)) - heading()))
        drive(speed * math.cos(a), speed * math.sin(a), wrapped(0 - heading()) * 3)
        wait(0.1)
    stop()

def tour_length(order):
    total = 0
    here = START
    for name in order:
        total = total + math.dist(here, drops[name])
        here = drops[name]
    return total

def nearest_neighbour():
    order = []
    here = START
    left = sorted(drops)
    while left:
        nearest = left[0]
        for name in left:
            if math.dist(here, drops[name]) < math.dist(here, drops[nearest]):
                nearest = name
        order.append(nearest)
        left.remove(nearest)
        here = drops[nearest]
    return order

route = nearest_neighbour()
print("nearest neighbour:", " ".join(route), f"{tour_length(route):.1f} cm")
best = min(permutations(drops), key=tour_length)
print("best:", " ".join(best), f"{tour_length(best):.1f} cm")
for name in route:
    drive_to(*drops[name])

Any program that meets the task's checks is marked correct in the simulator; this is one way, not the only way.