language agnostic - Code Golf: escaneo en zigzag

language-agnostic code-golf

Question

El reto

El código más corto por número de caracteres que toma un solo entero de entrada N (N> = 3) y devuelve una matriz de índices que cuando se itera atravesarían una matriz N x N según el patrón de escaneo JPEG "zigzag". El siguiente es un ejemplo de recorrido en una matriz de 8x8:

Ejemplos

(La matriz central no es parte de la entrada o salida, solo una representación de la matriz NxN que representa la entrada).

                1 2 3
(Input) 3  -->  4 5 6  -->  1 2 4 7 5 3 6 8 9 (Output)
                7 8 9

                1  2  3  4
(Input) 4  -->  5  6  7  8  -->  1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16 (Output)
                9 10 11 12
               13 14 15 16

Notas

• La base de la matriz resultante debe ser apropiada para su idioma (por ejemplo, las matrices Matlab están basadas en 1, las matrices C ++ están basadas en 0).
• Esto está relacionado con esta pregunta .

Prima

Amplíe su respuesta para tomar dos entradas N y M (N, M> = 3) y realice el mismo escaneo sobre una matriz N x M (En este caso, N sería el número de columnas y M el número de filas).

Ejemplos de bonos

                  1  2  3  4
(Input) 4 3  -->  5  6  7  8  -->  1 2 5 9 6 3 4 7 10 11 8 12 (Output)
                  9 10 11 12

                   1  2  3
(Input) 3 4  -->   4  5  6  -->  1 2 4 7 5 3 6 8 10 11 9 12 (Output)
                   7  8  9
                  10 11 12

Answer 1

C89 (280 bytes)

Supongo que esto aún puede optimizarse: uso cuatro matrices para almacenar los posibles vectores de movimiento cuando golpeo una pared. Supongo que se puede hacer, guardando algunos caracteres en la definición, pero creo que costará más implementar la lógica más abajo. De todos modos, aquí tienes:

t,l,b,r,i,v,n;main(int c,char**a){n=atoi(*++a);b=n%2;int T[]={n-1,1},L[]={1-n,n}
,B[]={1-n,1},R[]={n-1,n};for(c=n*n;c--;){printf("%d%c",i,c?32:10);if(i>=n*(n-1))
v=B[b=!b];else if(i%n>n-2){if(!(n%2)&&i<n)goto g;v=R[r=!r];}else if(i<n)g:v=T[t=
!t];else if(!(i%n))v=L[l=!l];i+=v;}}

se compila con algunas advertencias, pero por lo que sé, es portátil C89. En realidad, no estoy seguro de si mi algoritmo es inteligente en absoluto, tal vez puedas reducir mucho más uno mejor (aún no me he tomado el tiempo de entender las otras soluciones).

Answer 2

F #, 126 caracteres

let n=stdin.ReadLine()|>int
for i=0 to 2*n do for j in[id;List.rev].[i%2][0..i]do if i-j<n&&j<n then(i-j)*n+j|>printf"%d "

Ejemplos:

$ echo 3 | fsi --exec Program.fsx
0 1 3 6 4 2 5 7 8

$ echo 4 | fsi --exec Program.fsx
0 1 4 8 5 2 3 6 9 12 13 10 7 11 14 15

Answer 3

Golfscript, 26/30 32/36 45 59 caracteres

La solución no J más corta hasta el momento:

