Challenge - Print Spiral

Level 1

Write a program in the language of your choice that will display a ”spiral” of n × n numbers.
For example, here’s what the spiral looks like for n = 10:

*Main> printSpiral 10
99 98 97 96 95 94 93 92 91 90
64 63 62 61 60 59 58 57 56 89
65 36 35 34 33 32 31 30 55 88
66 37 16 15 14 13 12 29 54 87
67 38 17  4  3  2 11 28 53 86
68 39 18  5  0  1 10 27 52 85
69 40 19  6  7  8  9 26 51 84
70 41 20 21 22 23 24 25 50 83
71 42 43 44 45 46 47 48 49 82
72 73 74 75 76 77 78 79 80 81
*Main>

Level 2

Make sure your program uses constant (or linear) space. This means, it is not allowed to build an array before printing it (or to build another data structure consuming space with O( n^2 ).

Idea found here: https://www.quora.com/What-are-some-interesting-puzzles-asked-in-computer-science-programming-technical-interviews

Post your solution in the comments below.

Clarification

For a solution in O(n) it is allowed to build a String (or Array,...) for a single line, but still not to build an array containing all information contained in the spiral. Perhaps this fits better to your language of choice or it is good for building a prototype,... Thanks for asking, Evan Oman.

Comments

[Alex Doroshenko]

Got it to Level 2, without using arrays at all.
On level 2 this becomes purely a math problem, so its solutions will be probably pretty similar in any language (except formulas used can be more efficient), but I'm sticking to Rust as I'm learning it right now.

The idea of my solution is that the spiral can be split into series of numbers (called layers here) which run starting from n^2 to n^2 + n, then spiral turns left and runs n numbers more. That 'n' depends on a distance from the spiral center, and starting position will be either top left or bottom right corner, but that's all the difference between them.

#![feature(inclusive_range_syntax)]

const SPIRAL_SIDE: u32 = 10;

fn main() {
    let border = (SPIRAL_SIDE / 2) as i32;
    let (min, max) = if SPIRAL_SIDE % 2 == 0 {
        (-border + 1, border)
    } else {
        (-border, border)
    };

    for y in (min..=max).rev() {
        (min..=max)
            .into_iter()
            .for_each(|x| print!("{:>3} ", number_at(x, y)));
        println!();
    }
}

fn number_at(x: i32, y: i32) -> i32 {
    let distance_from_center = x.abs().max(y.abs());

    if y > -x {
        calculate_number_for(x, y, 2 * distance_from_center - 1)
    } else {
        calculate_number_for(-x, -y, 2 * distance_from_center)
    }
}

fn calculate_number_for(x: i32, y: i32, layer_id: i32) -> i32 {
    let bottom_right_num = layer_id.pow(2);
    let top_right_num = bottom_right_num + layer_id;

    let dist_from_top_right = (x - y).abs();

    if y <= x {
        top_right_num - dist_from_top_right
    } else {
        top_right_num + dist_from_top_right
    }
}

You can run this script here play.rust-lang.org/?gist=1548e5d81..., spiral size can be changed by adjusting the const SPIRAL_SIDE at the top.

[Ignacio Sniechowski]

If you want to use it in the stable channel, just change the main() to

fn main() {
    let border = (SPIRAL_SIDE / 2) as i32;
    let (min, max) = if SPIRAL_SIDE % 2 == 0 {
        (-border + 1, border + 1)
    } else {
        (-border, border)
    };

    for y in (min..max).rev() {
        (min..max)
            .into_iter()
            .for_each(|x| print!("{:>3} ", number_at(x, y)));
        println!();
    }
}

And no need of

#![feature(inclusive_range_syntax)]

[Heiko Dudzus]

In my first reflections of the code, I picked numbers in the mirrored case where 'bottom_right_num' was top left and 'top_right_num' was bottom left. Picking one with y > -x (above the secondary diagonal) it was easier to understand. Then I could transfer it to the mirrored case. Different names in different cases perhaps could be easier to understand, on the other hand I had kind of bad luck with my choice of examples. ;)

Thanks for your solution and for the link to the playground.

[Alex Doroshenko]

Well, when I finally got the pattern with numbers, it was at the top-right side, so the code kind of reflects this 🙂

[Heiko Dudzus]

Seems like Rust functions return the final statement (for each case) without a return keyword? Edit: Ah, I see, implicit returns.

[Alex Doroshenko]

Yes, final statement is returned. Actually, almost anything with a block in Rust yields a final block statement as a value, so it's possible, for example, write something like let x = if y < 0 { -y } else { y };

[Heiko Dudzus]

That's quite common in functional programming, btw. When I read about Rust in early 2016, the most impressive and likeable idea was borrowing. And, of course, pattern matching. I like to see some Rust here.

[RevanProdigalKnight]

In TypeScript:

type int = number; // For clarity (and brevity)

