# Challenge - Print Spiral

###
Heiko Dudzus
Nov 18 '17
*Updated on Nov 21, 2017 *

## 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.

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.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.If you want to use it in the stable channel, just change the main() to

And no need of

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.

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

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

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 };`

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.

In TypeScript:

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.

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?

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.

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:

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

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:

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:

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

^{2}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:

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

^{2})) I use the loop function iterateUntilM to iterate the slightly modified printElement function until the spiral is printed: O(1)In the printElement function, elements are indexed by a counter from 0 to n

^{2}- 1, their position in the spiral can be derived from the index by division modulo n: (row,col) = quotRem counter n.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.

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.

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.

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

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

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

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

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

allentries of the spiral (being O( n^{2})).The key is to find the mathematical formula between elements of row i and i-1.

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?