Print an ascii spiral in O(log n) memory
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
*
*
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 + 1diagonal 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.
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.