Print an ascii spiral in O(log n) memory

Question

You may write a program or function that receives an odd, positive integer n, where n >= 3, as either a function argument, command line arguments, or on STDIN (or equivalent for your system), and prints to STDOUT (or system equivalent) an ASCII spiral that spins inward clockwise where the top edge is exactly n characters long. The first right edge should be n+1 characters long, obviously. For instance,

Input:

11

Output:

***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

The catches:

• Your program must use no more than O(log n) memory.
• Your program may only print the characters * (ASCII 42), (ASCII 32), <CR> (ASCII 13) and <LF> (ASCII 10).
• Your program must print the string, not return it from the function.
• The Big-O restriction is only on memory, there are no restrictions on runtime.
• A trailing newline is optional.
• If your language does not support large integer types, you do not have to support higher than what it does support, but you may not use this as a trick to say "oh, well, I don't have to support above X so I can just make a huge array the maximum size every time"

Standard loopholes are banned, as usual.

Answer 1

C, 125 121 bytes

Golfed version This has no variable k. The variable k is used in the ungolfed version just to aid readability. Also for loop conditionals are rearranged and one set of unnecessary {} removed. Another set of {} can be removed by migrating puts("") inside the brackets of the j loop in the initialization position, but this would mean a newline at the beginning of the output, so I haven't done it.

f(n){int i,j;n/=2;for(i=-n-2;i++-n-1;){if(i){for(j=-n-1;j++-n;)putchar(32+10*(n+(j*j<i*i?i:j+(i!=j|i>0))&1));puts("");}}}

Prints an n wide by n+1 high spiral like the example.

Explanation

Basically I halve the value of n (rounding down) and run two loops: an outer one i from -n/2-1 to n/2+1 to print the rows (i=0 is suppressed so we get n+1 rows) and an inner one j from (-n/2 to n/2 to print the characters.) We use expression & 1 to print stripes, and the condition j*j<i*i to decide whether to print vertical or horizontal stripes (vertical at the sides where absolute magnitude of i is larger, and horizontal at the top and bottom.) An adjustment +n is required to help with the correct termination depending on whether n/2 is odd or even.

k is normally 1, and provides an adjustment for the fact that the absolute values of i range from 1 to n/2+1 while the absolute values of j range from 0 to n/2. If k was always 1 we would get concentric rectangles, but it is inverted to 0 when i==j&i<=0 so that a diagonal row of cells is inverted, producing the spiral.

ungolfed in test program

f(n){
  int i,j,k;
  n/=2;
  for(i=-n-1;i<=n+1;i++){
    if(i){
       for(j=-n;j<=n;j++){
           k=i!=j|i>0;
           putchar(32+10*(n+(j*j<i*i?i:k+j)&1));
         }
       puts("");
     }
  }
} 

int m;
main(){
  scanf("%d",&m);
  f(m);
}

Output

11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

3
***
  *
* *
***

1
*
*

Answer 2

C, 118 bytes

m,p,x,y,d;f(n){for(m=n++/2;p<n*n;x=p%n-m,y=p++/n-m,d=y==x+1&x<0,y-=y>0,d+=x*x>y*y?x:y,putchar(x>m?10:(d+m)%2?32:42));}

Code before final golfing:

#include <stdio.h>

int m, p, x, y, d;

int f(int n) {
    for (m = n++ / 2; p < n * n; ) {
        x = p % n - m;
        y = p++ / n - m;
        d = y == x + 1 && x < 0;
        y -= y > 0;
        d += x * x > y * y ? x : y;
        if (x > m) {
            putchar(10);
        } else if ((d + m) % 2) {
            putchar(32);
        } else {
            putchar(42);
        }
    }

    return 0;
}

The key observation is that the pattern is almost a series of concentric squares. With a couple of slight wrinkles:

• The y-size is one larger than the x-size. This is corrected by subtracting 1 from y for the lower half, which essentially repeats the middle row.
• To turn the rectangles into a spiral, the pixels along the y = x + 1 diagonal need to be inverted up to the middle of the shape.

