rotate_left.py

# Another from Programming Pearls (again, my attempt before reading
# the rest of the chapter). Rotate a vector left in place by some
# amount without using extra memory proportional to the length of the
# input vector and while running in in O(n)

def rotate_left(vec, n):
    i = 0
    start = 0
    letter = vec[i]
    seen = 0
    while True:
        seen += 1
        i = (i - n) % len(vec)
        newletter = vec[i]
        vec[i] = letter
        letter = newletter
        # We've looped back to where we started
        if i == start:
            # Have we seen all the items in the vector yet?
            if seen == len(vec):
                break
            else:
                start = i = start+1
                letter = vec[i]
    return vec

print "".join(rotate_left(list("abcdefgh"), 3))

# Can also rotate right
print "".join(rotate_left(list("abcdefgh"), -2))