language agnostic - Código de golf: Ulam Spiral

language-agnostic code-golf

Question

El reto

El código más corto por número de caracteres para generar la espiral de Ulam con un tamaño de espiral dado por la entrada del usuario.

La espiral de Ulam es un método para mapear números primos. La espiral comienza desde el número 1 en el centro (1 no es un número primo) y genera una espiral a su alrededor, marcando todos los números primos como el carácter '' * ''. Un non prime será impreso como un espacio '' ''.

texto alt http://liranuna.com/junk/ulam.gif

Casos de prueba

Input:
2
Output:
* *
*
*
Input:
3
Output:
* *
* *
* **
*
*
Input:
5
Output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *

El conteo de códigos incluye entrada / salida (es decir, programa completo).

Answer 1

C, 208 206 201 200 199 196 194 193 194 193 188 185 183 180 176 bytes

(si se eliminan las nuevas líneas):

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);}}

Compilado con

> gcc -std=c99 -o ulam ulam.c

Advertencia. Este programa es lento, porque hace una división de prueba de hasta 2 ^ 31. Pero sí produce la salida requerida:

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

En C bien formateado y con #incluye redundante:

#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?'' '':''*'');
}
}

Funciona al transformar las coordenadas de la cuadrícula en el número apropiado y luego realizar la prueba de primalidad, en lugar de dibujar en forma de serpiente. Las diferentes ecuaciones para los cuatro "cuadrantes" se pueden contraer en uno con el intercambio de x e y, y un término adicional para "contar hacia atrás".

Answer 2

Golfscript - 92 personajes

~. (: S +,: R {S / -: |; R {S -: $ |> ''*'' 1 / [| $. |] 2 / @: d | ~) $ <! ^ = ~: $ ;: y. * 4 * $ - y-) 2d * $ y - * +: $, {) $ /%!} ,, 2 ==}% n}%

97 caracteres
~. (: S +,: R {S / -: |; R {S -: $ |> ''*'' 1 / [| $. |] 2 / @: d | ~) $ <! ^ = ~: $ ;: y. * 4 * $ - y-) 2d * $ y - * +. 1 = 3 * +: $, 2> {$ /%!},! =}% n}%

99 caracteres
~. (: S +, {S -}%: R {~): |; R {: $ |> ''*'' 1 / [| $. |] 2 / @: d | ~) $ <! ^ = ~ : $ ;: y. * 4 * $ - y-) 2d * $ y - * +. 1 = 3 * +: $, 2> {$ /%!},! =}% n}%

100 caracteres
~: S. (+, {S (-}%: R {~): |; R {: $ |> ''*'' 1 / [| $. |] 2 / @: d | ~) $ <! ^ = ~: $ ;: y. * 4 * $ - y-) 2d * $ y - * +. 1 = 3 * +: $, 2> {$ /%!},! =}% n}%

101 caracteres
~: S. (+, {S (-}%: R {~): v; R {: $ v>: d; ''*'' 1 / [v $ .v] 2 / v ~) $ <! D ^ = ~: $ ;: y. * 4 * $ - y-) 2d * $ y - * +. 1 = 3 * +: $, 2> {$ /%!},! =}% n}%

Answer 3

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] &

Uso

13 devanados:

Grid[{{1}}~g~#, Frame -> All] &[13]

Answer 4

Python - 171

C de drhirsch portado a 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 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Answer 5

Python - 176

Este comienza con una larga lista de caracteres de nueva línea y los reemplaza a todos, excepto a los que se necesitan al final de las líneas.

Comenzando en el centro, el algoritmo se asoma por la esquina izquierda en cada paso. Si hay un carácter de nueva línea, gire a la izquierda, de lo contrario, siga adelante.

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
El uso de una cadena evita la "unión" pero termina un byte más ya que la cadena es inmutable

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

Answer 6

Python - 203 personajes

 _________________________________________________________
/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))

Cómo funciona
La idea es llenar A con x, y coords que necesitan ser impresos como ''*''
El algoritmo comienza en la celda correspondiente a 2, por lo que se evita el caso especial de prueba de primalidad.
x, y es la celda de interés
j, k hacer un seguimiento de si necesitamos inc o dec x o y para llegar a la siguiente celda
s es el valor de i en la siguiente esquina
t mantiene un registro del incremento hasta s

all (i% d para d en R (2, i)) hace la verificación de primalidad

La última línea es bastante torpe. Recorre todas las celdas y decide si colocar un espacio o un asterisco.

Answer 7

Python 2.x, 220C 213C 207C 204C 201C 198C 196C 188C

Un agradecimiento especial a gnibbler por algunos consejos en # en Freenode . La salida incluye una nueva línea principal y final.

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)

(La compatibilidad con Python 3 requeriría caracteres adicionales; esto usa input , la declaración de print y / para la división de enteros).

Answer 8

Ruby - 158 personajes

El mismo algoritmo que este , solo la prueba principal es diferente

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

Answer 9

Lua, 302 caracteres

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

Salida de lua ulam.lua 6 :

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

Answer 10

Pitón 284 266 256 243 242 240 caracteres

Quería probar la recursión, estoy seguro de que puede ser muy breve:

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)

editado bajo sugerencia en comentarios

Answer 11

Haskell - 224 caracteres

(%)=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

No soy el mejor en Haskell, así que es probable que haya algo más de contracción que pueda ocurrir aquí.

salida de echo 6 | runghc ulam.hs echo 6 | runghc ulam.hs

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

este es un algoritmo diferente (similar al de @drhirsch) lamentablemente no puedo entenderlo por debajo de 239 caracteres

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)

Answer 12

MATLAB, 56 caracteres

basado en la solución @gnovice , mejorada utilizando la función espiral de MATLAB :)

disp(char(isprime(flipud(spiral(2*input('''')-1)))*10+32))

Casos de prueba:

>> 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
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *

Answer 13

Ruby 1.8.7, 194 caracteres

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":''''}

Por alguna razón, ruby1.9 quiere otro espacio en la línea 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}

Answer 14

Mi primer código de golf!

Ruby, 309 301 283 271 265 caracteres

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

Answer 15

No es tan hermosa como la entrada anterior de C, pero aquí está la mía.

Nota: estoy publicando porque tiene un enfoque diferente al anterior, principalmente

• no hay reasignación de coordenadas
• Da los mismos resultados que las pruebas.

• funciona con entrada> 9 (dos dígitos - sin truco -47 )

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

el cual, traducido adecuadamente en C ilegible, se convierte en 339 caracteres.

compilar con: gcc -o ulam_compr ulam_compr.c funciona en osx

i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)

y 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'');
}
}

Aquí hay algunos resultados:

 $ ./ulam_compr 3
* *
* *
* **
*
*
$ ./ulam_compr 5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *

Answer 16

Solución J: 197 173 165 161 bytes (hasta ahora)
Esto no utiliza el método mencionado en los comentarios al 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){'' *''

Answer 17

¡Primer comentario! (oh espera, esto no es SlashDot ?)

Mi entrada para el Equipo Clojure, 685 528 caracteres.

(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:
* * * *
* * *
* * *
* * *
* * * *
* * *
* * * * * *
* * * * *
* * *
* * ** * * *
* * *
* *
* * * * * *
* * * *
* *
* * * * *
* *
* * *
* * * *

Answer 18

MATLAB: 182 167 156 caracteres

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

Y formateado un poco más agradable:

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

Casos de prueba:

>> ulam
2
* *
*
*
>> ulam
3
* *
* *
* **
*
*
>> ulam
5
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *

Answer 19

Python, 299 caracteres:

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)