Clasificación actualizada (¡no se lo digas a los demás!) - 30 caracteres:

 ~:1.*,{..1//1%+.2%.+(@*]}$'' ''* #solution 1
#~:/.*,{.//1$/%+.1&@.~if]}$'' ''* #solution 2
#~/:1*,{..1//1%+.2%.+(@*]}$'' ''* #(bonus)
#~/:/*,{.//1$/%+.1&@.~if]}$'' ''* #(bonus)

Implementación recta - 36 caracteres:

 ~:@.*,{[.@%:|/@/:^+|^- 2%^|if]}$'' ''*
#~/:@*,{[.@%:|/@/:^+|^- 2%^|if]}$'' ''* #(bonus)

Si puede proporcionar una salida como "013642578" en lugar de "0 1 3 6 4 2 5 7 8", puede eliminar los últimos 4 caracteres.

Crédito al doble por la técnica de clasificación.

Explicación:

~/:@*        #read input, store first number into @, multiply the two
,            #put range(@^2) on the stack
{...}$       #sort array using the key in ...
" "*         #join array w/ spaces

y para la clave:

[            #put into an array whatever is left on the stack until ]
.@%:|        #store @%n on the stack, also save it as |
/@/:^        #store @/n on the stack, also save it as ^
+            #add them together. this remains on the stack.
|^- 2%^|if   #if (| - ^) % 2 == 1, then put ^ on stack, else put | on stack.
]            #collect them into an array

Answer 4

MATLAB, 101/116 caracteres

Es básicamente una versión condensada de la misma respuesta dada here , para ejecutarse directamente en el símbolo del sistema:

N=input('''');i=fliplr(spdiags(fliplr(reshape(1:N*N,N,N)'')));i(:,1:2:end)=flipud(i(:,1:2:end));i(i~=0)''

y uno extendido que lee dos valores del usuario:

S=str2num(input('''',''s''));i=fliplr(spdiags(fliplr(reshape(1:prod(S),S)'')));i(:,1:2:end)=flipud(i(:,1:2:end));i(i~=0)''

Pruebas:

3
ans =
     1     2     4     7     5     3     6     8     9

y

4 3
ans =
     1     2     5     9     6     3     4     7    10    11     8    12

Answer 5

Python, 92, 95 , 110 , 111 , 114 , 120 , 122 , 162 , 164 caracteres

N=input()
for a in sorted((p%N+p/N,(p%N,p/N)[(p%N-p/N)%2],p)for p in range(N*N)):print a[2],

Pruebas:

$ echo 3 | python ./code-golf.py 
0 1 3 6 4 2 5 7 8

$ echo 4 | python ./code-golf.py 
0 1 4 8 5 2 3 6 9 12 13 10 7 11 14 15

Esta solución se generaliza fácilmente para las placas N x M : modifique el procesamiento de entrada y reemplace N*N con N*M :

N,M=map(int,raw_input().split())
for a in sorted((p%N+p/N,(p%N,p/N)[(p%N-p/N)%2],p)for p in range(N*M)):print a[2],

Sospecho que hay una manera más fácil / breve de leer dos números.

Pruebas:

$ echo 4 3 | python ./code-golf.py 
0 1 4 8 5 2 3 6 9 10 7 11

Answer 6

Ruby 137 130 138 caracteres

n=gets.to_i
def g(a,b,r,t,s);x=[s*r]*t;t==r ?[a,x,a]:[a,x,g(b,a,r,t+1,-s),x,a];end
q=0;puts ([1]+g(1,n,n-1,1,1)).flatten.map{|s|q+=s}*'' ''

$ zz.rb
3
1 2 4 7 5 3 6 8 9

$ zz.rb
4
1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16

Answer 7

Ruby, 69 89 caracteres

n=gets.to_i
puts (0...n*n).sort_by{|p|[t=p%n+p/n,[p%n,p/n][t%2]]}*'' ''

89 caracteres

n=gets.to_i
puts (0...n*n).map{|p|[t=p%n+p/n,[p%n,p/n][t%2],p]}.sort.map{|i|i[2]}.join'' ''

correr

> zigzag.rb
3
0 1 3 6 4 2 5 7 8

> zigzag.rb
4
0 1 4 8 5 2 3 6 9 12 13 10 7 11 14 15

Créditos a doblep por el método de clasificación.

Answer 8

Haskell 117 caracteres

i s=concatMap(/q->d q++(reverse.d$q+1))[0,2..s+s]
 where d r=[x+s*(r-x)|x<-[0..r],x<s&&(r-x)<s]
main=readLn>>=print.i

Carreras:

$ echo 3 | ./Diagonals 
[0,1,3,6,4,2,5,7,8]

$ echo 4 | ./Diagonals 
[0,1,4,8,5,2,3,6,9,12,13,10,7,11,14,15]

La variante rectangular es un poco más larga, con 120 caracteres:

j(w,h)=concatMap(/q->d q++(reverse.d$q+1))[0,2..w+h]
 where d r=[x+w*(r-x)|x<-[0..r],x<w&&(r-x)<h]
main=readLn>>=print.j

La entrada aquí requiere una tupla:

$ echo ''(4,3)'' | ./Diagonals 
[0,1,4,8,5,2,3,6,9,10,7,11]

$ echo ''(3,4)'' | ./Diagonals 
[0,1,3,6,4,2,5,7,9,10,8,11]

Las respuestas se basan en 0 y se devuelven como listas (formas naturales para Haskell).

Answer 9

J, 13 15 caracteres

;<@|.`</.i.2$

Uso:

   ;<@|.`</.i.2$  3
0 1 3 6 4 2 5 7 8

   ;<@|.`</.i.2$  4
0 1 4 8 5 2 3 6 9 12 13 10 7 11 14 15

Explicación

( NB. Es el indicador de comentario de J)

;         NB. Link together...
<@|.`<    NB. ... ''take the reverse of'' and ''take normally''
/.        NB. ... applied to alternating diagonals of...
i.        NB. ... successive integers starting at 0 and counting up to fill an array with dimensions of...
2$        NB. ... the input extended cyclically to a list of length two.

J, bonus, 13 caracteres

;<@|.`</.i.|.

Uso:

   ;<@|.`</.i.|. 3 4
0 1 3 6 4 2 5 7 9 10 8 11

   ;<@|.`</.i.|. 9 6
0 1 9 18 10 2 3 11 19 27 36 28 20 12 4 5 13 21 29 37 45 46 38 30 22 14 6 7 15 23 31 39 47 48 40 32 24 16 8 17 25 33 41 49 50 42 34 26 35 43 51 52 44 53

Answer 10

Perl 102 caracteres

<>=~/ /;print map{$_%1e6," "}sort map{($x=($%=$_%$`)+($/=int$_/$`))*1e9+($x%2?$/:$%)*1e6+$_}0..$''*$`-1

uso:

echo 3 4 | perl zigzag.pl
0 1 3 6 4 2 5 7 9 10 8 11