Reputation: 7096
Code Golf: Easter Spiral
What's more appropriate than a Spiral for Easter Code Golf sessions?
Well, I guess almost anything.
The Challenge
The shortest code by character count to display a nice ASCII Spiral made of asterisks ('*').
Input is a single number, R, that will be the x-size of the Spiral. The other dimension (y) is always R-2. The program can assume R to be always odd and >= 5.
Some examples:
Input
7
Output
*******
* *
* *** *
* * *
***** *
Input
9
Output
*********
* *
* ***** *
* * * *
* *** * *
* * *
******* *
Input
11
Output
***********
* *
* ******* *
* * * *
* * *** * *
* * * * *
* ***** * *
* * *
********* *
Code count includes input/output (i.e., full program). Any language is permitted.
My easily beatable 303 chars long Python example:
import sys;
d=int(sys.argv[1]);
a=[d*[' '] for i in range(d-2)];
r=[0,-1,0,1];
x=d-1;y=x-2;z=0;pz=d-2;v=2;
while d>2:
while v>0:
while pz>0:
a[y][x]='*';
pz-=1;
if pz>0:
x+=r[z];
y+=r[(z+1)%4];
z=(z+1)%4; pz=d; v-=1;
v=2;d-=2;pz=d;
for w in a:
print ''.join(w);
Now, enter the Spiral...
Upvotes: 22
Views: 2109
Answers (10)
Reputation: 35074
Ruby (1.9.2) — 126
f=->s{s<0?[]:(z=?**s;[" "*s]+(s<2?[]:[z]+f[s-4]<<?*.rjust(s))).map{|i|"* #{i} *"}<<z+"** *"}
s=gets.to_i;puts [?**s]+f[s-4]
Perl, where are you? )
Upvotes: 2
Reputation: 16747
C#, 292 262 255 chars
Simple approach: draw the spiral line by line from the outside in.
using C=System.Console;class P{static void Main(string[]a){int A=
1,d=1,X=int.Parse(a[0]),Y=X-2,l=X,t=0,i,z;while(l>2){d*=A=-A;l=l<
4?4:l;for(i=1;i<(A<0?l-2:l);i++){C.SetCursorPosition(X,Y);C.Write
("*");z=A<0?Y+=d:X+=d;}if(t++>1||l<5){l-=2;t=1;}}C.Read();}}
Upvotes: 2
Reputation: 9113
OCaml, 299 chars
Here is a solution in OCaml, not the shortest but I believe quite readable.
It only uses string manipulations using the fact the you can build a spiral by mirroring the previous one.
Let's say you start at with n = 5:
55555
5 5
555 5
Now with n = 7:
7777777
7 7
5 555 7
5 5 7
55555 7
Did you see where all the 5's went ?
Here is the unobfuscated code using only the limited library provided with OCaml:
(* The standard library lacks a function to reverse a string *)
let rev s =
let n = String.length s - 1 in
let r = String.create (n + 1) in
for i = 0 to n do
r.[i] <- s.[n - i]
done;
r
;;
let rec f n =
if n = 5 then
[
"*****";
"* *";
"*** *"
]
else
[
String.make n '*';
"*" ^ (String.make (n - 2) ' ') ^ "*"
] @ (
List.rev_map (fun s -> (rev s) ^ " *") (f (n - 2))
)
;;
let p n =
List.iter print_endline (f n)
;;
let () = p (read_int ());;
Here is the obfuscated version which is 299 characters long:
open String
let rev s=
let n=length s-1 in
let r=create(n+1)in
for i=0 to n do r.[i]<-s.[n-i]done;r
let rec f n=
if n=5 then["*****";"* *";"*** *"]else
[make n '*';"*"^(make (n-2) ' ')^"*"]
@(List.rev_map(fun s->(rev s)^" *")(f(n-2)));;
List.iter print_endline (f(read_int ()))
Upvotes: 3
Reputation: 3150
Java, 265 250 245 240 chars
Rather than preallocating a rectangular buffer and filling it in, I just loop over x/y coordinates and output '*' or ' ' for the current position. For this, we need an algorithm which can evaluate arbitrary points for whether they're on the spiral. The algorithm I used is based on the observation that the spiral is equivalent to a collection of concentric squares, with the exception of a set of positions which all happen along a particular diagonal; these positions require a correction (they must be inverted).
The somewhat readable version:
public class Spr2 {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int cy = (n - 5) / 4 * 2 + 1;
int cx = cy + 2;
for (int y = n - 3; y >= 0; y--) {
for (int x = 0; x < n; x++) {
int dx = cx - x;
int dy = cy - y;
int adx = Math.abs(dx);
int ady = Math.abs(dy);
boolean c = (dx > 0 && dx == dy + 1);
boolean b = ((adx % 2 == 1 && ady <= adx) || (ady % 2 == 1 && adx <= ady)) ^ c;
System.out.print(b ? '*' : ' ');
}
System.out.println();
}
}
}
A brief explanation for the above:
cx,cy = center
dx,dy = delta from center
adx,ady = abs(delta from center)
c = correction factor (whether to invert)
b = the evaluation
Optimized down. 265 chars:
public class S{
public static void main(String[]a){
int n=Integer.parseInt(a[0]),c=(n-5)/4*2+1,d=c+2,e,f,g,h,x,y;
for(y=0;y<n-2;y++){
for(x=0;x<=n;x++){
e=d-x;f=c-y;g=e>0?e:-e;h=f>0?f:-f;
System.out.print(x==n?'\n':(g%2==1&&h<=g||h%2==1&&g<=h)^(e>0&&e==f+1)?'*':' ');
}}}}
Updated. Now down to 250 chars:
class S{
public static void main(String[]a){
int n=Integer.parseInt(a[0]),c=(n-5)/4*2+1,d=c+2,g,h,x,y;
for(y=-c;y<n-2-c;y++){
for(x=-d;x<=n-d;x++){
g=x>0?x:-x;h=y>0?y:-y;
System.out.print(x==n-d?'\n':(g%2==1&&h<=g||h%2==1&&g<=h)^(x<0&&x==y-1)?'*':' ');
}}}}
Shaved just a few more characters. 245 chars:
class S{
public static void main(String[]a){
int n=Integer.parseInt(a[0]),c=(n-5)/4*2+1,d=c+2,g,h,x,y=-c;
for(;y<n-2-c;y++){
for(x=-d;x<=n-d;x++){
g=x>0?x:-x;h=y>0?y:-y;
System.out.print(x==n-d?'\n':(g%2==1&h<=g|h%2==1&g<=h)^(x<0&x==y-1)?'*':' ');
}}}}
Shaved just a few more characters. 240 chars:
class S{
public static void main(String[]a){
int n=Byte.decode(a[0]),c=(n-5)/4*2+1,d=c+2,g,h,x,y=-c;
for(;y<n-2-c;y++){
for(x=-d;x<=n-d;x++){
g=x>0?x:-x;h=y>0?y:-y;
System.out.print(x==n-d?'\n':(g%2==1&h<=g|h%2==1&g<=h)^(x<0&x==y-1)?'*':' ');
}}}}
Upvotes: 3
Reputation: 2660
Ruby, 237 chars
I'm new to code golf, so I'm way off the mark, but I figured I'd give it a shot.
x=ARGV[0].to_i
y=x-2
s,h,j,g=' ',x-1,y-1,Array.new(y){Array.new(x,'*')}
(1..x/2+2).step(2){|d|(d..y-d).each{|i|g[i][h-d]=s}
(d..h-d).each{|i|g[d][i]=s}
(d..j-d).each{|i|g[i][d]=s}
(d..h-d-2).each{|i|g[j-d][i]=s}}
g.each{|r|print r;puts}
Upvotes: 3
Reputation: 133567
Groovy, 373 295 257 243 chars
Tried a recursive approach that builds up squares starting from the most extern one going inside.. I used Groovy.
*********
*********
*********
*********
*********
*********
******* *
*********
* *
* *
* *
* *
* * *
******* *
*********
* *
* ***** *
* ***** *
* *** * *
* * *
******* *
*********
* *
* ***** *
* * * *
* *** * *
* * *
******* *
and so on..
r=args[0] as int;o=r+1;c='*'
t=new StringBuffer('\n'*(r*r-r-2))
e(r,0)
def y(){c=c==' '?'*':' '}
def e(s,p){if (s==3)t[o*p+p..o*p+p+2]=c*s else{l=o*(p+s-3)+p+s-2;(p+0..<p+s-2).each{t[o*it+p..<o*it+p+s]=c*s};y();t[l..l]=c;e(s-2,p+1)}}
println t
readable one:
r=args[0] as int;o=r+1;c='*'
t=new StringBuffer('\n'*(r*r-r-2))
e(r,0)
def y(){c=c==' '?'*':' '}
def e(s,p){
if (s==3)
t[o*p+p..o*p+p+2]=c*s
else{
l=o*(p+s-3)+p+s-2
(p+0..<p+s-2).each{
t[o*it+p..<o*it+p+s]=c*s}
y()
t[l..l]=c
e(s-2,p+1)
}
}
println t
EDIT: improved by just filling squares and then overriding them (check new example): so I avoided to fill just the edge of the rect but the whole one.
Upvotes: 4
Reputation: 116137
Python : 238 - 221 - 209 characters
All comments welcome:
d=input();r=range
a=[[' ']*d for i in r(d-2)]
x=y=d/4*2
s=d%4-2
for e in r(3,d+1,2):
for j in r(y,y+s*e-s,s):a[x][j]='*';y+=s
for j in r(x,x+s*e-(e==d)-s,s):a[j][y]='*';x+=s
s=-s
for l in a:print''.join(l)
Upvotes: 4
Reputation: 118865
F#, 267 chars
A lot of answers are starting with blanks and adding *s, but I think it may be easier to start with a starfield and add whitespace.
let n=int(System.Console.ReadLine())-2
let mutable x,y,d,A=n,n,[|1;0;-1;0|],
Array.init(n)(fun _->System.Text.StringBuilder(String.replicate(n+2)"*"))
for i=1 to n do for j=1 to(n-i+1)-i%2 do x<-x+d.[i%4];y<-y+d.[(i+1)%4];A.[y].[x]<-' '
Seq.iter(printfn"%O")A
For those looking for insight into how I golf, I happened to save a lot of progress along the way, which I present here with commentary. Not every program is quite right, but they're all honing in on a shorter solution.
First off, I looked for a pattern of how to paint the white:
*********
* *
* ***** *
* * * *
* *** * *
* * *
******* *
*********
*6543216*
*1*****5*
*2*212*4*
*3***1*3*
*41234*2*
*******1*
***********
* *
* ******* *
* * * *
* * *** * *
* * * * *
* ***** * *
* * *
********* *
***********
*876543218*
*1*******7*
*2*43214*6*
*3*1***3*5*
*4*212*2*4*
*5*****1*3*
*6123456*2*
*********1*
Ok, I see it. First program:
let Main() =
let n=int(System.Console.ReadLine())
let A=Array2D.create(n-2)n '*'
let mutable x,y,z,i=n-2,n-2,0,n-2
let d=[|0,-1;-1,0;0,1;1,0|] // TODO
while i>0 do
for j in 1..i-(if i%2=1 then 1 else 0)do
x<-x+fst d.[z]
y<-y+snd d.[z]
A.[y,x]<-'0'+char j
z<-(z+1)%4
i<-i-1
printfn"%A"A
Main()
I know that d, the tuple-array of (x,y)-diffs-modulo-4 can later be reduced by x and y both indexing into different portions of the same int-array, hence the TODO. The rest is straightforward based on the visual insight into 'whitespace painting'. I'm printing a 2D array, which is not right, need an array of strings, so:
let n=int(System.Console.ReadLine())
let s=String.replicate n "*"
let A=Array.init(n-2)(fun _->System.Text.StringBuilder(s))
let mutable x,y,z,i=n-2,n-2,0,n-2
let d=[|0,-1;-1,0;0,1;1,0|]
while i>0 do
for j in 1..i-(if i%2=1 then 1 else 0)do
x<-x+fst d.[z]
y<-y+snd d.[z]
A.[y].[x]<-' '
z<-(z+1)%4
i<-i-1
for i in 0..n-3 do
printfn"%O"A.[i]
Ok, now let's change the array of tuples into an array of int:
let n=int(System.Console.ReadLine())-2
let mutable x,y,z,i,d=n,n,0,n,[|0;-1;0;1;0|]
let A=Array.init(n)(fun _->System.Text.StringBuilder(String.replicate(n+2)"*"))
while i>0 do
for j in 1..i-i%2 do x<-x+d.[z];y<-y+d.[z+1];A.[y].[x]<-' '
z<-(z+1)%4;i<-i-1
A|>Seq.iter(printfn"%O")
The let for A can be part of the previous line. And z and i are mostly redundant, I can compute one in terms of the other.
let n=int(System.Console.ReadLine())-2
let mutable x,y,d,A=n,n,[|0;-1;0;1|],
Array.init(n)(fun _->System.Text.StringBuilder(String.replicate(n+2)"*"))
for i=n downto 1 do for j in 1..i-i%2 do x<-x+d.[(n-i)%4];y<-y+d.[(n-i+1)%4];A.[y].[x]<-' '
Seq.iter(printfn"%O")A
downto is long, re-do the math so I can go (up) to in the loop.
let n=int(System.Console.ReadLine())-2
let mutable x,y,d,A=n,n,[|1;0;-1;0|],
Array.init(n)(fun _->System.Text.StringBuilder(String.replicate(n+2)"*"))
for i=1 to n do for j in 1..(n-i+1)-i%2 do x<-x+d.[i%4];y<-y+d.[(i+1)%4];A.[y].[x]<-' '
Seq.iter(printfn"%O")A
A little more tightening yields the final solution.
Upvotes: 6
Reputation: 17900
Python (2.6): 156 chars
r=input()
def p(r,s):x=(i+1)/2;print "* "*x+("*" if~i%2 else" ")*(r-4*x)+" *"*x+s
for i in range(r/2):p(r,"")
for i in range((r-1)/2-1)[::-1]:p(r-2," *")
Thanks for the comments. I've removed extraneous whitespace and used input(). I still prefer a program that takes its argument on the command-line, so here's a version still using sys.argv at 176 chars:
import sys
r=int(sys.argv[1])
def p(r,s):x=(i+1)/2;print "* "*x+("*" if~i%2 else" ")*(r-4*x)+" *"*x+s
for i in range(r/2):p(r,"")
for i in range((r-1)/2-1)[::-1]:p(r-2," *")
Explanation
Take the spiral and chop it in two almost-equal parts, top and bottom, with the top one row bigger than the bottom:
***********
* *
* ******* *
* * * *
* * *** * *
* * * * *
* ***** * *
* * *
********* *
Observe how the top part is nice and symmetrical. Observe how the bottom part has a vertical line down the right side, but is otherwise much like the top. Note the pattern in every second row at the top: an increasing number of stars on each side. Note that each intervening row is exactly the saw as the one before except it fills in the middle area with stars.
The function p(r,s) prints out the ith line of the top part of the spiral of width r and sticks the suffix s on the end. Note that i is a global variable, even though it might not be obvious! When i is even it fills the middle of the row with spaces, otherwise with stars. (The ~i%2 was a nasty way to get the effect of i%2==0, but is actually not necessary at all because I should have simply swapped the "*" and the " ".) We first draw the top rows of the spiral with increasing i, then we draw the bottom rows with decreasing i. We lower r by 2 and suffix " *" to get the column of stars on the right.
Upvotes: 15
Reputation: 36096
Java
328 characters
class S{
public static void main(String[]a){
int n=Integer.parseInt(a[0]),i=n*(n-2)/2-1,j=0,t=2,k;
char[]c=new char[n*n];
java.util.Arrays.fill(c,' ');
int[]d={1,n,-1,-n};
if(n/2%2==0){j=2;i+=1+n;}
c[i]='*';
while(t<n){
for(k=0;k<t;k++)c[i+=d[j]]='*';
j=(j+1)%4;
if(j%2==0)t+=2;
}
for(i=0;i<n-2;i++)System.out.println(new String(c,i*n,n));
}
}
As little as 1/6 more than Python seems not too bad ;)
Here's the same with proper indentation:
class S {
public static void main(String[] a) {
int n = Integer.parseInt(a[0]), i = n * (n - 2) / 2 - 1, j = 0, t = 2, k;
char[] c = new char[n * n];
java.util.Arrays.fill(c, ' ');
int[] d = { 1, n, -1, -n };
if (n / 2 % 2 == 0) {
j = 2;
i += 1 + n;
}
c[i] = '*';
while (t < n) {
for (k = 0; k < t; k++)
c[i += d[j]] = '*';
j = (j + 1) % 4;
if (j % 2 == 0)
t += 2;
}
for (i = 0; i < n - 2; i++)
System.out.println(new String(c, i * n, n));
}
}
Upvotes: 6