### re: Challenge - Print Spiral VIEW POST

This was my O(n) prototype in Haskell. Which helped me to find an O(1) solution. It is not very haskellish to iterate many IO actions, but I deliberately chose a Challenge that is not very natural to Haskell. Well, to keep the data structure in O(n) I had to give the data linewise to IO:

``````import Text.Printf

type Size = Int
type Line = Int

spiral :: Size -> Line -> [Int]
spiral n line
-- even spirals add a top line and a right column to the smaller odd spiral
| even n && line == 0 = [sqr-1,      sqr-2      ..     sqr-n]  -- top line
| even n && line > 0  = spiral (n-1) (line-1) ++ [sqr-n-line]
-- odd spirals add a left column and a bottom line to the smaller even spiral
| odd n && line < n-1 = [sqr-2*n+1+line] ++ spiral (n-1) line
| otherwise =           [sqr-n            ..           sqr-1]  -- bottom line
where
sqr = n^2

printLine :: Size -> Line -> IO ()
printLine n l = (putStrLn.unwords.map (printf "%*v" len)) (spiral n l)
where len = (length . show) (n^2-1)

printSpiral :: Size -> IO ()
printSpiral n = mapM_ (printLine n) [0..n-1]

main = printSpiral 10
``````

It catched my eye, that the spiral structure is represented in the 'spiral' function. I was in a veeery playful mood and worked this out much further by embedding the interesting part in an ASCII graphic of the spiral structure: :-)

``````import Text.Printf

type Size = Int
type Line = Int

spiral :: Size -> Line -> [Int]
spiral n line
-- even spirals add a top line and a right column to the smaller odd spiral
--                     +------------------------------+
| even n && line == 0 =     [sqr-1, sqr-2 .. sqr-n]     -- top line
--                     +------------------------+-----+
--                     |                        |     |
--                     |                        |     |
--                     |                        |     |
| even n && line > 0  =  spiral (n-1) (line-1) ++ rce   -- rce: right col element
--                     |                        |     |
--                     |                        |     |
--                     |                        |     |
--                     +------------------------+-----+
--
-- odd spirals add a left column and a bottom line to the smaller even spiral
--
--                     +-----+------------------------+
--                     |     |                        |
--                     |     |                        |
--                     |     |                        |
| odd n && line < n-1 =  lce ++   spiral (n-1) line     -- lce: left col element
--                     |     |                        |
--                     |     |                        |
--                     |     |                        |
--                     +-----+------------------------+
| otherwise =               [sqr-n   ..   sqr-1]         -- bottom line
--                     +------------------------------+
where
sqr = n^2
rce = [sqr - n - line]          -- right column element
lce = [sqr - n - (n-1) + line]  -- left column element

printLine :: Size -> Line -> IO ()
printLine n line = (putStrLn.unwords.map (printf "%*v" len)) (spiral n line)
where len = (length . show) (n^2-1)

printSpiral :: Size -> IO ()
printSpiral n = mapM_ (printLine n) [0..n-1]

main = printSpiral 10
``````

Literate Programming? That's old hat! This is graphical programming! :-D (Don't take me serious.)

Maybe we see some more recursive solutions?

P.S.: Not programming tail recursive (like the above example) is no problem in O(n), but if you aim for O(1) it is a different story.

Six cases, four of them with explicit return values (at the edges), two of them recursive:

``````import Text.Printf

type Size = Int
type Row = Int
type Column = Int

-- top row: count down from sqr - 1 with col
-- right column: count down from sqr - n with row
-- bottom row: count up from sqr - n with col
-- left column: count up from sqr - n - (n - 1) with row

element :: Size -> Row -> Column -> Int
element n row col
| even n && row == 0   = sqr - 1 - col
| even n && col == n-1 = sqr - n - row
| even n               = element (n-1) (row-1) col
| odd n && row == n-1  = sqr - n + col
| odd n && col == 0    = sqr - n - (n-1) + row
| otherwise            = element (n-1) row (col-1)
where sqr = n^2

printElement :: Size -> Row -> Column -> IO ()
printElement n row col = printf ("%*v" ++ end) len (element n row col)
where len = (length . show) (n^2-1)
end = if col == n-1 then "\n" else " "

printSpiral n = sequence_ \$ printElement n <\$> [0..n-1] <*> [0..n-1]

main = printSpiral 10
``````

I didn't expect printing elementwise to be so easy in Haskell. The classical nested for loop for printing 2-dimensional array in one line:

``````printSpiral n = sequence_ \$ printElement n <\$> [0..n-1] <*> [0..n-1]
``````

Lifting the printElement function into the list functor, getting a list of IO actions back and sequencing this list. That is more intuitive to read than what I used to do with the 'unwords' and 'unlines' functions in similar cases.

I do functorial lifting every day, but although I knew of the sequence function, I never found a use case. Until this puzzle came along. :-) Using sequence in similar cases is the lesson I learned here. :-)

But wait!

The sequence function takes a list of IO actions, one for each element of the spiral. So there's a list of size n2 in memory! :-)

The logic of the element function is O(1), the printing function is not.
So, at first, I'm doing it in good old C:

``````#include <stdio.h>
#include <math.h>

int element(int n, int x, int y) {
int sqr = n*n;
if (n%2 == 0) { // even
if (y == 0) return sqr - 1 - x;
if (x == n-1) return sqr - n - y;
return element(n-1,x,y-1);
} // odd:
if (y == n-1) return sqr - n + x;
if (x == 0) return sqr - n - (n - 1) + y;
return element(n-1,x-1,y);
}

int main() {
int n = 10;
int len = ceil(log10(n*n-1));
for (int y=0; y<n; y++){
for (int x=0; x<n; x++) {
printf("%*i ", len, element(n,x,y));
}
printf("\n");
}
}
``````

What was most fun to learn for me, here, was a failure regarding the problem. :-D

Instead of functorial lifting into the list (resulting in O( n2 )) I use the loop function iterateUntilM to iterate the slightly modified printElement function until the spiral is printed: O(1)

``````import Text.Printf (printf)

type Size = Int
type Row = Int
type Column = Int
type Counter = Int

element :: Size -> Row -> Column -> Int
element n row col
| even n && row == 0   = sqr - 1 - col
| even n && col == n-1 = sqr - n - row
| even n               = element (n-1) (row-1) col
| odd n && row == n-1  = sqr - n + col
| odd n && col == 0    = sqr - n - (n-1) + row
| otherwise            = element (n-1) row (col-1)
where sqr = n^2

printElement :: Size -> Counter -> IO Counter
printElement n counter =
printf ("%*v" ++ end) len (element n row col) >> return (counter+1)
where len = (length . show) (n^2-1)
end = if col == n-1 then "\n" else " "
(row,col) = quotRem counter n

printSpiral n = iterateUntilM (>=n^2) (printElement n) 0 >> return ()

main = printSpiral 10
``````

In the printElement function, elements are indexed by a counter from 0 to n2 - 1, their position in the spiral can be derived from the index by division modulo n: (row,col) = quotRem counter n.

Code of Conduct Report abuse