For the rest, the code is simply looping over all positions, calculating the Chebyshev distance from the center for each position, and emitting one of the two characters depending on the distance being even or odd. And emitting a newline for the last position of each line.

Since there are only a few scalar variables, and characters are emitted one by one, memory usage is obviously constant.

Answer 3

C++, 926 bytes

#include<iostream>
#include<string>
#include<math.h>
#define S string
using namespace std;S N(S x,int y){S z="";for(int q=0;q<y;q++){z+=x;}return z;}int main(){int n=0,t=0,g=0,fi=1;cin>>n;int t1[]={0,0,n,0};int t2[]={0,n-2,n-2,1};for(int k=0;k<n+1;k++){if((k>(n-2)/2)&&(k<(n+5)/2)){if(g==0){S d,e;if(!((n+1)%4)){cout<<N("* ",t2[0])<<"  *"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t2[0])<<"***"<<N(" *",t2[0])<<endl;t2[2]=n-8-(n-11);t1[2]=n-4-(n-11);t1[0]--;t2[3]--;t1[3]-=2;}else{cout<<N("* ",t1[0])<<"***"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t1[0])<<"*  "<<N(" *",t2[0])<<endl;t2[0]--;t1[2]+=2;t2[2]+=6;t1[3]--;t2[1]-=2;t2[3]-=2;}fi=0;}g=5;}else{t=1-t;int*tR;tR=t?t1:t2;cout<<N("* ",tR[0])<<N(t?"*":" ",tR[2])<<N(" *",tR[3])<<endl;if(fi){if(t){t1[0]+=k==0?0:1;t1[2]-=k==0?2:4;t1[3]++;}else{t2[0]++;t2[2]-=4;t2[3]++;}}else{if(t){t1[0]--;t1[2]+=4;t1[3]--;}else{t2[0]--;t2[2]+=4;t2[3]--;}}}}return 0;}

This is not elegant, but it doesn't take up much memory for large n. Furthermore, there are (almost certainly) about 20 characters that can be further golfed, but I can't stand to look at it anymore.

Short Explanation:

This splits the lines in the spirals into two types: the ones with ****** in the middle, and the ones with \s\s\s\s\s in the middle. Then it is clear that each line is composed of several "* "s, the middle, and some " *". Figuring out exactly how many of each thing is simple if you look at the pattern for long enough. The tricky thing was printing the center of the spiral which I basically hard coded using a conditional. This ended up being useful because the *** and \s\s\s lines switch being odd/even there.

Tests:

Input: 55 (I think the big ones look coolest)

Output:

*******************************************************
                                                      *
