Discussion on: 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.

Heiko Dudzus • Nov 26 '17 • Edited

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 n² 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

Heiko Dudzus • Nov 26 '17 • Edited

Instead of functorial lifting into the list (resulting in O( n² )) 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 n² - 1, their position in the spiral can be derived from the index by division modulo n: (row,col) = quotRem counter n.