Code De Golf: Spirale D'Ulam
Le Défi
Le code le plus court par nombre de caractères pour sortir la spirale D'Ulam avec une taille de spirale donnée par l'entrée de l'utilisateur.
La spirale D'Ulam est une méthode pour cartographier les nombres premiers. La spirale commence à partir du nombre 1 étant au centre (1 n'est pas un premier) et générant une spirale autour d'elle, marquant tous les nombres premiers comme le caractère '*
'. Non, le premier sera imprimé comme un espace ''.
Texte Alt http://liranuna.com/junk/ulam.gif
Cas de Test
Input:
2
Output:
* *
*
*
Input:
3
Output:
* *
* *
* **
*
*
Input:
5
Output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Le nombre de codes inclut l'entrée / sortie (c'est-à-dire le programme complet).
19 réponses
Golfscript-92 Caractères
~.(: S+,: R{S\ -|/; R{S-:$|>' *'1/[|$.|]2/@:d|~)$
97 les caractères
~.(: S+,: R{S\ -|/; R{S-:$|>' *'1/[|$.|]2/@:d|~)${$\%!},!=}%n}%
99 les caractères
~.(: S+, {S -}%: R {~):/; R{:$|>' *'1/[|$.|]2/@:d|~)${$\%!},!=}%n}%
100 les caractères
~: S. (+, {S ( - }%: R {~):|; R {:$/>' *'1/[|$.|]2/@:d|~)${$\%!},!=}%n}%
101 les caractères
~: S. (+, {S ( - }%: R {~): v; R {:$V>: d; '* ' 1/[v$.v] 2 / V~)${$\%!},!=}%n}%
Python-203 Caractères
_________________________________________________________
/x=input();y=x-1;w=x+y;A=[];R=range;k,j,s,t=R(4) \
| for i in R(2,w*w): |
| A+=[(x,y)]*all(i%d for d in R(2,i)) |
| if i==s:j,k,s,t=k,-j,s+t/2,t+1 |
| x+=j;y+=k |
| for y in R(w):print"".join(" *"[(x,y)in A]for x in R(w)) |
\_________________________________________________________/
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
x=input();y=x-1;w=x+y
A=[];R=range;k,j,s,t=R(4)
for i in R(2,w*w):
A+=[(x,y)]*all(i%d for d in R(2,i))
if i==s:j,k=k,-j;s,t=s+t/2,t+1
x+=j;y+=k
for y in R(w):print"".join(" *"[(x,y)in A]for x in R(w))
Comment cela fonctionne
L'idée est de remplir A avec des coordonnées x,y qui doivent être imprimées comme '* '
L'algorithme commence à la cellule correspondant à 2, de sorte que le cas particulier de tester 1 pour la primalité est évité.
x,y est la cellule d'intérêt
j, k Gardez une trace de si nous avons besoin d'inc ou dec x ou y pour arriver à la cellule suivante
s est la valeur de i au coin suivant
t garde la trace de l'incrément à s
Tous (I % D Pour d dans R (2,i)) la primalité vérifie-t-elle
La dernière ligne est plutôt maladroite. Il itère sur toutes les cellules et décide de placer un espace ou un astérisque
MATLAB: 182 167 156 les caractères
Script ulam.m
:
A=1;b=ones(1,4);for i=0:(input('')-2),c=b(4);b=b+i*8+(2:2:8);A=[b(2):-1:b(1);(b(2)+1:b(3)-1)' A (b(1)-1:-1:c+1)';b(3):b(4)];end;disp(char(isprime(A)*10+32))
Et formaté un peu plus agréable:
A = 1;
b = ones(1,4);
for i = 0:(input('')-2),
c = b(4);
b = b+i*8+(2:2:8);
A = [b(2):-1:b(1); (b(2)+1:b(3)-1)' A (b(1)-1:-1:c+1)'; b(3):b(4)];
end;
disp(char(isprime(A)*10+32))
Cas de Test:
>> ulam
2
* *
*
*
>> ulam
3
* *
* *
* **
*
*
>> ulam
5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
C, 208 206 201 200 199 196 194 193 194 193 188 185 183 180 176 Octets
(si les nouvelles lignes sont supprimées):
main(int u,char**b){
for(int v,x,y,S=v=**++b-48;--v>-S;putchar(10))
for(u=-S;++u<S;){
x=u;y=v;v>-u^v<u?:(x=v,y=u);
x=4*y*y-x-y+1+2*(v<u)*(x-y);
for(y=1;x%++y;);
putchar(y^x?32:42);}}
Compilé avec
> gcc -std=c99 -o ulam ulam.c
Attention. Ce programme est lent, car il fait une section de première instance jusqu'à 2 ^ 31. Mais est produit la sortie requise:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
En C joliment formaté et avec redondant #comprend:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
int u,v,x,y,d,S = atoi(argv[1]);
/* v is the y coordinate of grid */
for (v=S; v>=-S; --v)
/* u is the x coordinate. The second operand (!putchar...) of the boolean or
* is only ececuted a a end of a x line and it prints a newline (10) */
for (u=-S; u<=S || !putchar(10); ++u) {
/* x,y are u,v after "normalizing" the coordintes to quadrant 0
normalizing is done with the two comparisions, swapping and and
an additional term later */
d = v<u;
x=u;
y=v;
if (v<=-u ^ d) {
x=v;
y=u;
}
/* reuse x, x is now the number at grid (u,v) */
x = 4*y*y -x-y+1 +2*d*(x-y);
/* primality test, y resused as loop variable, won't win a speed contest */
for (y=2; y<x && x%y; ++y)
;
putchar(y!=x?' ':'*');
}
}
Il fonctionne en transformant les coordonnées de la grille au nombre approprié, puis en effectuant le test de primalité, au lieu de dessiner de manière serpent. Les différentes équations pour les quatre " quadrants "peuvent être réduites en une seule avec l'échange x et y et un terme supplémentaire pour"comptage en arrière".
Ruby 1.8.7, 194 caractères
n=2*gets.to_i-1
r=n**2
l,c=[nil]*r,r/2
r.times{|i|l[c]=i+1;c=i==0||l[c-n]&&!l[c+1]?c+1:l[c-1]&&!l[c-n]?c-n:l[c+n]?c-1:c+n}
r.times{|i|print"1"*l[i]!~/^1?$|^(11+?)\1+$/?'*':' ',i%n==n-1?"\n":''}
Pour une raison quelconque, ruby1. 9 veut un autre espace sur la ligne 4:
r.times{|i|l[c]=i+1;c=i==0||l[c-n]&&!l[c+1]?c+1:l[c-1]&&!l[c-n]?c-n :l[c+n]?c-1:c+n}
Python-171
Le C de Drhirsch porté en python.
S=input();R=range(-S+1,S)
for w in R:
p="";v=-w
for u in R:d=v<u;x,y=[(u,v),(v,u)][(w>=u)^d];x=4*y*y-x-y+1+2*d*(x-y);p+=" *"[(x>1)*all(x%f for f in range(2,x))]
print p
echo 20 |python ulam.py * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
MATLAB, 56 caractères
Basé sur la solution @gnovice , améliorée en utilisant la fonction spiral de MATLAB:)
disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
Des Cas De Test:
>> disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
2
* *
*
*
>> disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
3
* *
* *
* **
*
*
>> disp(char(isprime(flipud(spiral(2*input('')-1)))*10+32))
5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
J solution: 197 173 165 161 octets (jusqu'à présent)
cela n'utilise pas la méthode mentionnée dans les commentaires à L'OP
p=:j./<.-:$g=:1$~(,])n=:<:+:".1!:1]3
d=:j.r=:1
(m=:3 :'if.y<*:n do.if.0=t=:<:t do.d=:d*0j1[t=:<.r=:r+0.5 end.m>:y[g=:y(<+.p=:p+d)}g end.')t=:2
1!:2&2(1 p:g){' *'
Mon premier code golf!
Ruby, 309 301 283 271 265 les caractères
s=gets.to_i;d=s*2-1;a=Array.new(d){' '*d}
e=d**2;p='*'*e;2.upto(e){|i|2.upto(e/i){|j|p[i*j-1]=' '}};p[0]=' '
s.times{|i|k=s-i-1;l=2*i;m=l+1;o=l-1
m.times{|j|n=j+k;a[k][n]=p[l**2-j];a[n][k]=p[l**2+j];a[k+l][n]=p[m**2-m+j]}
l.times{|j|a[j+k][k+l]=p[o**2+o-j]}}
puts a
Python 2.x, 220C 213C 207C 204C 201C 198C 196C 188C
Merci Spécial à gnibbler pour obtenir des conseils dans #stackoverflow
sur Freenode. La sortie comprend un retour à la ligne de début et de fin.
import math
v=input()*2
w=v-1
a=['\n']*w*v
p=w*v/2
for c in range(1,w*w):a[p]=' *'[(c>1)*all(c%d for d in range(2,c))];x=int(math.sqrt(c-1));p+=(-1)**x*((x*x<c<=x*x+x)*w+1)
print''.join(a)
(Python 3 compatibilité nécessiterait supplémentaires caractères; il utilise input
, l'print
déclaration de et /
pour la division entière.)
Ruby-158 Caractères
Même algorithme que celui-ci , juste le test principal est différent
p=(v=(w=gets.to_i*2)-1)*w/2-1
a='
'*v*w
d=0
(v*v).times{|i|a[p]="1"*(i+1)!~/^1?$|^(11+?)\1+$/?42:32;d=(a[p+(z=[w,-1,-w,1])[d-1]]<32)?(d-1):d%4;p+=z[d]}
puts a
Haskell-224 caractères
(%)=zipWith(++)
r x=[x]
l 1=r[1]
l n=r[a,a-1..b]++(m r[a+1..]%l s%m r[b-1,b-2..])++r[d-s*2..d]where{d=(n*2-1)^2;b=d-s*6;a=d-s*4;s=n-1}
p[_]='*'
p _=' '
i n=p[x|x<-[2..n],n`mod`x==0]
m=map
main=interact$unlines.m(m i).l.read
Je ne suis pas le meilleur chez haskell donc il y a probablement plus de rétrécissement qui peut se produire ici
Sortie de echo 6 | runghc ulam.hs
* *
* *
* * * *
* * *
* * *
* ** *
* * *
* *
* * * *
* *
*
C'est un algorithme différent (similaire à celui de @drhirsch) malheureusement, je n'arrive pas à l'obtenir ci-dessous 239 caractères
p[_]='*'
p _=' '
main=interact$unlines.u.read
i n=p[x|x<-[2..n],n`mod`x==0]
u(n+1)=map(map(i.f.o).zip[-n..n].replicate((n+1)*2-1))[n,n-1..(-n)]
f(x,y,z)=4*y*y-x-y+1+if z then 2*(x-y)else 0
o(u,v)=if(v> -u)==(v<u)then(v,u,v<u)else(u,v,v<u)
Premier message! (Oh attendez, ce n'est pas SlashDot ?)
Mon entrée pour L'équipe Clojure, 685 528 personnages.
(defn ulam[n] (let [z (atom [1 0 0 {[0 0] " "}])
m [[0 1 1 0][2 -1 0 -1][2 0 -1 0][2 0 0 1][2 0 1 0]]
p (fn [x] (if (some #(zero? (rem x %)) (range 2 x)) " " "*"))]
(doseq [r (range 1 (inc n)) q (range (count m)) [a b dx dy] [(m q)]
s (range (+ (* a r) b))]
(let [i (inc (first @z)) x (+ dx (@z 1)) y (+ dy (@z 2))]
(reset! z [i x y (assoc (last @z) [x y] (p i))])))
(doseq [y (range (- n) (inc n))] (doseq [x (range (- n) (inc n))]
(print ((last @z) [x y]))) (println))))
(ulam (dec (.nextInt (java.util.Scanner. System/in))))---
Input:
5
Output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Input:
10
Output:
* * * *
* * *
* * *
* * *
* * * *
* * *
* * * * * *
* * * * *
* * *
* * ** * * *
* * *
* *
* * * * * *
* * * *
* *
* * * * *
* *
* * *
* * * *
Pas aussi beau que l'entrée C précédente, mais voici le mien.
Note: je poste parce qu'il prend une approche différente de la précédente, principalement
- Il n'y a pas de remappage de coordonnées
- , il donne les mêmes résultats que les tests
-
, Il travaille avec entrée > 9 (deux chiffres - pas de
-47
truc)enum directions_e { dx, up, sx, dn } direction; int main (int argc, char **argv) { int len = atoi(argv[1]); int offset = 2*len-1; int size = offset*offset; char *matrix = malloc(size); int startfrom = 2*len*(len-1); matrix[startfrom] = 1; int next = startfrom; int count = 1; int i, step = 1; direction = dx ; for (;; step++ ) do { for ( i = 0 ; i < step ; i++ ) { switch ( direction ) { case dx: next++; break; case up: next = next - offset; break; case sx: next--; break; case dn: next = next + offset; } int div = ++count; do { div--; } while ( count % div ); if ( div > 1 ) { matrix[next] = ' '; } else { matrix[next] = '*'; } if (count >= size) goto dontusegoto; } direction = ++direction % 4; } while ( direction %2); dontusegoto: for ( i = 0 ; i < size ; i++ ) { putchar(matrix[i]); if ( !((i+1) % offset) ) putchar('\n'); } return 0; }
Qui, correctement traduit en C illisible, devient 339 caractères.
Compiler avec: gcc -o ulam_compr ulam_compr.c
fonctionne sur osx
i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)
Et debian Lenny.
main(int a,char**v){
int l=atoi(v[1]),o=2*l-1,z=o*o,n=2*l*(l-1),c=1,i,s=1,d;
char*m=malloc(z);
m[n]=1;
for(;;s++)do{
for(i=0;i<s;i++){
if(d==0)n++;
else if(d==1)n-=o;
else if(d==2)n--;
else n+=o;
int j=++c;
while(c%--j);
if(j>1)m[n]=' ';else m[n]='*';
if(c>=z)goto g;
}d=++d%4;}while(d%2);
g:for(i=0;i<z;i++){
putchar(m[i]);
if(!((i+1)%o))putchar('\n');
}
}
Voici une sortie:
$ ./ulam_compr 3
* *
* *
* **
*
*
$ ./ulam_compr 5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Python-176
Celui-ci commence par une longue liste de caractères de nouvelle ligne et les remplace tous sauf ceux qui sont nécessaires à la fin des lignes.
À partir du centre, l'algorithme regarde autour du coin gauche à chaque étape. S'il y a un caractère de retour à la ligne, tournez à gauche sinon continuez.
w=input()*2;v=w-1;a=['\n']*v*w;p=w/2*v-1;d=0;z=[w,-1,-w,1]
for i in range(v*v):a[p]=' *'[i and all((i+1)%f for f in range(2,i))];d=d%4-(a[p+z[d-1]]<' ');p+=z[d]
print"".join(a)
Python - 177
L'utilisation d'une chaîne évite "join" mais finit par un octet de plus puisque la chaîne est immuable
w=input()*2;v=w-1;a='\n'*v*w;p=w/2*v-1;d=0;z=[w,-1,-w,1]
for i in range(v*v):a=a[:p]+' *'[i and all((i+1)%f for f in range(2,i))]+a[p+1:];d=d%4-(a[p+z[d-1]]<' ');p+=z[d]
print a
Python, 299 caractères:
from sys import *
def t(n):
if n==1:return ' '
for i in range(2,n):
if n%i==0:return ' '
return '*'
i=int(stdin.readline())
s=i*2-1
o=['\n']*(s+1)*s
c=1
g=2
d=0
p=(s+2)*(i-1)
for n in range(s**2):
o[p]=t(n+1);p+=[1,-s-1,-1,s+1][d%4];g-=1
if g==c:d+=1
if g==0:d+=1;c+=1;g=2*c
print ''.join(o)
Lua, 302 caractères
s=...t={" "}n=2 function p()for j=2,n-1 do if n%j==0 then n=n+1 return" "end
end n=n+1 return"*"end for i=2,s do for k=#t,1,-1 do t[k+1]=t[k]..p()end
t[1]=""for k=1,i*2-1 do t[1]=p()..t[1]end for k=2,#t do t[k]=p()..t[k]end
t[#t+1]=""for k=1,i*2-1 do t[#t]=t[#t]..p()end end print(table.concat(t,"\n"))
Sortie de lua ulam.lua 6
:
* * * * * * * * * * * * * * * ** * * * * * * * * * * * * *
Python 284 266 256 243 242 240 char
Je voulais essayer la récursivité, je suis sûr qu'elle peut être fortement raccourcie:
r=range
def f(n):
if n<2:return[[4]]
s=2*n-1;z=s*s;c=[r(z-2*s+2,z-3*s+2,-1)];e=1
for i in f(n-1):c+=[[c[0][0]+e]+i+[c[0][-1]-e]];e+=1
c+=[r(z-s+1,z+1)];return c
for l in f(input()):print''.join(' *'[all(x%f for f in r(2,x))]for x in l)
Édité sous suggestion dans les commentaires
Mathematica 243
l = Length; t = Table; f = Flatten;
h@m_ := With[{x = l@m[[1]], y = l@m}, f[{{Reverse@t[w + y + (x y), {w, x + 2}]},
t[f[{(x y) + x + y + 2 + w, m[[w]], (x y) + y - w + 1}], {w, y}],
{t[2 + y + x + y + w + (x y), {w, x + 2}]}}, 1]];
m_~g~z_ := Nest[h, m, z] /. {_?PrimeQ -> "\[Bullet]", _Integer -> ""};
Grid[{{1}}~g~#, Frame -> All] &
L'Utilisation de
13 enroulements:
Grid[{{1}}~g~#, Frame -> All] &[13]