const
  numberFor = (x: int, y: int, layer: int): int => {
    const
      bottomRight: int = layer ** 2,
      topRight: int = bottomRight + layer,
      distance: int = Math.abs(x - y);

    return topRight + ((y <= x) ? -distance : distance);
  },
  numberAt(x: int, y: int): int => {
    const distance: int = 2 * Math.max(Math.abs(x), Math.abs(y));

    return (y > -x) ?
      numberFor( x,  y, distance - 1) :
      numberFor(-x, -y, distance);
  },
  printSpiral = (size: int): void => { // Where `size` is the length of each side
    const
      // Figure out biggest possible number for spiral number spacing
      maxNumSize: int = `${size ** 2}`.length,
      // Repeat that for all the numbers that will be printed each line
      lineFormat: string = new Array(size).fill(`%${maxNumSize}d`).join(' '),
      // Now figure out the actual bounds to use
      max: int = (size / 2) | 0, // Shorthand for `Number.parseInt()`
      min: int = (size % 2 === 0) ? (-max + 1) : -max;

    // If running on node.js this can be circumvented by using non-console logging
    let line: int[] = []; // Damn `console.log` for always printing a newline

    // It would be nice if JS had a range operator like python...
    for (let y = max; y >= min; y--) {
      for (let x = min; x <= max; x++) {
        line.push(numberAt(x, y));
      }
      console.log(lineFormat, ...line);
      line = [];
    }
  };

I've tested the number spacing out to an 82x82 spiral, and assume that it would work further than that as well, but I was running out of horizontal screen space.

[Heiko Dudzus]

As I can see, you have written all the needed logic for a solution in O(1), but without node.js you need to assemble a line first, before printing it entirely. Something like this was my intention for allowing O(n).

Of course, your program consumes linear space, but I think the core concept can be regarded, like Alexey's, as O(1) solution.

I agree to your comment about ranges, by the way. Would you like to submit Python code?

[RevanProdigalKnight]

I'd like to, but it's been a while since I last used Python and I've forgotten most of the rest of the nice syntax features.

[Heiko Dudzus]

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]

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.

[Tobias Salzmann]

A O(1) (or rather O(log log n), because numbers need space) solution in spirit, but I was not in the mood for side effects. Essentially doing recursion per row. I chose to index rows such that 0 is in row 0.

object Spiral extends App {

  type Row = Seq[Int]
  type Matrix = Seq[Row]

  sealed trait Parity
  case object Even extends Parity
  case object Odd extends Parity

  def parity(n: Int) = if(n % 2 == 0) Even else Odd

  def spiralRow(n: Int)(rowIndex: Int): Row = {

    def lastRow(n: Int) = (n * n - n) to (n * n - 1)
    def firstRow(n: Int) = (n * n - 1) to (n * n - n) by -1

    val first = -n / 2
    val last = n / 2

    (parity(n), rowIndex) match {
      case (Even, `first`)  => firstRow(n)
      case (Even, _) => spiralRow(n - 1)(rowIndex) :+ ((n * n) - n - (n / 2) - rowIndex)
      case (Odd, `last`) => lastRow(n)
      case (Odd, _) => ((n - 1) * (n - 1) + rowIndex + (n / 2)) +: spiralRow(n - 1)(rowIndex)
    }
  }


  def spiral(n: Int): Matrix = {
    (0 until n)
      .map(_ - n / 2)
      .map(spiralRow(n))
  }

  def padTo(length: Int)(k: Int) = s"${" " * (length - k.toString.length)}${k.toString}"

  def printSpiral(n: Int): Unit = {
    val maxDigits = (n * n - 1).toString.length
    spiral(n: Int)
      .map(_.map(padTo(maxDigits)).mkString(" "))
        .foreach(println)
  }

  printSpiral(10)
}

[Stefan Dangl]

It does not have to be a purely math problem on Level 2.

I implemented this recursive approach which prepends and appends to lines of smaller spirals.

Of course you may ask, if using the call-stack isn't similar to a data structure, and from a theoretical point of view (Touring machine) it is. So here is a version without recursion using tailrec.

And then there is also the solution of not using any intermediate data structure at all and printing directly

Sorry for not having enough time to write really nice code.

[Heiko Dudzus]

Recursion was the way to go for me, too, because of the recursive structure of spirals. Really nice to see your recursive solutions! :)

I shared your view about how collecting data on the call stack is analogous to building a data structure regarding space complexity, and came to your conclusion to use tail recursion.

[Alex Pliutau]

Interesting, created this challenge in my Go challenges collection, waiting for a solution github.com/plutov/practice-go/tree...

[Heiko Dudzus]

I could contribute a solution that's different to the ones we have seen here, so far. I feel like I shouldn't, at this point. :-D

[Alex Pliutau]

You should! I usually waiting 7 days for all PRs and select the fastest one.

[Lluís Josep Martínez]

The key is to find the mathematical formula between elements of row i and i-1.

[Heiko Dudzus]

This is generally true. I'm not sure if this approach reflects the structure of the spiral so well that it leads easily to a solution. I may be wrong on that.

Are you developing code?

[Evan Oman]

Should the space complexity be constant or linear? Probably O(1) since O(n) would allow you to build an array.

[Heiko Dudzus]

I wanted to allow to build up one single line before printing. I think that would result in a space complexity of O(n). That allows to build an array, but not to build an array containing all entries of the spiral (being O( n² )).