Code Golf: Zigzag pattern scanning

Question

The Challenge

The shortest code by character count that takes a single input integer N (N >= 3) and returns an array of indices that when iterated would traverse an NxN matrix according to the JPEG "zigzag" scan pattern. The following is an example traversal over an 8x8 matrix^src:

Examples

(The middle matrix is not part of the input or output, just a representation of the NxN matrix the input represents.)

                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

Notes

• The resulting array's base should be appropriate for your language (e.g., Matlab arrays are 1-based, C++ arrays are 0-based).
• This is related to this question.

Bonus

Extend your answer to take two inputs N and M (N, M >=3) and perform the same scan over an NxM matrix. (In this case N would be the number of columns and M the number of rows.)

Bonus Examples

                  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

Winni

I'll start the J pool with... under 7 characters. – Sethrida

@Mark: The best I have so far is 15. I'm pretty sure 7 isn't possible for this question, but I'd love to be proven wrong. – Camillacamille

why is it i spend a day of coding then i spend 3 more hours doing code golf? =P – Inducement

Answer 1

J, 13 15 characters

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

Usage:

   ;<@|.`</.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

Explanation

(NB. is J's comment indicator)

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

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

Usage:

   ;<@|.`</.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

Camillacamille

I like how it takes two characters to do 'applied to alternating diagonals of'. – Softy

yea the 'alternating diagonal' built-in is what makes this possible. im workin on a goflscript solution which doesnt use that.. will see how short it can be – Inducement

Answer 2

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

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

Testing:

$ 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

This solution easily generalizes for NxM boards: tweak the input processing and replace N*N with 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],

I suspect there's some easier/shorter way to read two numbers.

Testing:

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

Croteau

I'm not familiar with Python syntax, but how does this print the numbers separated by a space? – Clementinaclementine

@Adam the comma does that, also "A '\n' character is written at the end, unless the print statement ends with a comma" – Aquilegia

You can use 'split()' rather than 'replace()' – Camillacamille

@David: No he can't. He'll be left with an array of two strings. He needs an array of two ints, so that's why he's using eval + replace. You could just use split and then cast each array element to an int, but I think that'll end up using more characters. – Saree

@wallacoloo: how about N,M=input() (python 2.x)? – Discoverer

@doublep: Well yeah but nowhere is postulated the input should be in format '4\s+3'. Based on that i think any reasonable input requirement is ok - in this case '4,\s*3'. Why should we be biased towards Google Code Jam or C input style? Other languages (Python, Basic, ...) like CSVs better ;-) ps. example of imho unreasonable requirement - 'encode m and n by interlacing the bits and input that, e.g. for 4 (0b100) and 3 (0b011) type 37 (0b100101) – Discoverer

Answer 3

Ruby, 69 89 chars

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

89 chars

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

Run

> 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

Credits to doublep for the sort method.

Clementinaclementine

n=eval *$<;p (0...n*n).sort_by{|p|[t=p%n+p/n,[p%n,p/n][t%2]]} 61 – Hampden

@matyr: p prints [0, 1, 3,...] instead of 0 1 3.... – Thamora

@matyr, thanks for that. made it 69. eval *$< didn't work on my system. – Clementinaclementine

@Sebastian "an array of indices" doesn't indicate space-separated. @Adam puts -> $><<. – Hampden

Answer 4

F#, 126 chars

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 "

Examples:

$ 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

Maxama

[x;y].[i%2] rather than if i%2=0 then x else y - nice, gotta remember that one - props to @doublep – Maxama

Oooh, that's a nice trick. I think that one might work in PowerShell as well. – Weissman

Answer 5

Golfscript, 26/30 32/36 45 59 characters

Shortest non-J solution so far:

Updated sort (don't tell the others!) - 30 chars:

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

---

Straight implementation - 36 chars:

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

If you can provide output as "013642578" instead of "0 1 3 6 4 2 5 7 8", then you can remove the last 4 characters.

Credit to doublep for the sorting technique.

---

Explanation:

~\:@*        #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

and for the key:

[            #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

Inducement

@Nabb: you sure the updated sort works? i tried it but it gives different output – Inducement

output is exactly the same for both the square and bonus problems for the values I tested – Garrard

Not familiar with Golfscript, but (a+b)%2 is equal to (a-b)%2. You might be able to %2 the sum of | and ^ if it helps saving some characters. – Clementinaclementine

Answer 6

MATLAB, 101/116 chars

Its basically a condensed version of the same answer given here, to be run directly on the command prompt:

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

and an extended one that read two values from the user:

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

Testing:

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

and

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

Chalet

Answer 7

C89 (280 bytes)

I guess this can still be optimized - I use four arrays to store the possible movement vectors when hitting a wall. I guess it can be done, saving some chars at the definition, but I think it will cost more to implement the logic further down. Anyway, here you go:

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

compiles with a few warnings, but as far as I know it is portable C89. I'm actually not sure whether my algorithm is clever at all, maybe you can get way shorter with a better one (haven't taken the time to understand the other solutions yet).

Glovsky

Answer 8

Ruby 137 130 138 characters

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

Terefah

You should use puts [array]*' ' to match the output in the question. – Clementinaclementine

Answer 9

Haskell 117 characters

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

Runs:

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

The rectangular variant is a little longer, at 120 characters:

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

Input here requires a tuple:

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

Answers are all 0-based, and returned as lists (natural forms for Haskell).

Floristic

Answer 10

Perl 102 characters

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

usage :

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

Larch