Coordinates for clockwise outwards spiral

Question

I'm trying to make what I think is called an Ulam spiral using Haskell. It needs to go outwards in a clockwise rotation:

   6 - 7 - 8 - 9
   |           |
   5   0 - 1   10
   |       |   |
   4 - 3 - 2   11
               |
 ..15- 14- 13- 12

For each step I'm trying to create coordinates, the function would be given a number and return spiral coordinates to the length of input number eg:

mkSpiral 9
> [(0,0),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1)]

(-1, 1) - (0, 1) - (1, 1)
   |        
(-1, 0)   (0, 0) - (1, 0)
   |                 |
(-1,-1) - (0,-1) - (1,-1)

I've seen Looping in a spiral solution, but this goes counter-clockwise and it's inputs need to the size of the matrix.

I also found this code which does what I need but it seems to go counterclock-wise, stepping up rather than stepping right then clockwise :(

type Spiral = Int
type Coordinate = (Int, Int)

-- number of squares on each side of the spiral
sideSquares :: Spiral -> Int
sideSquares sp = (sp * 2) - 1

-- the coordinates for all squares in the given spiral
coordinatesForSpiral :: Spiral -> [Coordinate]
coordinatesForSpiral 1 = [(0, 0)]
coordinatesForSpiral sp = [(0, 0)] ++ right ++ top ++ left ++ bottom
  where fixed = sp - 1
        sides = sideSquares sp - 1
        right = [(x, y) | x <- [fixed], y <- take sides [-1*(fixed-1)..]]
        top = [(x, y) | x <- reverse (take sides [-1*fixed..]), y <- [fixed]]
        left = [(x, y) | x <- [-1*fixed], y <- reverse(take sides [-1*fixed..])]
        bottom = [(x, y) | x <- take sides [-1*fixed+1..], y <- [-1*fixed]]

-- an endless list of coordinates (the complete spiral)
mkSpiral :: Int -> [Coordinate]
mkSpiral x = take x endlessSpiral

endlessSpiral :: [Coordinate]
endlessSpiral = endlessSpiral' 1

endlessSpiral' start = coordinatesForSpiral start ++ endlessSpiral' (start + 1)

After much experimentation I can't seem to change the rotation or starting step direction, could someone point me in the right way or a solution that doesn't use list comprehension as I find them tricky to decode?

Answer 1

Let us first take a look at how the directions of a spiral are looking:

R D L L U U R R R D D D L L L L U U U U ....

We can split this in sequences like:

      n times       n+1 times
       _^_           __^__
      /   \         /     \
R … R D … D L L … L U U … U
\_ _/       \__ __/
  v            v
n times     n+1 times

We can repeat that, each time incrementing n by two, like:

data Dir = R | D | L | U

spiralSeq :: Int -> [Dir]
spiralSeq n = rn R ++ rn D ++ rn1 L ++ rn1 U
    where rn = replicate n
          rn1 = replicate (n + 1)

spiral :: [Dir]
spiral = concatMap spiralSeq [1, 3..]

Now we can use Dir here to calculate the next coordinate, like:

move :: (Int, Int) -> Dir -> (Int, Int)
move (x, y) = go
    where go R = (x+1, y)
          go D = (x, y-1)
          go L = (x-1, y)
          go U = (x, y+1)

We can use scanl :: (a -> b -> a) -> a -> [b] -> [a] to generate the points, like:

spiralPos :: [(Int, Int)]
spiralPos = scanl move (0,0) spiral

This will yield an infinite list of coordinates for the clockwise spiral. We can use take :: Int -> [a] -> [a] to take the first k items:

Prelude> take 9 spiralPos
[(0,0),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1)]

Answer 2

The idea with the following solution is that instead of trying to generate the coordinates directly, we’ll look at the directions from one point to the next. If you do that, you’ll notice that starting from the first point, we go 1× right, 1× down, 2× left, 2× up, 3× right, 3× down, 4× left… These can then be seperated into the direction and the number of times repeated:

direction: > v < ^ > v < …
   # reps: 1 1 2 2 3 3 4 …

And this actually gives us two really straightforward patterns! The directions just rotate > to v to < to ^ to >, while the # of reps goes up by 1 every 2 times. Once we’ve made two infinite lists with these patterns, they can be combined together to get an overall list of directions >v<<^^>>>vvv<<<<…, which can then be iterated over to get the coordinate values.

Now, I’ve always thought that just giving someone a bunch of code as the solution is not the best way to learn, so I would highly encourage you to try implementing the above idea yourself before looking at my solution below.

---

Welcome back (if you did try to implement it yourself). Now: onto my own solution. First I define a Stream data type for an infinite stream:

data Stream a = Stream a (Stream a) deriving (Show)

Strictly speaking, I don’t need streams for this; Haskell’s predefined lists are perfectly adequate for this task. But I happen to like streams, and they make some of the pattern matching a bit easier (because I don’t have to deal with the empty list).

Next, I define a type for directions, as well as a function specifying how they interact with points:

-- Note: I can’t use plain Left and Right
-- since they conflict with constructors
-- of the ‘Either’ data type
data Dir = LeftDir | RightDir | Up | Down deriving (Show)

type Point = (Int, Int)

move :: Dir -> Point -> Point
move LeftDir (x,y)  = (x-1,y)
move RightDir (x,y) = (x+1, y)
move Up (x,y)       = (x,y+1)
move Down (x,y)     = (x,y-1)

Now I go on to the problem itself. I’ll define two streams — one for the directions, and one for the number of repetitions of each direction:

dirStream :: Stream Dir
dirStream = Stream RightDir $ Stream Down $ Stream LeftDir $ Stream Up dirVals

numRepsStream :: Stream Int
numRepsStream = go 1
  where
    go n = Stream n $ Stream n $ go (n+1)

At this point we’ll need a function for replicating each element of a stream a specific number of times:

replicateS :: Stream Int -> Stream a -> Stream a
replicateS (Stream n ns) (Stream a as) = conss (replicate n a) $ replicateS ns as
  where
    -- add more than one element to the beginning of a stream
    conss :: [a] -> Stream a -> Stream a
    conss [] s = s
    conss (x:xs) s = Stream x $ appends xs s

This gives replicateS dirStream numRepsStream for the stream of directions. Now we just need a function to convert those directions to coordinates, and we’ve solved the problem:

integrate :: Stream Dir -> Stream Point
integrate = go (0,0)
  where
    go p (Stream d ds) = Stream p (go (move d p) ds)

spiral :: Stream Point
spiral = integrate $ replicateS numRepsStream dirStream

Unfortunately, it’s somewhat inconvenient to print an infinite stream, so the following function is useful for debugging and printing purposes:

takeS :: Int -> Stream a -> [a]
takeS 0 _ = []; takeS n (Stream x xs) = x : (takeS (n-1) xs)