Гольф кода: Зигзагообразное сканирование шаблона
Проблема
Самый короткий код счетчиком символов, который берет единственное входное целое число N (N> = 3) и возвраты массив индексов, которые при итерации пересекут NxN матрица согласно JPEG "делает зигзаги" шаблон сканирования. Следующее является обходом в качестве примера по 8x8 matrixsrc:
Примеры
(Средняя матрица не является частью ввода или вывода, просто представление NxN матрицирует вход, представляет.)
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
Примечания
- Основа полученного массива должна подходить для Вашего языка (например, массивы Matlab на основе 1 массивы C++ на основе 0).
- Это связано с этим вопросом.
Премия
Расширьте свой ответ для взятия двух исходных данных N и M (N, M> =3), и выполняют то же сканирование по NxM матрица. (В этом случае N было бы число столбцов и M количество строк.)
Бонусные примеры
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
9 ответов
J, 13 15 символов
;<@|.`</.i.2$
Использование:
;<@|.`</.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
Пояснение
( NB. - это индикатор комментария 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, бонус, 13 символов
;<@|.`</.i.|.
Использование:
;<@|.`</.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
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],
Тестирование:
$ 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
Это решение легко обобщается для NxM плат: подстройте обработку ввода и замените N*N на 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],
Я подозреваю, что есть какой-то более простой/короткий способ прочитать два числа.
Тестирование:
$ echo 4 3 | python ./code-golf.py
0 1 4 8 5 2 3 6 9 10 7 11
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.
Golfscript, 26/30 32/36 45 59 символов
Кратчайшее решение, не относящееся к J:
Обновленная сортировка ( не говорите другим!) - 30 символов:
~:1.*,{..1/\1%+.2%.+(@*]}$' '* #solution 1
#~:\.*,{.\/1$\%+.1&@.~if]}$' '* #solution 2
#~\:1*,{..1/\1%+.2%.+(@*]}$' '* #(bonus)
#~\:\*,{.\/1$\%+.1&@.~if]}$' '* #(bonus)
Прямая реализация - 36 символов:
~:@.*,{[.@%:|\@/:^+|^- 2%^|if]}$' '*
#~\:@*,{[.@%:|\@/:^+|^- 2%^|if]}$' '* #(bonus)
Если вы можете предоставить вывод как «013642578» вместо «0 1 3 6 4 2 5 7 8», то вы можете удалите последние 4 символа.
Удвоение качества за технику сортировки.
Объяснение:
~\:@* #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
и для ключа:
[ #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
MATLAB, 101/116 символов
Это в основном сокращенная версия того же ответа, данного здесь , для запуска непосредственно в командной строке:
N=input('');i=fliplr(spdiags(fliplr(reshape(1:N*N,N,N)')));i(:,1:2:end)=flipud(i(:,1:2:end));i(i~=0)'
и расширенная версия, которая считывает два значения от пользователя:
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)'
Тестирование:
3
ans =
1 2 4 7 5 3 6 8 9
и
4 3
ans =
1 2 5 9 6 3 4 7 10 11 8 12
F #, 126 символов
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 "
Примеры:
$ 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
Ruby 137 130 138 символов
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
Haskell 117 символов
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
Выполняется:
$ 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]
Прямоугольный вариант немного длиннее - 120 символов:
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
Для ввода здесь требуется кортеж:
$ 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]
Ответы все основаны на 0 и возвращаются в виде списков (естественные формы для Haskell).
Использование символов Perl 102
<>=~/ /;print map{$_%1e6," "}sort map{($x=($%=$_%$`)+($/=int$_/$`))*1e9+($x%2?$/:$%)*1e6+$_}0..$'*$`-1
:
echo 3 4 | perl zigzag.pl
0 1 3 6 4 2 5 7 9 10 8 11