Problem: ¶

Given an nxm 2D array of integers, print it in spiral order.

Eg for a 3×3 matrix (with the following implicit values):

1	2	3
4	5	6
7	8	9

Would be printed as “1 2 3 6 9 8 7 4 5”

Solution: ¶

The straight forward solution is to have 4 iterations, and in each iteration to print one of the two directions (horizontal and vertical) alternatively.

However a more intuitive solution is to use vectors to create a tour starting from the index (0,0) and incrementing the next point based on the current direction and position.

First we create the concept of directions along with a couple of helper functions:

 1data Direction = North | East | South | West
 2-- Return the clockwise direction of a given direction
 3clockwise_of North = East
 4clockwise_of East = South
 5clockwise_of South = West
 6clockwise_of West = North
 7
 8-- Returns the vector representing the direction
 9vector_of North = (0, -1)
10vector_of South = (0, 1)
11vector_of East = (1, 0)
12vector_of West = (-1, 0)
13
14-- The primary coordinate that will be updated when traversing in a particular direction
15primary_coord North = 1
16primary_coord South = 1
17primary_coord East = 0
18primary_coord West = 0
19
20-- Given a direction and point, returns the next and previous points in the direction.
21next_pt dir (x,y) = ((x + fst (vector_of dir)),(y + snd (vector_of dir)))
22prev_pt dir (x,y) = ((x - fst (vector_of dir)),(y - snd (vector_of dir)))

Now we simply use the above helpers to start and iterate through a tour:

 1print_spirally width height = print_spirally' East (0,0) 0 [width, height]
 2    where
 3        print_spirally' dir (x,y) t [w,h]
 4            | w == 0 || h == 0 = []
 5            | t < [w,h] !! curr_coord = (y * width + x + 1) : print_spirally' dir (next_pt dir (x,y)) (t+1) [w,h]
 6            | otherwise = print_spirally' next_dir (next_pt next_dir (prev_pt dir (x,y))) 0 [next_w,next_h]
 7            where
 8                curr_coord = primary_coord dir
 9                dir_vector = vector_of dir
10                next_dir = clockwise_of dir
11                next_dir_vector = vector_of next_dir
12                next_w = w - (abs (fst next_dir_vector))
13                next_h = h - (abs (snd next_dir_vector))

Couple of things to note:

w,h represent the “remaining” width and height in the spiral as each time there is a change in direction, the available coordinate size reduces by one (height if beginning vertically, width if beginning horizontally).
t is the number of values printed in a given direction (when this value reaches “w” or “h” depending on the direction, direction is rotated and t is reset to 0).
When the direction needs to change (in the otherwise) the “current” point is one beyond the last point in the direction. For this reason the next point is evaluted from the previous direction in the previous point.