Spiral order
Write spiral(m) that returns the items of a rectangular matrix in clockwise spiral order, starting at the top left. Do not change the matrix you were given.
spiral([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
# [1, 2, 3, 6, 9, 8, 7, 4, 5]Show hint
Take the top row. Then rotate what is left a quarter turn anticlockwise, so the next edge you need becomes the new top row. zip(*m) helps.
Show solution
def spiral(m):
m = [row[:] for row in m] # work on a copy
out = []
while m:
out += m.pop(0)
m = [list(row) for row in zip(*m)][::-1]
return outzip(*m) turns columns into rows, and reversing the result completes an anticlockwise rotation, so the right-hand column is now on top. The copy matters: pop(0) would otherwise empty the caller's matrix.
This version is short but rebuilds the matrix every turn. The faster approach keeps four boundaries (top, bottom, left, right) and walks them inwards, visiting each item once.
Want a problem like this every day? See today's problem and keep a streak going.