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

27
demandé sur LiraNuna 2009-11-27 00:42:30

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}%

8
répondu gnibbler 2009-11-29 23:28:54

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

28
répondu gnibbler 2009-11-28 00:35:42

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
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  
10
répondu gnovice 2009-11-27 22:46:50

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

7
répondu hirschhornsalz 2009-11-28 09:34:12

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}
5
répondu ACoolie 2009-11-27 02:59:25

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 
      *     *   * *   *             *  
 *     * *     *   * *                 
*     * *                     *     *  
       * *     *   *           *     * 
                  *   * *   *          
 *               *   *       *   * *   
*     *   *           * *     *        
 *   * *     * *     *     *           
* *           *           *   *     * *
   *     *   *       *     *           
    *   *         *   * *   * * *      
 * *       *     *         * *   *     
      *     *   * *               *    
                   * *     *   *   * * 
*   *   *   * *   *       *   * *      
                   * *   *             
  *       *   * *     * * *     * * *  
   * * * * * * * *   *       *         
                  * * *           *    
             *   *  ** * * *   * * *   
      *       * * *                    
               *   *                   
    *   * *   * *   *   * *   *   * *  
 *     *   *   *     *     * *   *     
                *           *          
 *         * *     *   *   *       * * 
* *     *   *           *       *     *
   *     *     *   * *                 
              * *   *     *   *     *  
   * * * *         * *     *     * *   
      *   *           * *              
 *   * *     *     *   * *           * 
  * *       *         *       *     *  
             * *   * *         *     * 
          *   *     *     *         * *
       * *     *                 *     
*   *       *           *   *     *    
                             *     *   
*   * *   *     *           *          
5
répondu gnibbler 2009-11-29 23:38:08

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
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  
5
répondu Amro 2017-05-23 11:46:39

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){' *'
3
répondu cobbal 2009-11-27 20:26:05

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
3
répondu Jim Puls 2009-11-28 01:36:39

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

3
répondu Stephan202 2017-05-23 12:25:49

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
3
répondu John La Rooy 2017-05-23 11:54:24

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)
3
répondu barkmadley 2009-11-28 15:38:28

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:
        *   * *   *
 *     *         * 
  *   * *          
         * *     * 
  * *   *       *  
         * *   *   
*   * *     * * *  
 * * * *   *       
        * * *      
   *   *  ** * * * 
    * * *          
     *   *         
*   * *   *   * *  
 *   *     *     * 
      *           *
 * *     *   *   * 
  *           *    
     *   * *       
    * *   *     *  
1
répondu Carl Smotricz 2009-11-27 05:05:24

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
    * *  
 *     * 
* *   *  
   * * * 
  * ** *
 * *     
*   *    
 *   *   
*     *  
1
répondu lorenzog 2009-11-27 20:39:41

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
1
répondu gnibbler 2009-11-28 12:38:22

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)
0
répondu Thanatos 2009-11-27 03:35:32

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:

*   *      
     * *   
* *     * *
 * *   *   
    * * *  
   *  ** * 
* * *      
 *   *     
* *   *   *
 *     *   
  *        
0
répondu gwell 2009-11-27 04:55:32

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

0
répondu Andrea Ambu 2009-11-28 15:48:51

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]

Ulam

0
répondu DavidC 2012-09-19 23:36:17