Discussion on: Challenge - Print Spiral

[Heiko Dudzus]

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]

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.