loading...

re: Challenge - Print Spiral VIEW POST

FULL DISCUSSION
 

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