顺时针向外螺旋的坐标

Question

我正在尝试使用 Haskell 制作我认为称为 Ulam 螺旋的东西。需要顺时针向外旋转：

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

对于我尝试创建坐标的每一步，函数都会被赋予一个数字和 return 螺旋坐标到输入数字的长度，例如：

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)

我见过 Looping in a spiral 解决方案，但这是逆时针的，它的输入需要矩阵的大小。

我还找到了 this 代码，它可以满足我的需要，但它似乎是逆时针方向前进，而不是顺时针方向前进:(

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)

经过大量实验后，我似乎无法更改旋转或开始步进方向，有人可以指出我正确的方法或不使用列表理解的解决方案吗，因为我发现它们很难解码？

Answer 1

以下解决方案的想法是，我们不会尝试直接生成坐标，而是查看从一个点到下一个点的方向。如果这样做，您会注意到从第一点开始，我们向右走 1 倍，向下走 1 倍，向左走 2 倍，向上走 2 倍，向右走 3 倍，向下走 3 倍，向左走 4 倍……然后这些可以是分为方向和重复次数:

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

这实际上给了我们两个非常简单的模式！方向只是旋转 > 到 v 到 < 到 ^ 到 >，而重复次数每 2 次增加 1。一旦我们用这些模式制作了两个无限列表，就可以将它们组合在一起以获得一个完整的方向列表 >v<<^^>>>vvv<<<<…，然后可以对其进行迭代以获得坐标值。

现在，我一直认为仅仅给别人一堆代码作为解决方案并不是最好的学习方式，所以我高度鼓励您尝试实施在查看下面的解决方案之前，请先自己提出上述想法。

欢迎回来（如果您确实尝试过自己实施）。现在：我自己的解决方案。首先，我为无限流定义了一个 Stream 数据类型：

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

严格来说，我不需要流； Haskell 的预定义列表完全可以完成这项任务。但是我碰巧喜欢流，它们使一些模式匹配变得更容易一些（因为我不必处理空列表）。

接下来，我定义了一个方向类型，以及一个指定它们如何与点交互的函数：

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

现在我继续讨论问题本身。我将定义两个流——一个用于方向，一个用于每个方向的重复次数：

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)

此时我们需要一个函数来将流中的每个元素复制特定次数：

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

这为方向流提供了 replicateS dirStream numRepsStream。现在我们只需要一个函数将这些方向转换为坐标，我们就解决了这个问题：

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

不幸的是，打印无限流有点不方便，所以下面的函数对于调试和打印目的很有用：

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

Answer 2

让我们先来看看螺旋的方向是怎样的：

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

我们可以按如下顺序拆分：

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

我们可以重复，每次递增 n 两倍，例如：

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来计算下一个坐标，如：

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]来生成点，比如：

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

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

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

顺时针向外螺旋的坐标

Coordinates for clockwise outwards spiral

haskell

recursion

spiral