loading...

### re: Challenge - Print Spiral VIEW POST

re: 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 delibe...

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)
import Control.Monad.Loops (iterateUntilM)

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