***************************************************** *
*                                                   * *
* ************************************************* * *
* *                                               * * *
* * ********************************************* * * *
* * *                                           * * * *
* * * ***************************************** * * * *
* * * *                                       * * * * *
* * * * ************************************* * * * * *
* * * * *                                   * * * * * *
* * * * * ********************************* * * * * * *
* * * * * *                               * * * * * * *
* * * * * * ***************************** * * * * * * *
* * * * * * *                           * * * * * * * *
* * * * * * * ************************* * * * * * * * *
* * * * * * * *                       * * * * * * * * *
* * * * * * * * ********************* * * * * * * * * *
* * * * * * * * *                   * * * * * * * * * *
* * * * * * * * * ***************** * * * * * * * * * *
* * * * * * * * * *               * * * * * * * * * * *
* * * * * * * * * * ************* * * * * * * * * * * *
* * * * * * * * * * *           * * * * * * * * * * * *
* * * * * * * * * * * ********* * * * * * * * * * * * *
* * * * * * * * * * * *       * * * * * * * * * * * * *
* * * * * * * * * * * * ***** * * * * * * * * * * * * *
* * * * * * * * * * * * *   * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * {-- my program adds a space here btw
* * * * * * * * * * * * * *** * * * * * * * * * * * * *
* * * * * * * * * * * * *     * * * * * * * * * * * * *
* * * * * * * * * * * * ******* * * * * * * * * * * * *
* * * * * * * * * * * *         * * * * * * * * * * * *
* * * * * * * * * * * *********** * * * * * * * * * * *
* * * * * * * * * * *             * * * * * * * * * * *
* * * * * * * * * * *************** * * * * * * * * * *
* * * * * * * * * *                 * * * * * * * * * *
* * * * * * * * * ******************* * * * * * * * * *
* * * * * * * * *                     * * * * * * * * *
* * * * * * * * *********************** * * * * * * * *
* * * * * * * *                         * * * * * * * *
* * * * * * * *************************** * * * * * * *
* * * * * * *                             * * * * * * *
* * * * * * ******************************* * * * * * *
* * * * * *                                 * * * * * *
* * * * * *********************************** * * * * *
* * * * *                                     * * * * *
* * * * *************************************** * * * *
* * * *                                         * * * *
* * * ******************************************* * * *
* * *                                             * * *
* * *********************************************** * *
* *                                                 * *
* *************************************************** *
*                                                     *
*******************************************************

Input: 3

Output:

***
  *
* * 
***

Note: I am not a computer scientist/CS student, and I don't know how to prove that this uses O(log n) memory. I can only work out what to do based on the links in the question. I would be grateful if someone could confirm/deny if this answer is valid. My logic for this answer's validity is that it never stores any variable of size based on n except the input itself. Instead, a for loop that runs n times computes integer values based on n. There are the same number of those values regardless of the input.

Note2: This doesn't work for n=1 because of my method of dealing with the middle. This would be easy to fix with conditionals, so if anyone is within a few characters of my answer, I'll fix it ;)

Play with it on ideone.

Answer 4

Haskell, 151 bytes

