顺时针向外螺旋的坐标 [英] Coordinates for clockwise outwards spiral

问题描述

我正在尝试使用Haskell使我认为是所谓的Ulam螺旋线. 它需要以顺时针方向向外旋转:

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?

推荐答案

首先让我们看一下螺旋方向的样子:

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

我们可以重复一次，每次将n加2，例如:

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..]

现在，我们可以在此处使用Dir来计算下一个坐标，例如:

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)

我们可以使用 scanl :: (a -> b -> a) -> a -> [b] -> [a] 生成点，例如:

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

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

这将产生一个无限的顺时针螺旋坐标列表.我们可以使用 take :: Int -> [a] -> [a] 提取前 k 个项目:

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)]

这篇关于顺时针向外螺旋的坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！