A3.4 Linked lists

BugBot's route is a linked list stored in the arrays names, xs, ys and nxt (coordinates in cm from where the robot starts, -1 is null), with start and free pointers. At the moment the route is A → B → E → C, but waypoint E is closed. Change only pointers and array elements; do not use the list methods insert, remove, pop or del. 1. Write delete(name): unlink the node called name and put its slot on the front of the free list. 2. Write insert_after(before, name, x, y): take the slot at the front of the free list, store name, x and y in it, link it in straight after the node called before, and return the slot's index. 3. Delete "E", then insert "D" at (40, 60) after "B", and print D stored at index <index>. 4. Traverse the list and print the names in order, separated by single spaces: route: A B D C. 5. Traverse again, calling go_to(xs[i], ys[i]) for each node, so the robot drives the route without passing through E. Both functions change start or free, so declare them global inside the functions.

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

def go_to(x, y):
    """Drive to (x, y) cm from the start: across first, then up or down."""
    px, py = position()
    dx, dy = x - px, y - py
    if dx > 1:
        right(50, distance=dx)
    elif dx < -1:
        left(50, distance=-dx)
    if dy > 1:
        forward(50, distance=dy)
    elif dy < -1:
        backward(50, distance=-dy)

# the route as a linked list held in arrays; -1 is the null pointer
names = ["C", "B", "A", "E", "", ""]
xs    = [0,   40,  0,   20,  0,  0]
ys    = [60,  20,  20,  40,  0,  0]
nxt   = [-1,  3,   1,   0,   5,  -1]
start = 2
free = 4

def delete(name):
    pass

def insert_after(before, name, x, y):
    pass

The hint students can ask for: To delete, find the node before E and point it past E, then put E's slot on the front of the free list. To insert, take the slot at the front of the free list, fill it, point it at whatever B pointed to, then point B at it. Traverse by following next pointers from start until you reach -1.

A solution

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

def go_to(x, y):
    """Drive to (x, y) cm from the start: across first, then up or down."""
    px, py = position()
    dx, dy = x - px, y - py
    if dx > 1:
        right(50, distance=dx)
    elif dx < -1:
        left(50, distance=-dx)
    if dy > 1:
        forward(50, distance=dy)
    elif dy < -1:
        backward(50, distance=-dy)

# the route as a linked list held in arrays; -1 is the null pointer
names = ["C", "B", "A", "E", "", ""]
xs    = [0,   40,  0,   20,  0,  0]
ys    = [60,  20,  20,  40,  0,  0]
nxt   = [-1,  3,   1,   0,   5,  -1]
start = 2
free = 4

def find(name):
    """Index of the node called name, and the index of the node before it (-1 if it is first)."""
    prev = -1
    cur = start
    while cur != -1 and names[cur] != name:
        prev = cur
        cur = nxt[cur]
    return cur, prev

def delete(name):
    global start, free
    cur, prev = find(name)
    if cur == -1:
        return
    if prev == -1:
        start = nxt[cur]
    else:
        nxt[prev] = nxt[cur]
    nxt[cur] = free
    free = cur

def insert_after(before, name, x, y):
    global free
    if free == -1:
        print("no space")
        return -1
    new = free
    free = nxt[free]
    names[new], xs[new], ys[new] = name, x, y
    b, _ = find(before)
    nxt[new] = nxt[b]
    nxt[b] = new
    return new

delete("E")
slot = insert_after("B", "D", 40, 60)
print("D stored at index", slot)

route = []
cur = start
while cur != -1:
    route.append(names[cur])
    cur = nxt[cur]
print("route:", " ".join(route))

cur = start
while cur != -1:
    go_to(xs[cur], ys[cur])
    cur = nxt[cur]

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