(#)=mod
f n=[[if y<= -(abs$x+1)||y>abs x then r$y#2/=n#2 else r$x#2==n#2|x<-[-n..n]]|y<-[-n-1..n+1],y/=0]
r b|b='*'|1<2=' '
p=putStr.unlines.f.(`div`2)

Usage example:

*Main> p 9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

*Main> p 11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

Thanks to Haskell's laziness this runs within constant memory. It uses the obvious approach, i.e. looping over y and x and choosing between * and , depending on

• if the current position is above or below a diagonal
• x resp. y is even or odd
• n/2 is even or odd

Answer 5

Common Lisp - 346

(lambda(n &aux(d 0))(tagbody $ #6=(#7=dotimes(i n)#4=(princ"*"))#2=(#7#(i d)#5=(princ" ")#4#)#3=(terpri)#1=(#7#(i d)#4##5#)(when(> n 0)(#7#(i(1- n))#5#)#4#)#2##3#(when(> n 3)#1##4##4#(incf d)(decf n 4)(go $))(go /)@(decf d)(incf n 4)(when(> n 3)#2##5##4##3#)/ #1#(when(> n 0)#4#)(when(> n 1)(#7#(i(- n 2))#5#)#4#)#2##3##1##6#(when(> d 0)(go @))))

Iterative solution with constant memory usage. The above makes heavy uses of #n= and #n# reader variables. Even though there are more direct approaches, here I started with a recursive function and modified it to simulate recursion with goto statements: this is probably unreadable.

Output for all input values from 0 to 59.

Original recursive version, with debugging informations

(note: terpri means newline)

(defun spiral (n &optional (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (when (= d 0) (prefix))
    (dotimes (i n) (princ "c"))
    (postfix)
    (terpri)

    (prefix)
    (when (> n 0)
      (dotimes (i (1- n)) (princ " "))
      (princ "d"))
    (postfix)
    (terpri)

    (when (> n 3)
      (prefix)
      (princ "**")
      (spiral (- n 4) (1+ d))
      (postfix)
      (princ " f")
      (terpri))

    (prefix)
    (when (> n 0)
      (princ "g"))

    (when (> n 1)
      (dotimes (i (- n 2)) (princ " "))
      (princ "h"))
    (postfix)
    (terpri)

    (prefix)
    (dotimes (i n) (princ "i"))
    ))

For example:

(spiral 8)

   8   0 | cccccccc
   8   0 |        d
   8   0 | **cccc b
   4   1 | a    d b
   4   1 | a ** b b
   0   2 | a a  b b
   0   2 | a a  b b
   0   2 | a a  b f
   4   1 | a g  h b
   4   1 | a iiii f
   8   0 | g      h
   8   0 | iiiiiiii

See also this paste with all results from 0 to 59 (not the same as above, this one is more verbose).

Iterative version, with debugging informations

(defun spiral (n &aux (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (tagbody
     step-in
       (when (= d 0) (prefix))
       (dotimes (i n) (princ "c"))
       (postfix)
       (terpri)

       (prefix)
       (when (> n 0)
         (dotimes (i (1- n)) (princ " "))
         (princ "d"))
       (postfix)
       (terpri)

       (when (> n 3)
         (prefix)
         (princ "**")

         (incf d)
         (decf n 4)
         (go step-in))

       (go skip)

     step-out
       (decf d)
       (incf n 4)
       (when (> n 3)
         (postfix)
         (princ " f")
         (terpri))

     skip
       (prefix)
       (when (> n 0)
         (princ "g"))

       (when (> n 1)
         (dotimes (i (- n 2)) (princ " "))
         (princ "h"))
       (postfix)
       (terpri)

       (prefix)
       (dotimes (i n) (princ "i"))
       (when(> d 0)(go step-out)))))

Answer 6

CJam, 72 bytes

li_2/:M;)__*{1$mdM-\M-_2$)=2$0<*@_*@_0>-_*e>mQ_M>2*@@+M+2%+'#S+N+N+=o}/;

This is fairly direct conversion of my C solution to CJam. Not as short as you would normally expect from a CJam solution, but this one really suffers from the memory restriction. The common benefits of building up results on the stack that gets dumped automatically at the end, and using fancy list/string operations, all go out the window. This generates and outputs the solution one character at a time. The stack only contains a few integers at runtime, and is empty at the end.

Even though it's not a great display of using a golfing language, it's still considerably shorter than the C code just because the notation is more compact.

Explanation:

li    Get input n.
_2/   Calculate n/2.
:M;   Store it in variable M
)__*  Calculate (n+1)*(n+1), which is the total number of output characters.
      Also keep a copy of n+1 on the stack.
{     Start loop over output character positions.
  1$md  Calculate divmod of position with n+1. This gives y and x of position.
  M-    Subtract M from x.
  \M-   Subtract M from y.
  _     Copy y.
  2$)   Calculate x+1.
  =     Check if y == x+1
  2$0<  Check if x < 0.
  *     Multiply the two check results. This is the result of the flip
        condition for the top-left diagonal to turn the rectangles into a spiral.
  @_*   Calculate x*x.
  @_    Get y to top of stack, and copy it.
  0>-   Subtract 1 from y if it is in the bottom half.
  _*    Calculate y*y.
  e>    Take maximum of x*x and y*y...
  mQ    ... and calculate the square root. This is the absolute value of the
        larger of the two.
  _M>   Check if the value is greater M, which means that this is the
        position of a line end.
  2*    Multiply by 2 so that we can add another condition to it later.
  @     Get result of diagonal flip condition to the stack top.
  @     Get max(x,y) to the top.
  +M+   Add the two, and add M to the whole thing. This value being even/odd
        determines if the output is a # or a space.
  2%    Check if value is odd.
  +     Add to line end condition to get a single ternary condition result.
  '#S+N+N+
        Build string "# \n\n".
  =     Use the condition result to pick the output character out of the string.
  o     Output the character.
}/    End loop over output characters.
;     Pop n+1 value off stack, to leave it empty.