Produce a spiral array.
A spiral array is a square arrangement of the first N2 natural numbers, where the
numbers increase sequentially as you go around the edges of the array spiraling inwards.
For example, given 5, produce this array:
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
F spiral_matrix(n) V m = [[0] * n] *n V d = [(0, 1), (1, 0), (0, -1), (-1, 0)] V xy = (0, -1) V c = 0 L(i) 0 .< n + n - 1 L 0 .< (n + n - i) I/ 2 xy += d[i % 4] m[xy.x][xy.y] = c c++ R mF printspiral(myarray) L(y) 0 .< myarray.len L(x) 0 .< myarray.len print(‘#2’.format(myarray[y][x]), end' ‘ ’) print()printspiral(spiral_matrix(5))
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
For maximum compatibility, this program uses only the basic instruction set.
SPIRALM CSECT USING SPIRALM,R13SAVEAREA B STM-SAVEAREA(R15) DC 17F'0' DC CL8'SPIRALM'STM STM R14,R12,12(R13) ST R13,4(R15) ST R15,8(R13) LR R13,R15* ---- CODE LA R0,0 LA R1,1 LH R12,N n LR R4,R1 Row=1 LR R5,R1 Col=1 LR R6,R1 BotRow=1 LR R7,R1 BotCol=1 LR R8,R12 TopRow=n LR R9,R12 TopCol=n LR R10,R0 Dir=0 LR R15,R12 n MR R14,R12 R15=n*n LA R11,1 k=1LOOP CR R11,R15 BH ENDLOOP LR R1,R4 BCTR R1,0 MH R1,N AR R1,R5 LR R2,R11 k BCTR R2,0 BCTR R1,0 SLA R1,1 STH R2,MATRIX(R1) Matrix(Row,Col)=k-1 CH R10,=H'0' BE DIR0 CH R10,=H'1' BE DIR1 CH R10,=H'2' BE DIR2 CH R10,=H'3' BE DIR3 B DIRXDIR0 CR R5,R9 if Col<TopCol BNL DIR0S LA R5,1(R5) Col=Col+1 B DIRXDIR0S LA R10,1 Dir=1 LA R4,1(R4) Row=Row+1 LA R6,1(R6) BotRow=BotRow+1 B DIRXDIR1 CR R4,R8 if Row<TopRow BNL DIR1S LA R4,1(R4) Row=Row+1 B DIRXDIR1S LA R10,2 Dir=2 BCTR R5,0 Col=Col-1 BCTR R9,0 TopCol=TopCol-1 B DIRXDIR2 CR R5,R7 if Col>BotCol BNH DIR2S BCTR R5,0 Col=Col-1 B DIRXDIR2S LA R10,3 Dir=3 BCTR R4,0 Row=Row-1 BCTR R8,0 TopRow=TopRow-1 B DIRXDIR3 CR R4,R6 if Row>BotRow BNH DIR3S BCTR R4,0 Row=Row-1 B DIRXDIR3S LA R10,0 Dir=0 LA R5,1(R5) Col=Col+1 LA R7,1(R7) BotCol=BotCol+1DIRX EQU * LA R11,1(R11) k=k+1 B LOOPENDLOOP EQU * LA R4,1 iLOOPI CR R4,R12 BH ENDLOOPI XR R10,R10 LA R5,1 jLOOPJ CR R5,R12 BH ENDLOOPJ LR R1,R4 BCTR R1,0 MH R1,N AR R1,R5 BCTR R1,0 SLA R1,1 LH R2,MATRIX(R1) Matrix(i,j) LA R3,BUF AR R3,R10 CVD R2,P8 MVC 0(4,R3),=X'40202120' ED 0(4,R3),P8+6 LA R10,4(R10) LA R5,1(R5) B LOOPJENDLOOPJ EQU * WTO MF=(E,WTOMSG) LA R4,1(R4) B LOOPIENDLOOPI EQU ** ---- END CODE L R13,4(0,R13) LM R14,R12,12(R13) XR R15,R15 BR R14* ---- DATAN DC H'5' max=20 (20*4=80) LTORG P8 DS PL8WTOMSG DS 0F DC H'80',XL2'0000'BUF DC CL80' 'MATRIX DS H Matrix(n,n) YREGS END SPIRALM
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
REPORTzspiral_matrix.CLASSlcl_spiral_matrixDEFINITIONFINAL.PUBLIC SECTION.TYPES:BEGIN OFty_coordinates,dyTYPEi,dxTYPEi,valueTYPEi,END OFty_coordinates,ty_t_coordinatesTYPE STANDARD TABLE OFty_coordinatesWITHEMPTYKEY.DATAmv_dimentionTYPEi.DATAmv_initial_valueTYPEi.METHODS:constructorIMPORTINGiv_dimentionTYPEiiv_initial_valueTYPEi,get_coordinatesRETURNINGVALUE(rv_result)TYPEty_t_coordinates,print.PRIVATE SECTION.DATAlt_coordinatesTYPEty_t_coordinates.METHODScreateRETURNINGVALUE(ro_result)TYPE REF TOlcl_spiral_matrix.ENDCLASS.CLASSlcl_spiral_matrixIMPLEMENTATION.METHODconstructor.mv_dimention=iv_dimention.mv_initial_value=iv_initial_value.create().ENDMETHOD.METHODcreate.DATAdyTYPEi.DATAdxTYPEi.DATAvalueTYPEi.DATAseq_numberTYPEi.DATAseq_dimentionTYPEi.DATAsign_coefTYPEiVALUE-1.value=mv_initial_value." Fill in the first row (index 0)DOmv_dimentionTIMES.APPENDVALUE#(dy=dydx=dxvalue=value)TOlt_coordinates.value=value+1.dx=dx+1.ENDDO.seq_dimention=mv_dimention." Find the row and column numbers and set the values.DO(2*mv_dimention-2)/2TIMES.sign_coef=-sign_coef.seq_dimention=seq_dimention-1.DO2TIMES.seq_number=seq_number+1.DOseq_dimentionTIMES.IFseq_numberMOD2<>0.dy=dy+1*sign_coef.ELSE.dx=dx-1*sign_coef.ENDIF.APPENDVALUE#(dy=dydx=dxvalue=value)TOlt_coordinates.value=value+1.ENDDO.ENDDO.ENDDO.ro_result=me.ENDMETHOD.METHODget_coordinates.rv_result=lt_coordinates.ENDMETHOD.METHODprint.DATAcntTYPEi.DATAlineTYPEstring.SORTlt_coordinatesBYdydxASCENDING.LOOP ATlt_coordinatesASSIGNINGFIELD-SYMBOL(<ls_coordinates>).cnt=cnt+1.line=|{line}{<ls_coordinates>-value}|.IFcntMODmv_dimention=0.WRITE/line.CLEARline.ENDIF.ENDLOOP.ENDMETHOD.ENDCLASS.START-OF-SELECTION.DATA(go_spiral_matrix)=NEWlcl_spiral_matrix(iv_dimention=5iv_initial_value=0).go_spiral_matrix->print().
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
DEFINE MAX_SIZE="10"DEFINE MAX_MATRIX_SIZE="100"INT FUNC Index(BYTE size,x,y)RETURN (x+y*size)PROC PrintMatrix(BYTE ARRAY a BYTE size) BYTE i,j,v FOR j=0 TO size-1 DO FOR i=0 TO size-1 DO v=a(Index(size,i,j)) IF v<10 THEN Print(" ") ELSE Print(" ") FI PrintB(v) OD PutE() ODRETURNPROC FillMatrix(BYTE ARRAY a BYTE size) INT lev,maxLev,dist,maxDist,v maxLev=size/2 IF (size&1)=0 THEN maxLev==-1 FI maxDist=size-1 v=1 FOR lev=0 TO maxLev DO FOR dist=0 TO maxDist DO a(Index(size,lev+dist,lev))=v v==+1 OD FOR dist=0 TO maxDist-1 DO a(Index(size,size-1-lev,lev+dist+1))=v v==+1 OD FOR dist=0 TO maxDist-1 DO a(Index(size,size-2-lev-dist,size-1-lev))=v v==+1 OD FOR dist=0 TO maxDist-2 DO a(Index(size,lev,size-2-lev-dist))=v v==+1 OD maxDist==-2 ODRETURNPROC Test(BYTE size) BYTE ARRAY mat(MAX_MATRIX_SIZE) PrintF("Matrix size: %B%E",size) FillMatrix(mat,size) PrintMatrix(mat,size) PutE()RETURNPROC Main() Test(5) Test(6)RETURNScreenshot from Atari 8-bit computer
Matrix size: 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9Matrix size: 6 1 2 3 4 5 6 20 21 22 23 24 7 19 32 33 34 25 8 18 31 36 35 26 9 17 30 29 28 27 10 16 15 14 13 12 11
-- Spiral SquarewithAda.Text_Io;useAda.Text_Io;withAda.Integer_Text_Io;useAda.Integer_Text_Io;withAda.Numerics.Elementary_Functions;useAda.Numerics.Elementary_Functions;procedureSpiral_SquareistypeArray_Typeisarray(Positiverange<>,Positiverange<>)ofNatural;functionSpiral(N:Positive)returnArray_TypeisResult:Array_Type(1..N,1..N);Row:Natural:=1;Col:Natural:=1;Max_Row:Natural:=N;Max_Col:Natural:=N;Min_Row:Natural:=1;Min_Col:Natural:=1;beginforIin0..N**2-1loopResult(Row,Col):=I;ifRow=Min_RowthenCol:=Col+1;ifCol>Max_ColthenCol:=Max_Col;Row:=Row+1;endif;elsifCol=Max_ColthenRow:=Row+1;ifRow>Max_RowthenRow:=Max_Row;Col:=Col-1;endif;elsifRow=Max_RowthenCol:=Col-1;ifCol<Min_ColthenCol:=Min_Col;Row:=Row-1;endif;elsifCol=Min_ColthenRow:=Row-1;ifRow=Min_Rowthen-- Reduce spiralMin_Row:=Min_Row+1;Max_Row:=Max_Row-1;Row:=Min_Row;Min_Col:=Min_Col+1;Max_Col:=Max_Col-1;Col:=Min_Col;endif;endif;endloop;returnResult;endSpiral;procedurePrint(Item:Array_Type)isNum_Digits:constantFloat:=Log(X=>Float(Item'Length(1)**2),Base=>10.0);Spacing:constantPositive:=Integer(Num_Digits)+2;beginforIinItem'range(1)loopforJinItem'range(2)loopPut(Item=>Item(I,J),Width=>Spacing);endloop;New_Line;endloop;endPrint;beginPrint(Spiral(5));endSpiral_Square;
The following is a variant using a different algorithm (which can also be used recursively):
functionSpiral(N:Positive)returnArray_TypeisResult:Array_Type(1..N,1..N);Left:Positive:=1;Right:Positive:=N;Top:Positive:=1;Bottom:Positive:=N;Index:Natural:=0;beginwhileLeft<RightloopforIinLeft..Right-1loopResult(Top,I):=Index;Index:=Index+1;endloop;forJinTop..Bottom-1loopResult(J,Right):=Index;Index:=Index+1;endloop;forIinreverseLeft+1..RightloopResult(Bottom,I):=Index;Index:=Index+1;endloop;forJinreverseTop+1..BottomloopResult(J,Left):=Index;Index:=Index+1;endloop;Left:=Left+1;Right:=Right-1;Top:=Top+1;Bottom:=Bottom-1;endloop;Result(Top,Left):=Index;returnResult;endSpiral;
INT empty=0;PROC spiral = (INT n)[,]INT: ( INT dx:=1, dy:=0; # Starting increments # INT x:=0, y:=0; # Starting location # [0:n-1,0:n-1]INT my array; FOR y FROM LWB my array TO UPB my array DO FOR x FROM LWB my array TO UPB my array DO my array[x,y]:=empty OD OD; FOR i TO n**2 DO my array[x,y] := i; INT nx:=x+dx, ny:=y+dy; IF ( 0<=nx AND nx<n AND 0<=ny AND ny<n | my array[nx,ny] = empty | FALSE ) THEN x:=nx; y:=ny ELSE INT swap:=dx; dx:=-dy; dy:=swap; x+:=dx; y+:=dy FI OD; my array); PROC print spiral = ([,]INT my array)VOID:( FOR y FROM LWB my array TO UPB my array DO FOR x FROM LWB my array TO UPB my array DO print(whole(my array[x,y],-3)) OD; print(new line) OD); print spiral(spiral(5))
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
(ES6)
---------------------- SPIRAL MATRIX ----------------------- spiral :: Int -> [[Int]]onspiral(n)scriptgoon|λ|(rows,cols,start)if0<rowsthen{enumFromTo(start,start+pred(cols))}&¬map(my|reverse|,¬transpose(|λ|(cols,pred(rows),start+cols)))else{{}}endifend|λ|endscriptgo's|λ|(n,n,0)endspiral--------------------------- TEST -------------------------onrunwikiTable(spiral(5),¬false,¬"text-align:center;width:12em;height:12em;table-layout:fixed;")endrun-------------------- WIKI TABLE FORMAT --------------------- wikiTable :: [Text] -> Bool -> Text -> TextonwikiTable(lstRows,blnHdr,strStyle)scriptfWikiRowson|λ|(lstRow,iRow)setstrDelimtoif_(blnHdrand(iRow=0),"!","|")setstrDbltostrDelim&strDelimlinefeed&"|-"&linefeed&strDelim&space&¬intercalateS(space&strDbl&space,lstRow)end|λ|endscriptlinefeed&"{| class=\"wikitable\" "&¬if_(strStyle≠"","style=\""&strStyle&"\"","")&¬intercalateS("",¬map(fWikiRows,lstRows))&linefeed&"|}"&linefeedendwikiTable------------------------- GENERIC -------------------------- comparing :: (a -> b) -> (a -> a -> Ordering)oncomparing(f)scripton|λ|(a,b)tellmReturn(f)setfato|λ|(a)setfbto|λ|(b)iffa<fbthen-1elseiffa>fbthen1else0endifendtellend|λ|endscriptendcomparing-- concatMap :: (a -> [b]) -> [a] -> [b]onconcatMap(f,xs)setlngtolengthofxssetaccto{}tellmReturn(f)repeatwithifrom1tolngsetacctoacc&(|λ|(itemiofxs,i,xs))endrepeatendtellif{text,string}containsclassofxsthenaccastextelseaccendifendconcatMap-- enumFromTo :: Int -> Int -> [Int]onenumFromTo(m,n)ifm≤nthensetlstto{}repeatwithifrommtonsetendoflsttoiendrepeatreturnlstelsereturn{}endifendenumFromTo-- foldl :: (a -> b -> a) -> a -> [b] -> aonfoldl(f,startValue,xs)tellmReturn(f)setvtostartValuesetlngtolengthofxsrepeatwithifrom1tolngsetvto|λ|(v,itemiofxs,i,xs)endrepeatreturnvendtellendfoldl-- if_ :: Bool -> a -> a -> aonif_(bool,x,y)ifboolthenxelseyendifendif_-- intercalateS :: String -> [String] -> StringonintercalateS(sep,xs)set{dlm,mytext item delimiters}to{mytext item delimiters,sep}setstoxsastextsetmytext item delimiterstodlmreturnsendintercalateS-- length :: [a] -> Inton|length|(xs)lengthofxsend|length|-- max :: Ord a => a -> a -> aonmax(x,y)ifx>ythenxelseyendifendmax-- maximumBy :: (a -> a -> Ordering) -> [a] -> aonmaximumBy(f,xs)setcmptomReturn(f)scriptmaxon|λ|(a,b)ifaismissing valueorcmp's|λ|(a,b)<0thenbelseaendifend|λ|endscriptfoldl(max,missing value,xs)endmaximumBy-- Lift 2nd class handler function into 1st class script wrapper-- mReturn :: First-class m => (a -> b) -> m (a -> b)onmReturn(f)ifclassoffisscriptthenfelsescriptproperty|λ|:fendscriptendifendmReturn-- map :: (a -> b) -> [a] -> [b]onmap(f,xs)tellmReturn(f)setlngtolengthofxssetlstto{}repeatwithifrom1tolngsetendoflstto|λ|(itemiofxs,i,xs)endrepeatreturnlstendtellendmap-- pred :: Enum a => a -> aonpred(x)x-1endpred-- Egyptian multiplication - progressively doubling a list, appending-- stages of doubling to an accumulator where needed for binary-- assembly of a target length-- replicate :: Int -> a -> [a]onreplicate(n,a)setoutto{}ifn<1thenreturnoutsetdblto{a}repeatwhile(n>1)if(nmod2)>0thensetouttoout&dblsetnto(ndiv2)setdblto(dbl&dbl)endrepeatreturnout&dblendreplicate-- reverse :: [a] -> [a]on|reverse|(xs)ifclassofxsistextthen(reverseofcharactersofxs)astextelsereverseofxsendifend|reverse|-- Simplified version - assuming rows of unvarying length.-- transpose :: [[a]] -> [[a]]ontranspose(rows)scriptcolson|λ|(_,iCol)scriptcellon|λ|(row)itemiColofrowend|λ|endscriptconcatMap(cell,rows)end|λ|endscriptmap(cols,item1ofrows)endtranspose-- unlines :: [String] -> Stringonunlines(xs)set{dlm,mytext item delimiters}to¬{mytext item delimiters,linefeed}setstrtoxsastextsetmytext item delimiterstodlmstrendunlines-- unwords :: [String] -> Stringonunwords(xs)intercalateS(space,xs)endunwords
| 0 | 1 | 2 | 3 | 4 |
| 15 | 16 | 17 | 18 | 5 |
| 14 | 23 | 24 | 19 | 6 |
| 13 | 22 | 21 | 20 | 7 |
| 12 | 11 | 10 | 9 | 8 |
spiralMatrix:function[n][m:newarray.of:@[n,n]null[dx,dy,x,y]:[1,0,0,0]loop0..dec n^2'i[m\[y]\[x]:i[nx,ny]:@[x+dx,y+dy]if?and?[and?[in?nx0..n-1][in?ny0..n-1]][null?m\[ny]\[nx]][[x,y]:@[nx,ny]]else[bdx:dx[dx,dy]:@[negdy,bdx][x,y]:@[x+dx,y+dy]]]returnm]loopspiralMatrix5'row[printmaprow'x->padto:stringx4]
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
ahk forum:discussion
n:=5,dx:=x:=y:=v:=1,dy:=0Loop%n*n{a_%x%_%y%:=v++nx:=x+dx,ny:=y+dyIf(1>nx||nx>n||1>ny||ny>n||a_%nx%_%ny%)t:=dx,dx:=-dy,dy:=tx:=x+dx,y:=y+dy}Loop%n%{ ; generate printouty:=A_Index ; for each rowLoop%n% ; and for each columns.=a_%A_Index%_%y%"`t" ; attach stored indexs.="`n" ; row is complete}MsgBox%s% ; show output/*---------------------------1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9---------------------------*/
# syntax: GAWK -f SPIRAL_MATRIX.AWK [-v offset={0|1}] [size]# converted from BBC BASICBEGIN{# offset: "0" prints 0 to size^2-1 while "1" prints 1 to size^2offset=(offset=="")?0:offsetsize=(ARGV[1]=="")?5:ARGV[1]if(offset!~/^[01]$/){exit(1)}if(size!~/^[0-9]+$/){exit(1)}bot_col=bot_row=0top_col=top_row=size-1direction=col=row=0for(i=0;i<=size*size-1;i++){# buildarr[col,row]=i+offsetif(direction==0){if(col<top_col){col++}else{direction=1;row++;bot_row++}}elseif(direction==1){if(row<top_row){row++}else{direction=2;col--;top_col--}}elseif(direction==2){if(col>bot_col){col--}else{direction=3;row--;top_row--}}elseif(direction==3){if(row>bot_row){row--}else{direction=0;col++;bot_col++}}}width=length(size^2-1+offset)+1# column widthfor(i=0;i<size;i++){# printfor(j=0;j<size;j++){printf("%*d",width,arr[j,i])}printf("\n")}exit(0)}
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
N%=5@%=LENSTR$(N%*N%-1)+1BotCol%=0:TopCol%=N%-1BotRow%=0:TopRow%=N%-1DIMMatrix%(TopCol%,TopRow%)Dir%=0:Col%=0:Row%=0FORI%=0TON%*N%-1Matrix%(Col%,Row%)=I%PRINTTAB(Col%*@%,Row%)I%CASEDir%OFWHEN0:IFCol%<TopCol%THENCol%+=1ELSEDir%=1:Row%+=1:BotRow%+=1WHEN1:IFRow%<TopRow%THENRow%+=1ELSEDir%=2:Col%-=1:TopCol%-=1WHEN2:IFCol%>BotCol%THENCol%-=1ELSEDir%=3:Row%-=1:TopRow%-=1WHEN3:IFRow%>BotRow%THENRow%-=1ELSEDir%=0:Col%+=1:BotCol%+=1ENDCASENEXTEND
Note: program produces a matrix starting from 1 instead of 0, because task says "natural numbers".
#include<stdio.h>#include<stdlib.h>#define valid(i, j) 0 <= i && i < m && 0 <= j && j < n && !s[i][j]intmain(intc,char**v){inti,j,m=0,n=0;/* default size: 5 */if(c>=2)m=atoi(v[1]);if(c>=3)n=atoi(v[2]);if(m<=0)m=5;if(n<=0)n=m;int**s=calloc(1,sizeof(int*)*m+sizeof(int)*m*n);s[0]=(int*)(s+m);for(i=1;i<m;i++)s[i]=s[i-1]+n;intdx=1,dy=0,val=0,t;for(i=j=0;valid(i,j);i+=dy,j+=dx){for(;valid(i,j);j+=dx,i+=dy)s[i][j]=++val;j-=dx;i-=dy;t=dy;dy=dx;dx=-t;}for(t=2;val/=10;t++);for(i=0;i<m;i++)for(j=0;j<n||!putchar('\n');j++)printf("%*d",t,s[i][j]);return0;}
Recursive method, width and height given on command line:
#include<stdio.h>#include<stdlib.h>intspiral(intw,inth,intx,inty){returny?w+spiral(h-1,w,y-1,w-x-1):x;}intmain(intargc,char**argv){intw=atoi(argv[1]),h=atoi(argv[2]),i,j;for(i=0;i<h;i++){for(j=0;j<w;j++)printf("%4d",spiral(w,h,j,i));putchar('\n');}return0;}
Solution based on theJ hints:
publicint[,]Spiral(intn){int[,]result=newint[n,n];intpos=0;intcount=n;intvalue=-n;intsum=-1;do{value=-1*value/n;for(inti=0;i<count;i++){sum+=value;result[sum/n,sum%n]=pos++;}value*=n;count--;for(inti=0;i<count;i++){sum+=value;result[sum/n,sum%n]=pos++;}}while(count>0);returnresult;}// Method to print arrays, pads numbers so they line up in columnspublicvoidPrintArray(int[,]array){intn=(array.GetLength(0)*array.GetLength(1)-1).ToString().Length+1;for(inti=0;i<array.GetLength(0);i++){for(intj=0;j<array.GetLength(1);j++){Console.Write(array[i,j].ToString().PadLeft(n,' '));}Console.WriteLine();}}
Translated proper C++ solution:
//generate spiral matrix for given Nint[,]CreateMatrix(intn){int[]dx={0,1,0,-1},dy={1,0,-1,0};intx=0,y=-1,c=0;int[,]m=newint[n,n];for(inti=0,im=0;i<n+n-1;++i,im=i%4)for(intj=0,jlen=(n+n-i)/2;j<jlen;++j)m[x+=dx[im],y+=dy[im]]=++c;returnn;}//print aligned matrixvoidPrint(int[,]matrix){varlen=(int)Math.Ceiling(Math.Log10(m.GetLength(0)*m.GetLength(1)))+1;for(vary=0;y<m.GetLength(1);y++){for(varx=0;x<m.GetLength(0);x++){Console.Write(m[y,x].ToString().PadRight(len,' '));}Console.WriteLine();}}
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespacespiralmat{classspiral{publicstaticintlev;intlev_lim,count,bk,cd,low,l,m;spiral(){lev=lev_lim=count=bk=cd=low=l=m=0;}voidlevel(intn1,intr,intc){lev_lim=n1%2==0?n1/2:(n1+1)/2;if((r<=lev_lim)&&(c<=lev_lim))lev=Math.Min(r,c);else{bk=r>c?(n1+1)-r:(n1+1)-c;low=Math.Min(r,c);if(low<=lev_lim)cd=low;lev=cd<bk?cd:bk;}}intfunc(intn2,intxo,intlo){l=xo;m=lo;count=0;level(n2,l,m);for(intak=1;ak<lev;ak++)count+=4*(n2-1-2*(ak-1));returncount;}publicstaticvoidMain(string[]args){spiralob=newspiral();Console.WriteLine("Enter Order..");intn=int.Parse(Console.ReadLine());Console.WriteLine("The Matrix of {0} x {1} Order is=>\n",n,n);for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)Console.Write("{0,3:D} ",ob.func(n,i,j)+Convert.ToInt32(((j>=i)&&(i==lev))?((j-i)+1):((j==((n+1)-lev)&&(i>lev)&&(i<=j)))?(n-2*(lev-1)+(i-1)-(n-j)):((i==((n+1)-lev)&&(j<i)))?((n-2*(lev-1))+((n-2*(lev-1))-1)+(i-j)):((j==lev)&&(i>lev)&&(i<((n+1)-lev)))?((n-2*(lev-1))+((n-2*(lev-1))-1)+((n-2*(lev-1))-1)+(((n+1)-lev)-i)):0));Console.WriteLine();}Console.ReadKey();}}}
INPUT:-Enterorder..5OUTPUT:-TheMatrixof5x5Orderis=>12345161718196152425207142322218131211109INPUT:-Enterorder..6OUTPUT:-TheMatrixof6x6Orderis=>123456202122232471932333425818313635269173029282710161514131211
#include<vector>#include<memory>// for auto_ptr#include<cmath>// for the ceil and log10 and floor functions#include<iostream>#include<iomanip>// for the setw functionusingnamespacestd;typedefvector<int>IntRow;typedefvector<IntRow>IntTable;auto_ptr<IntTable>getSpiralArray(intdimension){auto_ptr<IntTable>spiralArrayPtr(newIntTable(dimension,IntRow(dimension)));intnumConcentricSquares=static_cast<int>(ceil(static_cast<double>(dimension)/2.0));intj;intsideLen=dimension;intcurrNum=0;for(inti=0;i<numConcentricSquares;i++){// do top sidefor(j=0;j<sideLen;j++)(*spiralArrayPtr)[i][i+j]=currNum++;// do right sidefor(j=1;j<sideLen;j++)(*spiralArrayPtr)[i+j][dimension-1-i]=currNum++;// do bottom sidefor(j=sideLen-2;j>-1;j--)(*spiralArrayPtr)[dimension-1-i][i+j]=currNum++;// do left sidefor(j=sideLen-2;j>0;j--)(*spiralArrayPtr)[i+j][i]=currNum++;sideLen-=2;}returnspiralArrayPtr;}voidprintSpiralArray(constauto_ptr<IntTable>&spiralArrayPtr){size_tdimension=spiralArrayPtr->size();intfieldWidth=static_cast<int>(floor(log10(static_cast<double>(dimension*dimension-1))))+2;size_tcol;for(size_trow=0;row<dimension;row++){for(col=0;col<dimension;col++)cout<<setw(fieldWidth)<<(*spiralArrayPtr)[row][col];cout<<endl;}}intmain(){printSpiralArray(getSpiralArray(5));}
C++ solution done properly:
#include<vector>#include<iostream>usingnamespacestd;intmain(){constintn=5;constintdx[]={0,1,0,-1},dy[]={1,0,-1,0};intx=0,y=-1,c=0;vector<vector<int>>m(n,vector<int>(n));for(inti=0,im=0;i<n+n-1;++i,im=i%4)for(intj=0,jlen=(n+n-i)/2;j<jlen;++j)m[x+=dx[im]][y+=dy[im]]=++c;for(auto&r:m){for(auto&v:r)cout<<v<<' ';cout<<endl;}}
Based on theJ hints (almost as incomprehensible, maybe)
(defnspiral[n](let[cyc(cycle[1n-1(-n)])](->>(range(decn)0-1)(mapcat#(repeat2%))(consn)(mapcat#(repeat%2%)cyc)(reductions+)(map vector(range0(*nn)))(sort-bysecond)(mapfirst)))(let[n5](clojure.pprint/cl-formattrue(str" ~{~<~%~,"(*n3)":;~2d ~>~}~%")(spiraln)))
Recursive generation:
(defnspiral-matrix[mn&[start]](let[row(list(map#(+start%)(rangem)))](if(=1n)row(concatrow(mapreverse(apply maplist(spiral-matrix(decn)m(+startm))))))))(defnspiral[nm](spiral-matrixnm1))
# Let's say you want to arrange the first N-squared natural numbers# in a spiral, where you fill in the numbers clockwise, starting from# the upper left corner. This code computes the values for each x/y# coordinate of the square. (Of course, you could precompute the values# iteratively, but what fun is that?)spiral_value=(x, y, n) ->prior_legs=N:0E:1S:2W:3edge_run=(edge_offset) ->N:->edge_offset.W-edge_offset.NE:->edge_offset.N-edge_offset.ES:->edge_offset.E-edge_offset.SW:->edge_offset.S-edge_offset.Wedge_offset=N:yE:n-1-xS:n-1-yW:xmin_edge_offset=nfordirofedge_offsetifedge_offset[dir]<min_edge_offsetmin_edge_offset=edge_offset[dir]border=dirinner_square_edge=n-2*min_edge_offsetcorner_offset=n*n-inner_square_edge*inner_square_edgecorner_offset+=prior_legs[border]*(inner_square_edge-1)corner_offset+edge_run(edge_offset)[border]()spiral_matrix=(n) -># return a nested array expressionforyin[0...n]forxin[0...n]spiral_valuex,y,ndo->fornin[6,7]console.log"\n----Spiral n=#{n}"console.logspiral_matrixn
> coffee spiral.coffee ----Spiral n=6[ [ 0, 1, 2, 3, 4, 5 ], [ 19, 20, 21, 22, 23, 6 ], [ 18, 31, 32, 33, 24, 7 ], [ 17, 30, 35, 34, 25, 8 ], [ 16, 29, 28, 27, 26, 9 ], [ 15, 14, 13, 12, 11, 10 ] ]----Spiral n=7[ [ 0, 1, 2, 3, 4, 5, 6 ], [ 23, 24, 25, 26, 27, 28, 7 ], [ 22, 39, 40, 41, 42, 29, 8 ], [ 21, 38, 47, 48, 43, 30, 9 ], [ 20, 37, 46, 45, 44, 31, 10 ], [ 19, 36, 35, 34, 33, 32, 11 ], [ 18, 17, 16, 15, 14, 13, 12 ] ]
(defunspiral(rowscolumns)(do((N(*rowscolumns))(spiral(make-array(listrowscolumns):initial-elementnil))(dx1)(dy0)(x0)(y0)(i0(1+i)))((=iN)spiral)(setf(arefspiralyx)i)(let((nx(+xdx))(ny(+ydy)))(cond((and(<-1nxcolumns)(<-1nyrows)(null(arefspiralnynx)))(setfxnxyny))(t(psetfdx(-dy)dydx)(setfx(+xdx)y(+ydy)))))))
> (pprint (spiral 6 6))#2A((0 1 2 3 4 5) (19 20 21 22 23 6) (18 31 32 33 24 7) (17 30 35 34 25 8) (16 29 28 27 26 9) (15 14 13 12 11 10))> (pprint (spiral 5 3))#2A((0 1 2) (11 12 3) (10 13 4) (9 14 5) (8 7 6))
Recursive generation:
(defunspiral(mn&optional(start1))(let((row(list(loopforxfrom0to(1-m)collect(+xstart)))))(if(=1n)row;; first row, plus (n-1) x m spiral rotated 90 degrees(appendrow(map'list#'reverse(apply#'mapcar#'list(spiral(1-n)m(+startm))))))));; test(loopforrowin(spiral43)do(formatt"~{~4d~^~}~%"row))
voidmain(){importstd.stdio;enumn=5;int[n][n]M;intpos,side=n;foreach(immutablei;0..n/2+n%2){foreach(immutablej;0..side)M[i][i+j]=pos++;foreach(immutablej;1..side)M[i+j][n-1-i]=pos++;foreach_reverse(immutablej;0..side-1)M[n-1-i][i+j]=pos++;foreach_reverse(immutablej;1..side-1)M[i+j][i]=pos++;side-=2;}writefln("%(%(%2d %)\n%)",M);}
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
Using a generator for any rectangular array:
importstd.stdio;/// 2D spiral generatorconststructSpiral{intw,h;intopApply(intdelegate(refint,refint,refint)dg){intidx,x,y,xy,dx=1,dy;int[]subLen=[w,h-1];voidturn(){autot=-dy;dy=dx;dx=t;xy=1-xy;}voidforward(intd=1){x+=d*dx;y+=d*dy;idx+=d;}Bye:while(true){if(subLen[xy]==0)break;foreach(_;0..subLen[xy]--)if(dg(idx,x,y))breakBye;elseforward();forward(-1);turn();forward();}return0;}}int[][]spiralMatrix(intw,inth){autom=newtypeof(return)(h,w);foreach(value,x,y;Spiral(w,h))m[y][x]=value;returnm;}voidmain(){foreach(r;spiralMatrix(9,4))writefln("%(%2d %)",r);}
0 1 2 3 4 5 6 7 821 22 23 24 25 26 27 28 920 35 34 33 32 31 30 29 1019 18 17 16 15 14 13 12 11
$p1=f$integer(p1)$max=p1*p1$$i=0$r=1$rd=0$c=1$cd=1$loop:$a'r'_'c'=i$nr=r+rd$nc=c+cd$ifnr.eq.0.or.nc.eq.0.or.nr.gt.p1.or.nc.gt.p1.or.f$type(a'nr'_'nc').nes.""$then$gosubchange_directions$endif$r=r+rd$c=c+cd$i=i+1$ifi.lt.maxthen$gotoloop$length=f$length(f$string(max-1))$r=1$loop2:$c=1$output=""$loop3:$output=output+f$fao("!#UL ",length,a'r'_'c')$c=c+1$ifc.le.p1then$gotoloop3$writesys$outputoutput$r=r+1$ifr.le.p1then$gotoloop2$exit$$change_directions:$ifrd.eq.0.andcd.eq.1$then$rd=1$cd=0$else$ifrd.eq.1.and.cd.eq.0$then$rd=0$cd=-1$else$ifrd.eq.0.and.cd.eq.-1$then$rd=-1$cd=0$else$rd=0$cd=1$endif$endif$endif$return
$ @spiral_matrix 3 0 1 2 7 8 3 6 5 4 $ @spiral_matrix 5 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8...
This code actually creates a matrix in memory and stores values in the matrix, instead of just simulating one by drawing the pattern. It can also create matrices of any size and the matrices don't have to be square. It works by creating a rectangle of the same size as the matrix. It enters the values in the matrix along circumference of the matrix. It then uses the Windows library routine "InflateRect" to decrease the size of the rectangle until the whole matrix is filled with spiraling values. Since a rectangle can be any size and doesn't have to be square, it works with any size matrix, including non-square matrices.
typeTMatrix=arrayofarrayofdouble;procedureDisplayMatrix(Memo:TMemo;Mat:TMatrix);{Display specified matrix}varX,Y:integer;varS:string;beginS:='';forY:=0toHigh(Mat[0])dobeginS:=S+'[';forX:=0toHigh(Mat)doS:=S+Format('%4.0f',[Mat[X,Y]]);S:=S+']'+#$0D#$0A;end;Memo.Lines.Add(S);end;procedureMakeSpiralMatrix(varMat:TMatrix;SizeX,SizeY:integer);{Create a spiral matrix of specified size}varInx:integer;varR:TRect;procedureDoRect(R:TRect;varInx:integer);{Create on turn of the spiral base on the rectangle}varX,Y:integer;begin{Do top part of rectangle}forX:=R.LefttoR.RightdobeginMat[X,R.Top]:=Inx;Inc(Inx);end;{Do Right part of rectangle}forY:=R.Top+1toR.BottomdobeginMat[R.Right,Y]:=Inx;Inc(Inx);end;{Do bottom part of rectangle}forX:=R.Right-1downtoR.LeftdobeginMat[X,R.Bottom]:=Inx;Inc(Inx);end;{Do left part of rectangle}forY:=R.Bottom-1downtoR.Top+1dobeginMat[R.Left,Y]:=Inx;Inc(Inx);end;end;begin{Set matrix size}SetLength(Mat,SizeX,SizeY);{create matching rectangle}R:=Rect(0,0,SizeX-1,SizeY-1);Inx:=0;{draw and deflate rectangle until spiral is done}while(R.Left<=R.Right)and(R.Top<=R.Bottom)dobeginDoRect(R,Inx);InflateRect(R,-1,-1);end;end;procedureSpiralMatrix(Memo:TMemo);{Display spiral matrix}varMat:TMatrix;beginMemo.Lines.Add('5x5 Matrix');MakeSpiralMatrix(Mat,5,5);DisplayMatrix(Memo,Mat);Memo.Lines.Add('8x8 Matrix');MakeSpiralMatrix(Mat,8,8);DisplayMatrix(Memo,Mat);Memo.Lines.Add('14x8 Matrix');MakeSpiralMatrix(Mat,14,8);DisplayMatrix(Memo,Mat);end;
5x5 Matrix[ 0 1 2 3 4][ 15 16 17 18 5][ 14 23 24 19 6][ 13 22 21 20 7][ 12 11 10 9 8]8x8 Matrix[ 0 1 2 3 4 5 6 7][ 27 28 29 30 31 32 33 8][ 26 47 48 49 50 51 34 9][ 25 46 59 60 61 52 35 10][ 24 45 58 63 62 53 36 11][ 23 44 57 56 55 54 37 12][ 22 43 42 41 40 39 38 13][ 21 20 19 18 17 16 15 14]14x8 Matrix[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13][ 39 40 41 42 43 44 45 46 47 48 49 50 51 14][ 38 71 72 73 74 75 76 77 78 79 80 81 52 15][ 37 70 95 96 97 98 99 100 101 102 103 82 53 16][ 36 69 94 111 110 109 108 107 106 105 104 83 54 17][ 35 68 93 92 91 90 89 88 87 86 85 84 55 18][ 34 67 66 65 64 63 62 61 60 59 58 57 56 19][ 33 32 31 30 29 28 27 26 25 24 23 22 21 20]Elapsed Time: 11.242 ms.
First, some quick data types to unclutter the actual algorithm.
/** Missing scalar multiplication, but we don't need it. */def makeVector2(x, y) { return def vector { to x() { return x } to y() { return y } to add(other) { return makeVector2(x + other.x(), y + other.y()) } to clockwise() { return makeVector2(-y, x) } }}/** Bugs: (1) The printing is specialized. (2) No bounds check on the column. */def makeFlex2DArray(rows, cols) { def storage := ([null] * (rows * cols)).diverge() return def flex2DArray { to __printOn(out) { for y in 0..!rows { for x in 0..!cols { out.print(<import:java.lang.makeString>.format("%3d", [flex2DArray[y, x]])) } out.println() } } to get(r, c) { return storage[r * cols + c] } to put(r, c, v) { storage[r * cols + c] := v } }}def spiral(size) { def array := makeFlex2DArray(size, size) var i := -1 # Counter of numbers to fill var p := makeVector2(0, 0) # "Position" var dp := makeVector2(1, 0) # "Velocity" # If the cell we were to fill next (even after turning) is full, we're done. while (array[p.y(), p.x()] == null) { array[p.y(), p.x()] := (i += 1) # Fill cell def next := p + dp # Look forward # If the cell we were to fill next is already full, then turn clockwise. # Gimmick: If we hit the edges of the array, by the modulo we wrap around # and see the already-filled cell on the opposite edge. if (array[next.y() %% size, next.x() %% size] != null) { dp := dp.clockwise() } # Move forward p += dp } return array}Example:
? print(spiral(5)) 0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
proc mkspiral n . t[] . subr side for i to l ind += d t[ind] = cnt cnt += 1 . . len t[] n * n l = n while cnt < len t[] d = 1 side l -= 1 d = n side d = -1 side l -= 1 d = -n side ..n = 5mkspiral n t[]numfmt 0 3for i to n * n write t[i] if i mod n = 0 print "" ..
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
defmoduleRCdodefspiral_matrix(n)dowide=length(to_char_list(n*n-1))fmt=String.duplicate("~#{wide}w ",n)<>"~n"runs=Enum.flat_map(n..1,&[&1,&1])|>tldelta=Stream.cycle([{0,1},{1,0},{0,-1},{-1,0}])running(Enum.zip(runs,delta),0,-1,[])|>Enum.with_index|>Enum.sort|>Enum.chunk(n)|>Enum.each(fnrow->:io.formatfmt,(for{_,i}<-row,do:i)end)enddefprunning([{run,{dx,dy}}|rest],x,y,track)donew_track=Enum.reduce(1..run,track,fni,acc->[{x+i*dx,y+i*dy}|acc]end)running(rest,x+run*dx,y+run*dy,new_track)enddefprunning([],_,_,track),do:track|>Enum.reverseendRC.spiral_matrix(5)
The other way
defmoduleRCdodefspiral_matrix(n)dowide=String.length(to_string(n*n-1))fmt=String.duplicate("~#{wide}w ",n)<>"~n"right(n,n-1,0,[])|>Enum.reverse|>Enum.with_index|>Enum.sort|>Enum.chunk(n)|>Enum.each(fnrow->:io.formatfmt,(for{_,i}<-row,do:i)end)enddefright(n,side,i,coordinates)dodown(n,side,i,Enum.reduce(0..side,coordinates,fnj,acc->[{i,i+j}|acc]end))enddefdown(_,0,_,coordinates),do:coordinatesdefdown(n,side,i,coordinates)doleft(n,side-1,i,Enum.reduce(1..side,coordinates,fnj,acc->[{i+j,n-1-i}|acc]end))enddefleft(n,side,i,coordinates)doup(n,side,i,Enum.reduce(side..0,coordinates,fnj,acc->[{n-1-i,i+j}|acc]end))enddefup(_,0,_,coordinates),do:coordinatesdefup(n,side,i,coordinates)doright(n,side-1,i+1,Enum.reduce(side..1,coordinates,fnj,acc->[{i+j,i}|acc]end))endendRC.spiral_matrix(5)
Another way
defmoduleRCdodefspiral_matrix(n)dofmt=String.duplicate("~#{length(to_char_list(n*n-1))}w ",n)<>"~n"Enum.flat_map(n..1,&[&1,&1])|>tl|>Enum.reduce({{0,-1},{0,1},[]},fnrun,{{x,y},{dx,dy},acc}->side=fori<-1..run,do:{x+i*dx,y+i*dy}{{x+run*dx,y+run*dy},{dy,-dx},acc++side}end)|>elem(2)|>Enum.with_index|>Enum.sort|>Enum.map(fn{_,i}->iend)|>Enum.chunk(n)|>Enum.each(fnrow->:io.formatfmt,rowend)endendRC.spiral_matrix(5)
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
function spiral(integer dimension) integer side, curr, curr2 sequence s s = repeat(repeat(0,dimension),dimension) side = dimension curr = 0 for i = 0 to floor(dimension/2) do for j = 1 to side-1 do s[i+1][i+j] = curr -- top curr2 = curr + side-1 s[i+j][i+side] = curr2 -- right curr2 += side-1 s[i+side][i+side-j+1] = curr2 -- bottom curr2 += side-1 s[i+side-j+1][i+1] = curr2 -- left curr += 1 end for curr = curr2 + 1 side -= 2 end for if remainder(dimension,2) then s[floor(dimension/2)+1][floor(dimension/2)+1] = curr end if return send function? spiral(5)
{ {0,1,2,3,4}, {15,16,17,18,5}, {14,23,24,19,6}, {13,22,21,20,7}, {12,11,10,9,8}}No fancy schmancy elegance here, just putting the numbers in the right place (though I commend the elegance)...
letSpiraln=letsq=Array2D.createnn0// Set up an output arrayletnCur=ref-1// Current value being insertedletNextN()=nCur:=(!nCur+1);!nCur// Inc current value and return new valueletFrameinset=// Create the "frame" at an offset from the outsideletrangeF=[inset..(n-inset-2)]// Range we use going forwardletrangeR=[(n-inset-1)..(-1)..(inset+1)]// Range we use going backwardrangeF|>Seq.iter(funi->sq.[inset,i]<-NextN())// Top of framerangeF|>Seq.iter(funi->sq.[i,n-inset-1]<-NextN())// Right side of framerangeR|>Seq.iter(funi->sq.[n-inset-1,i]<-NextN())// Bottom of framerangeR|>Seq.iter(funi->sq.[i,inset]<-NextN())// Left side of frame[0..(n/2-1)]|>Seq.iter(funi->Framei)// Fill in all framesifn&&&1=1thensq.[n/2,n/2]<-n*n-1// If n is odd, fill in the last single valuesq// Return our output array
This is an implementation of Joey Tuttle's method for computing a spiral directly as a list and then reshaping it into a matrix, as described in theJ entry. To summarize, we construct a list withn*n elements by following some simple rules, then take its cumulative sum, and finally its inverse permutation (or grade in J parlance). This gives us a list which can be reshaped to the final matrix.
USING:arraysgroupingiokernelmathmath.combinatoricsmath.rangesmath.statisticsprettyprintsequencessequences.repeating;IN:rosetta-code.spiral-matrix:counts(n--seq)1[a,b]2repeatrest;:vals(n--seq)[1swap2dup[neg]bi@4array][2*1-cycle]bi;:evJKT2(n--seq)[counts][vals]bi[<array>]2mapconcat;:spiral(n--matrix)[evJKT2cum-suminverse-permutation][group]bi;:spiral-demo(--)5 9[spiralsimple-table.nl]bi@;MAIN:spiral-demo
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 80 1 2 3 4 5 6 7 831 32 33 34 35 36 37 38 930 55 56 57 58 59 60 39 1029 54 71 72 73 74 61 40 1128 53 70 79 80 75 62 41 1227 52 69 78 77 76 63 42 1326 51 68 67 66 65 64 43 1425 50 49 48 47 46 45 44 1524 23 22 21 20 19 18 17 16
PROGRAMSPIRALIMPLICIT NONEINTEGER,PARAMETER::size=5INTEGER::i,x=0,y=1,count=size,n=0INTEGER::array(size,size)DOi=1,countx=x+1array(x,y)=nn=n+1END DO DOcount=count-1DOi=1,county=y+1array(x,y)=nn=n+1END DO DOi=1,countx=x-1array(x,y)=nn=n+1END DO IF(n>size*size-1)EXITcount=count-1DOi=1,county=y-1array(x,y)=nn=n+1END DO DOi=1,countx=x+1array(x,y)=nn=n+1END DO IF(n>size*size-1)EXIT END DO DOy=1,sizeDOx=1,sizeWRITE(*,"(I4)",ADVANCE="NO")array(x,y)END DO WRITE(*,*)END DOEND PROGRAMSPIRAL
' FB 1.05.0 Win64EnumDirectionacrossdownbackupEndEnumDimAsIntegernDoInput"Enter size of matrix ";nLoopUntiln>0Dimspiral(1Ton,1Ton)AsInteger'' all zero by default' enter the numbers 0 to (n^2 - 1) spirally in the matrixDimAsIntegerrow=1,col=1,lowRow=1,highRow=n,lowCol=1,highCol=nDimdAsDirection=acrossForiAsInteger=0To(n*n-1)spiral(row,col)=iSelectCasedCaseacrosscol+=1Ifcol>highColThencol=highColrow+=1d=downEndifCasedownrow+=1Ifrow>highRowThenrow=highRowcol-=1d=backEndifCasebackcol-=1Ifcol<lowColThencol=lowColrow-=1d=uplowRow+=1EndIfCaseuprow-=1Ifrow<lowRowThenrow=lowRowcol+=1d=acrosshighRow-=1lowCol+=1highCol-=1EndIfEndSelectNext' print spiral matrix if n < 20PrintIfn<20ThenForiAsInteger=1TonForjAsInteger=1TonPrintUsing"####";spiral(i,j);NextjPrintNextiElsePrint"Matrix is too big to display on 80 column console"EndIfPrintPrint"Press any key to quit"Sleep
Enter size of matrix ? 5 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
void local fn SpiralMatrix( size as int ) int t = 0, b = size - 1, l = 0, r = size - 1 int value = 0, i, j while ( t <= b && l <= r) { for i = l to r mda(t,i) = value++ next t++ for i = t to b mda(i,r) = value++ next r-- if ( t <= b ) for i = r to l step -1 mda(b,i) = value++ next b-- end if if ( l <= r ) for i = b to t step -1 mda(i,l) = value++ next l++ end if wend for i = 0 to size -1 for j = 0 to size - 1 printf @"%2d \b",mda_integer(i,j) next print nextend fnfn SpiralMatrix( 5 )HandleEvents0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
# Spiral matrix with numbers 1 .. n<sup>2</sup>, more natural in GAPSpiralMatrix:=function(n)locali,j,k,di,dj,p,vi,vj,imin,imax,jmin,jmax;a:=NullMat(n,n);vi:=[1,0,-1,0];vj:=[0,1,0,-1];imin:=0;imax:=n;jmin:=1;jmax:=n+1;p:=1;di:=vi[p];dj:=vj[p];i:=1;j:=1;forkin[1..n*n]doa[j][i]:=k;i:=i+di;j:=j+dj;ifi<iminori>imaxorj<jminorj>jmaxtheni:=i-di;j:=j-dj;p:=RemInt(p,4)+1;di:=vi[p];dj:=vj[p];i:=i+di;j:=j+dj;ifp=1thenimax:=imax-1;elifp=2thenjmax:=jmax-1;elifp=3thenimin:=imin+1;elsejmin:=jmin+1;fi;fi;od;returna;end;PrintArray(SpiralMatrix(5));# [ [ 1, 2, 3, 4, 5 ],# [ 16, 17, 18, 19, 6 ],# [ 15, 24, 25, 20, 7 ],# [ 14, 23, 22, 21, 8 ],# [ 13, 12, 11, 10, 9 ] ]
packagemainimport("fmt""strconv")varn=5funcmain(){ifn<1{return}top,left,bottom,right:=0,0,n-1,n-1sz:=n*na:=make([]int,sz)i:=0forleft<right{// work right, along topforc:=left;c<=right;c++{a[top*n+c]=ii++}top++// work down right sideforr:=top;r<=bottom;r++{a[r*n+right]=ii++}right--iftop==bottom{break}// work left, along bottomforc:=right;c>=left;c--{a[bottom*n+c]=ii++}bottom--// work up left sideforr:=bottom;r>=top;r--{a[r*n+left]=ii++}left++}// center (last) elementa[top*n+left]=i// printw:=len(strconv.Itoa(n*n-1))fori,e:=rangea{fmt.Printf("%*d ",w,e)ifi%n==n-1{fmt.Println("")}}}
Naive "path-walking" solution:
enumDirection{East([0,1]),South([1,0]),West([0,-1]),North([-1,0]);privatestatic_nprivatefinalstepDeltaprivateboundprivateDirection(delta){stepDelta=delta}publicstaticsetN(intn){Direction._n=nNorth.bound=0South.bound=n-1West.bound=0East.bound=n-1}publicListmove(i,j){defdir=thisdefnewIJDir=[[i,j],stepDelta].transpose().collect{it.sum()}+dirif(((North.bound)..(South.bound)).contains(newIJDir[0])&&((West.bound)..(East.bound)).contains(newIJDir[1])){newIJDir}else{(++dir).move(i,j)}}publicObjectnext(){switch(this){caseNorth:West.bound++;returnEast;caseEast:North.bound++;returnSouth;caseSouth:East.bound--;returnWest;caseWest:South.bound--;returnNorth;}}}defspiralMatrix={n->if(n<1)return[]defM=(0..<n).collect{[0]*n}defi=0defj=0Direction.n=ndefdir=Direction.East(0..<(n**2)).each{k->M[i][j]=k(i,j,dir)=(k<(n**2-1))\?dir.move(i,j)\:[i,j,dir]}M}
Test:
(1..10).each{n->spiralMatrix(n).each{row->row.each{printf"%5d",it}println()}println()}
0 0 1 3 2 0 1 2 7 8 3 6 5 4 0 1 2 3 11 12 13 4 10 15 14 5 9 8 7 6 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8 0 1 2 3 4 5 19 20 21 22 23 6 18 31 32 33 24 7 17 30 35 34 25 8 16 29 28 27 26 9 15 14 13 12 11 10 0 1 2 3 4 5 6 23 24 25 26 27 28 7 22 39 40 41 42 29 8 21 38 47 48 43 30 9 20 37 46 45 44 31 10 19 36 35 34 33 32 11 18 17 16 15 14 13 12 0 1 2 3 4 5 6 7 27 28 29 30 31 32 33 8 26 47 48 49 50 51 34 9 25 46 59 60 61 52 35 10 24 45 58 63 62 53 36 11 23 44 57 56 55 54 37 12 22 43 42 41 40 39 38 13 21 20 19 18 17 16 15 14 0 1 2 3 4 5 6 7 8 31 32 33 34 35 36 37 38 9 30 55 56 57 58 59 60 39 10 29 54 71 72 73 74 61 40 11 28 53 70 79 80 75 62 41 12 27 52 69 78 77 76 63 42 13 26 51 68 67 66 65 64 43 14 25 50 49 48 47 46 45 44 15 24 23 22 21 20 19 18 17 16 0 1 2 3 4 5 6 7 8 9 35 36 37 38 39 40 41 42 43 10 34 63 64 65 66 67 68 69 44 11 33 62 83 84 85 86 87 70 45 12 32 61 82 95 96 97 88 71 46 13 31 60 81 94 99 98 89 72 47 14 30 59 80 93 92 91 90 73 48 15 29 58 79 78 77 76 75 74 49 16 28 57 56 55 54 53 52 51 50 17 27 26 25 24 23 22 21 20 19 18
Solution based on theJ hints:
importData.ListimportControl.Monadgradexs=mapsnd.sort$zipxs[0..]valuesn=cycle[1,n,-1,-n]countsn=(n:).concatMap(ap(:)return)$[n-1,n-2..1]reshapen=unfoldr(\xs->ifnullxsthenNothingelseJust(splitAtnxs))spiraln=reshapen.grade.scanl1(+).concat$zipWithreplicate(countsn)(valuesn)displayRow=putStrLn.intercalate" ".mapshowmain=mapMdisplayRow$spiral5
An alternative, point-free solution based on the same J source.
importData.ListimportControl.Applicativecounts=tail.reverse.concat.map(replicate2).enumFromTo1values=cycle.((++)<$>mapid<*>mapnegate).(1:).(:[])grade=mapsnd.sort.flipzip[0..]copies=grade.scanl1(+).concat.map(uncurryreplicate).(zip<$>counts<*>values)parts=(<*>)take$(.)<$>(map.take)<*>(iterate.drop)<*>copiesdisp=(>>return()).mapM(putStrLn.intercalate" ".mapshow).partsmain=disp5
Another alternative:
importData.List(transpose)importText.Printf(printf)-- spiral is the first row plus a smaller spiral rotated 90 degspiral0__=[[]]spiralhws=[s..s+w-1]:rot90(spiralw(h-1)(s+w))whererot90=(mapreverse).transpose-- this is sort of hideous, someone may want to fix itmain=mapM_(\row->mapM_((printf"%4d").toInteger)row>>putStrLn"")(spiral1091)
Or less ambitiously,
importData.List(intercalate,transpose)---------------------- SPIRAL MATRIX ---------------------spiral::Int->[[Int]]spiraln=gonn0wheregorowscolsx|0<rows=[x..predcols+x]:fmapreverse(transpose$gocols(predrows)(x+cols))|otherwise=[[]]--------------------------- TEST -------------------------main::IO()main=putStrLn$wikiTable$spiral5--------------------- TABLE FORMATTING -------------------wikiTable::Showa=>[[a]]->StringwikiTable=concat.("{| class=\"wikitable\" style=\"text-align: right;":).("width:12em;height:12em;table-layout:fixed;\"\n|-\n":).return.(<>"\n|}").intercalate"\n|-\n".fmap(('|':).(' ':).intercalate" || ".fmapshow)
| 0 | 1 | 2 | 3 | 4 |
| 15 | 16 | 17 | 18 | 5 |
| 14 | 23 | 24 | 19 | 6 |
| 13 | 22 | 21 | 20 | 7 |
| 12 | 11 | 10 | 9 | 8 |
At first I looked at keeping the filling of the matrix on track using /M[r,c] which fails when out of bounds or if the cell is null, but then I noticed the progression of the row and column increments from corner to corner reminded me of sines and cosines. I'm not sure if the use of a trigonometric function counts as elegance, perversity, or both. The generator could be easily modified to start at an arbitrary corner. Or count down to produce and evolute.
proceduremain(A)# spiral matrixN:=0<integer(\A[1]|5)# N=1... (dfeault 5)WriteMatrix(SpiralMatrix(N))endprocedureWriteMatrix(M)#: write the matrixeveryx:=M[r:=1to*M,c:=1to*M[r]]dowrites(right(\x|"-",3),ifc=*M[r]then"\n"else"")returnendprocedureSpiralMatrix(N)#: create spiral matrixevery(!(M:=list(N))):=list(N)# build empty matrix NxN# setup before starting first turncorner:=0# . corner we're ati:=-1# . cell contentsr:=1;c:=0# . row & colcincr:=integer(sin(0))# . column incruntili>N^2do{rincr:=cincr# row incr follows colcincr:=integer(sin(&pi/2*(corner+:=1)))# col incr at each cornerif(run:=N-corner/2)=0thenbreak# shorten run to 0 at U/R & L/Leveryrunto1by-1doM[r+:=rincr,c+:=cincr]:=i+:=1# move, count, and fill}returnMend
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
100 PROGRAM "SpiralMa.bas"110 TEXT 80120 INPUT PROMPT "Enter size of matrix (max. 10): ":N130 NUMERIC A(1 TO N,1 TO N)140 CALL INIT(A)150 CALL WRITE(A)160 DEF INIT(REF T)170 LET BCOL,BROW,COL,ROW=1:LET TCOL,TROW=N:LET DIR=0180 FOR I=0 TO N^2-1190 LET T(COL,ROW)=I200 SELECT CASE DIR210 CASE 0220 IF ROW<TROW THEN230 LET ROW=ROW+1240 ELSE250 LET DIR=1:LET COL=COL+1:LET BCOL=BCOL+1260 END IF270 CASE 1280 IF COL<TCOL THEN290 LET COL=COL+1300 ELSE310 LET DIR=2:LET ROW=ROW-1:LET TROW=TROW-1320 END IF330 CASE 2340 IF ROW>BROW THEN350 LET ROW=ROW-1360 ELSE370 LET DIR=3:LET COL=COL-1:LET TCOL=TCOL-1380 END IF 390 CASE 3400 IF COL>BCOL THEN410 LET COL=COL-1420 ELSE430 LET DIR=0:LET ROW=ROW+1:LET BROW=BROW+1440 END IF450 END SELECT460 NEXT470 END DEF480 DEF WRITE(REF T)490 FOR I=LBOUND(T,1) TO UBOUND(T,1)500 FOR J=LBOUND(T,2) TO UBOUND(T,2)510 PRINT USING " ##":T(I,J);520 NEXT530 PRINT540 NEXT550 END DEF
This function is the result of somebeautiful insights:
spiral=:,~$[:/:}.@(2#>:@i.@-)+/\@#<:@+:$(,-)@(1&,)spiral50123415161718514232419613222120712111098
Would you likesome hints that will allow you to reimplement it in another language?
These inward spiralling arrays are known as "involutes"; we can also generate outward-spiraling "evolutes", and we can start or end the spiral at any corner, and go in either direction (clockwise or counterclockwise). See the first link (to JSoftware.com).
publicclassBlah{publicstaticvoidmain(String[]args){print2dArray(getSpiralArray(5));}publicstaticint[][]getSpiralArray(intdimension){int[][]spiralArray=newint[dimension][dimension];intnumConcentricSquares=(int)Math.ceil((dimension)/2.0);intj;intsideLen=dimension;intcurrNum=0;for(inti=0;i<numConcentricSquares;i++){// do top sidefor(j=0;j<sideLen;j++){spiralArray[i][i+j]=currNum++;}// do right sidefor(j=1;j<sideLen;j++){spiralArray[i+j][dimension-1-i]=currNum++;}// do bottom sidefor(j=sideLen-2;j>-1;j--){spiralArray[dimension-1-i][i+j]=currNum++;}// do left sidefor(j=sideLen-2;j>0;j--){spiralArray[i+j][i]=currNum++;}sideLen-=2;}returnspiralArray;}publicstaticvoidprint2dArray(int[][]array){for(int[]row:array){for(intelem:row){System.out.printf("%3d",elem);}System.out.println();}}}
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
spiralArray=function(edge){vararr=Array(edge),x=0,y=edge,total=edge*edge--,dx=1,dy=0,i=0,j=0;while(y)arr[--y]=[];while(i<total){arr[y][x]=i++;x+=dx;y+=dy;if(++j==edge){if(dy<0){x++;y++;edge-=2}j=dx;dx=-dy;dy=j;j=0;}}returnarr;}// T E S T:arr=spiralArray(edge=5);for(y=0;y<edge;y++)console.log(arr[y].join(" "));
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
Translating one of the Haskell versions:
(function(n){// Spiral: the first row plus a smaller spiral rotated 90 degrees clockwisefunctionspiral(lngRows,lngCols,nStart){returnlngRows?[range(nStart,(nStart+lngCols)-1)].concat(transpose(spiral(lngCols,lngRows-1,nStart+lngCols)).map(reverse)):[[]];}// rows and columns transposed (for 90 degree rotation)functiontranspose(lst){returnlst.length>1?lst[0].map(function(_,col){returnlst.map(function(row){returnrow[col];});}):lst;}// elements in reverse order (for 90 degree rotation)functionreverse(lst){returnlst.length>1?lst.reduceRight(function(acc,x){returnacc.concat(x);},[]):lst;}// [m..n]functionrange(m,n){returnArray.apply(null,Array(n-m+1)).map(function(x,i){returnm+i;});}// TESTINGvarlstSpiral=spiral(n,n,0);// OUTPUT FORMATTING - JSON and wikiTablefunctionwikiTable(lstRows,blnHeaderRow,strStyle){return'{| class="wikitable" '+(strStyle?'style="'+strStyle+'"':'')+lstRows.map(function(lstRow,iRow){varstrDelim=((blnHeaderRow&&!iRow)?'!':'|');return'\n|-\n'+strDelim+' '+lstRow.map(function(v){returntypeofv==='undefined'?' ':v;}).join(' '+strDelim+strDelim+' ');}).join('')+'\n|}';}return[wikiTable(lstSpiral,false,'text-align:center;width:12em;height:12em;table-layout:fixed;'),JSON.stringify(lstSpiral)].join('\n\n');})(5);
Output:
| 0 | 1 | 2 | 3 | 4 |
| 15 | 16 | 17 | 18 | 5 |
| 14 | 23 | 24 | 19 | 6 |
| 13 | 22 | 21 | 20 | 7 |
| 12 | 11 | 10 | 9 | 8 |
[[0,1,2,3,4],[15,16,17,18,5],[14,23,24,19,6],[13,22,21,20,7],[12,11,10,9,8]]
(()=>{"use strict";// ------------------ SPIRAL MATRIX ------------------// spiral :: Int -> [[Int]]constspiral=n=>{constgo=(rows,cols,start)=>Boolean(rows)?[enumFromTo(start)(start+pred(cols)),...transpose(go(cols,pred(rows),start+cols)).map(reverse)]:[[]];returngo(n,n,0);};// ---------------------- TEST -----------------------// main :: () -> Stringconstmain=()=>{constn=5,cellWidth=1+`${pred(n**2)}`.length;returnunlines(spiral(n).map(row=>(row.map(x=>`${x}`.padStart(cellWidth," "))).join("")));};// --------------------- GENERIC ---------------------// enumFromTo :: Int -> Int -> [Int]constenumFromTo=m=>n=>Array.from({length:1+n-m},(_,i)=>m+i);// pred :: Enum a => a -> aconstpred=x=>x-1;// reverse :: [a] -> [a]constreverse=xs=>"string"===typeofxs?(xs.split("").reverse().join("")):xs.slice(0).reverse();// transpose :: [[a]] -> [[a]]consttranspose=rows=>// The columns of the input transposed// into new rows.// Simpler version of transpose, assuming input// rows of even length.Boolean(rows.length)?rows[0].map((_,i)=>rows.flatMap(v=>v[i])):[];// unlines :: [String] -> Stringconstunlines=xs=>// A single string formed by the intercalation// of a list of strings with the newline character.xs.join("\n");// MAIN ---returnmain();})();
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
The strategy employed here is to start at [0,0] and move to the right ([0,1] == same row, next column) until we reach a boundary or a populated cell; then turn right, and proceed as before.
Initially fill the matrix with "false" so we can easily distinguish between unvisited cells (false) and non-existent cells (null).
Infrastructure:
# Create an m x n matrix def matrix(m; n; init): if m == 0 then [] elif m == 1 then [range(0;n)] | map(init) elif m > 0 then matrix(1;n;init) as $row | [range(0;m)] | map( $row ) else error("matrix\(m);_;_) invalid") end ;# Print a matrix neatly, each cell occupying n spacesdef neatly(n): def right: tostring | ( " " * (n-length) + .); . as $in | length as $length | reduce range (0;$length) as $i (""; . + reduce range(0;$length) as $j (""; "\(.)\($in[$i][$j] | right )" ) + "\n" ) ;def right: if . == [1, 0] then [ 0, -1] elif . == [0, -1] then [-1, 0] elif . == [-1, 0] then [ 0, 1] elif . == [0, 1] then [ 1, 0] else error("invalid direction: \(.)") end;Create a spiral n by n matrix
def spiral(n): # we just placed m at i,j, and we are moving in the direction d def _next(i; j; m; d): if m == (n*n) - 1 then . elif .[i+d[0]][j+d[1]] == false then .[i+d[0]][j+d[1]] = m+1 | _next(i+d[0]; j+d[1]; m+1; d) else (d|right) as $d | .[i+$d[0]][j+$d[1]] = m+1 | _next(i+$d[0]; j+$d[1]; m+1; $d) end; matrix(n;n;false) | .[0][0] = 0 | _next(0;0;0; [0,1]) ;# Examplespiral(5) | neatly(3)
$ jq -n -r -f spiral.jq 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
Define an iterator that marches through matrix indices in the spiral pattern, which makes it easy to generate spiral matrices and related objects. Note that Julia uses column major ordering of matrices and that Julia allows multi-dimensional arrays to be addressed by scalar index as well as by subscripts.
Spiral Matrix Iterator
immutableSpiralm::Intn::Intcmax::Intdir::Array{Array{Int,1},1}bdelta::Array{Array{Int,1},1}endfunctionSpiral(m::Int,n::Int)cmax=m*ndir=Array{Int,1}[[0,1],[1,0],[0,-1],[-1,0]]bdelta=Array{Int,1}[[0,0,0,1],[-1,0,0,0],[0,-1,0,0],[0,0,1,0]]Spiral(m,n,cmax,dir,bdelta)endfunctionspiral(m::Int,n::Int)0<m&&0<n||error("The matrix dimensions must be positive.")Spiral(m,n)endspiral(n::Int)=spiral(n,n)typeSpStatecnt::Intdirdex::Intcell::Array{Int,1}bounds::Array{Int,1}endBase.length(sp::Spiral)=sp.cmaxBase.start(sp::Spiral)=SpState(1,1,[1,1],[sp.n,sp.m,1,1])Base.done(sp::Spiral,sps::SpState)=sps.cnt>sp.cmaxfunctionBase.next(sp::Spiral,sps::SpState)s=sub2ind((sp.m,sp.n),sps.cell[1],sps.cell[2])ifsps.cell[rem1(sps.dirdex+1,2)]==sps.bounds[sps.dirdex]sps.bounds+=sp.bdelta[sps.dirdex]sps.dirdex=rem1(sps.dirdex+1,4)endsps.cell+=sp.dir[sps.dirdex]sps.cnt+=1return(s,sps)end
Helper Functions
usingFormattingfunctionwidth{T<:Integer}(n::T)w=ndigits(n)n<0||returnwreturnw+1endfunctionpretty{T<:Integer}(a::Array{T,2},indent::Int=4)lo,hi=extrema(a)w=max(width(lo),width(hi))id=" "^indentfe=FormatExpr(@sprintf(" {:%dd}",w))s=idnrow=size(a)[1]foriin1:nrowforjina[i,:]s*=format(fe,j)endi!=nrow||continues*="\n"*idendreturnsend
Main
n=5println("The n = ",n," spiral matrix:")a=zeros(Int,(n,n))for(i,s)inenumerate(spiral(n))a[s]=i-1endprintln(pretty(a))m=3println()println("Generalize to a non-square matrix (",m,"x",n,"):")a=zeros(Int,(m,n))for(i,s)inenumerate(spiral(m,n))a[s]=i-1endprintln(pretty(a))p=primes(10^3)n=7println()println("An n = ",n," prime spiral matrix:")a=zeros(Int,(n,n))for(i,s)inenumerate(spiral(n))a[s]=p[i]endprintln(pretty(a))
The n = 5 spiral matrix: 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8Generalize to a non-square matrix (3x5): 0 1 2 3 4 11 12 13 14 5 10 9 8 7 6An n = 7 prime spiral matrix: 2 3 5 7 11 13 17 89 97 101 103 107 109 19 83 173 179 181 191 113 23 79 167 223 227 193 127 29 73 163 211 199 197 131 31 71 157 151 149 139 137 37 67 61 59 53 47 43 41
// version 1.1.3typealiasVector=IntArraytypealiasMatrix=Array<Vector>funspiralMatrix(n:Int):Matrix{valresult=Matrix(n){Vector(n)}varpos=0varcount=nvarvalue=-nvarsum=-1do{value=-value/nfor(iin0untilcount){sum+=valueresult[sum/n][sum%n]=pos++}value*=ncount--for(iin0untilcount){sum+=valueresult[sum/n][sum%n]=pos++}}while(count>0)returnresult}funprintMatrix(m:Matrix){for(iin0untilm.size){for(jin0untilm.size)print("%2d ".format(m[i][j]))println()}println()}funmain(args:Array<String>){printMatrix(spiralMatrix(5))printMatrix(spiralMatrix(10))}
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8 0 1 2 3 4 5 6 7 8 9 35 36 37 38 39 40 41 42 43 10 34 63 64 65 66 67 68 69 44 11 33 62 83 84 85 86 87 70 45 12 32 61 82 95 96 97 88 71 46 13 31 60 81 94 99 98 89 72 47 14 30 59 80 93 92 91 90 73 48 15 29 58 79 78 77 76 75 74 49 16 28 57 56 55 54 53 52 51 50 17 27 26 25 24 23 22 21 20 19 18
Extended to include automatic scaling of the display scale and font. SeespiralM5
nomainwinUpperLeftX = 50UpperLeftY = 50WindowWidth =900WindowHeight =930statictext #w.st, "", 10, 850, 870, 40open "Spiral matrix" for graphics_nsb_nf as #w#w "trapclose [quit]"#w "backcolor darkblue; color cyan; fill darkblue"for N =2 to 50 #w.st "!font courier_new "; int( 60 /N); " bold" #w "down; font arial "; int( 240 /N); " bold" g$ ="ruld" ' direction sequence if N/2 =int( N/2) then pg =2 else pg =0 ' pointer to current direction ' last move is left or right depending on N even/odd d$ ="" for i =1 to N -1 ' calculate direction to move d$ =nChar$( i, mid$( g$, pg +1, 1)) +d$ pg =( pg +1) mod 4 d$ =nChar$( i, mid$( g$, pg +1, 1)) +d$ pg =( pg +1) mod 4 next i d$ =nChar$( N -1, "r") +d$ ' first row #w.st " N ="; N; " "; d$ xp =60 +250 /N yp =80 +250 /N stp =int( 750 /N) for i =0 to N^2 -1 dir$ =mid$( d$, i, 1) select case dir$ case "r" xp =xp +stp case "d" yp =yp +stp case "l" xp =xp -stp case "u" yp =yp -stp end select #w "place "; xp; " "; yp #w "\"; i next i timer 3000, [on] wait [on] timer 0 #w "cls" scannext Nwaitfunction nChar$( n, i$) for i =1 to n nChar$ =nChar$ +i$ next iend function[quit]close #wend
av,sn=math.abs,function(s)returns~=0ands/av(s)or0endfunctionsindex(y,x)-- returns the value at (x, y) in a spiral that starts at 1 and goes outwardsify==-xandy>=xthenreturn(2*y+1)^2endlocall=math.max(av(y),av(x))return(2*l-1)^2+4*l+2*l*sn(x+y)+sn(y^2-x^2)*(l-(av(y)==landsn(y)*xorsn(x)*y))-- OH GOD WHATendfunctionspiralt(side)localret,start,stop={},math.floor((-side+1)/2),math.floor((side-1)/2)fori=1,sidedoret[i]={}forj=1,sidedoret[i][j]=side^2-sindex(stop-i+1,start+j-1)--moves the coordinates so (0,0) is at the center of the spiralendendreturnretendfori,vinipairs(spiralt(8))doforj,uinipairs(v)doio.write(u.." ")endprint()end
If only the printed output is required, without intermediate array storage, then:
localfunctionprintspiral(n)localfunctionz(x,y)localm=math.min(x,y,n-1-x,n-1-y)returnx<yand(n-2*m-2)^2+(x-m)+(y-m)or(n-2*m)^2-(x-m)-(y-m)endfory=1,ndoforx=1,ndoio.write(string.format("%2d ",n^2-z(x-1,y-1)))endprint()endendprintspiral(9)
If the intermediate array storageis required, then:
localfunctionmakespiral(n)localt,z={},function(x,y)localm=math.min(x,y,n-1-x,n-1-y)returnx<yand(n-2*m-2)^2+(x-m)+(y-m)or(n-2*m)^2-(x-m)-(y-m)endfory=1,ndot[y]={}forx=1,ndot[y][x]=n^2-z(x-1,y-1)endendreturntendlocalfunctionprintspiral(t)fory=1,#tdoforx=1,#t[y]doio.write(string.format("%2d ",t[y][x]))endprint()endendprintspiral(makespiral(9))
(same for both)
0 1 2 3 4 5 6 7 831 32 33 34 35 36 37 38 930 55 56 57 58 59 60 39 1029 54 71 72 73 74 61 40 1128 53 70 79 80 75 62 41 1227 52 69 78 77 76 63 42 1326 51 68 67 66 65 64 43 1425 50 49 48 47 46 45 44 1524 23 22 21 20 19 18 17 16
with(ArrayTools):spiralArray := proc(size::integer) local M, sideLength, count, i, j: M := Matrix(size): count := 0: sideLength := size: for i from 1 to ceil(sideLength / 2) do for j from 1 to sideLength do M[i,i + j - 1] := count++: end: for j from 1 to sideLength - 1 do M[i + j, sideLength + i - 1] := count++: end: for j from 1 to sideLength - 1 do M[i + sideLength - 1, sideLength - j + i - 1] := count++: end: for j from 1 to sideLength - 2 do M[sideLength + i - j - 1, i] := count++ end: sideLength -= 2: end: return M;end proc:spiralArray(5);
[ 0 1 2 3 4] [ ] [15 16 17 18 5] [ ] [14 23 24 19 6] [ ] [13 22 21 20 7] [ ] [12 11 10 9 8]
We split the task up in 2 functions, one that adds a 'ring' around a present matrix. And a function that adds rings to a 'core':
AddSquareRing[x_List/;Equal@@Dimensions[x]&&Length[Dimensions[x]]==2]:=Module[{new=x,size,smallest},size=Length[x];smallest=x[[1,1]];Do[new[[i]]=Prepend[new[[i]],smallest-i];new[[i]]=Append[new[[i]],smallest-3size+i-3],{i,size}];PrependTo[new,Range[smallest-3size-3-size-1,smallest-3size-3]];AppendTo[new,Range[smallest-size-1,smallest-size-size-2,-1]];new]MakeSquareSpiral[size_Integer/;size>0]:=Module[{largest,start,times},start=size^2+If[Mod[size,2]==0,{{-4,-3},{-1,-2}},{{-1}}];times=If[Mod[size,2]==0,size/2-1,(size-1)/2];Nest[AddSquareRing,start,times]]
Examples:
MakeSquareSpiral[2]//MatrixFormMakeSquareSpiral[7]//MatrixForm
gives back:
There already exists a command to generate a spiral matrix in MATLAB. But, it creates a matrix that spirals outward, not inward like the task specification requires. It turns out that these matrices can be transformed into each other using some pretty simple transformations.
We start with a simple linear transformation:Then depending on if n is odd or even we use either an up/down or left/right mirror transformation.
functionmatrix=reverseSpiral(n)matrix=(-spiral(n))+n^2;ifmod(n,2)==0matrix=flipud(matrix);elsematrix=fliplr(matrix);endend%reverseSpiral
Sample Usage:
>>reverseSpiral(5)ans=0123415161718514232419613222120712111098
spiral(n):=block([a,i,j,k,p,di,dj,vi,vj,imin,imax,jmin,jmax],a:zeromatrix(n,n),vi:[1,0,-1,0],vj:[0,1,0,-1],imin:0,imax:n,jmin:1,jmax:n+1,p:1,di:vi[p],dj:vj[p],i:1,j:1,forkfrom1thrun*ndo(a[j,i]:k,i:i+di,j:j+dj,ifi<iminori>imaxorj<jminorj>jmaxthen(i:i-di,j:j-dj,p:mod(p,4)+1,di:vi[p],dj:vj[p],i:i+di,j:j+dj,ifp=1thenimax:imax-1elseifp=2thenjmax:jmax-1elseifp=3thenimin:imin+1elsejmin:jmin+1)),a)$spiral(5);/* matrix([ 1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]) */
%Spiral Matrix. Nigel Galloway, February 3rd., 2020int: Size;array [1..Size,1..Size] of var 1..Size*Size: spiral;constraint spiral[1,1..]=1..Size;constraint forall(n in 2..(Size+1) div 2)(forall(g in n..Size+1-n)(spiral[n,g]=spiral[n,g-1]+1));constraint forall(n in 1..(Size+1) div 2)(forall(g in n+1..Size+1-n)(spiral[g,Size-n+1]=spiral[g-1,Size-n+1]+1));constraint forall(n in 1..Size div 2)(forall(g in n..Size-n)(spiral[Size-n+1,g]=spiral[Size-n+1,g+1]+1)) /\ forall(n in 1..Size div 2)(forall(g in n+1..Size-n)(spiral[g,n]=spiral[g+1,n]+1));output [show2d(spiral)];
minizinc -DSize= spiral.mzn[| 1, 2, 3, 4 | 12, 13, 14, 5 | 11, 16, 15, 6 | 10, 9, 8, 7 |]----------minizinc -DSize=5 zigzag.mzn[| 1, 2, 3, 4, 5 | 16, 17, 18, 19, 6 | 15, 24, 25, 20, 7 | 14, 23, 22, 21, 8 | 13, 12, 11, 10, 9 |]----------minizinc -DSize=6 zigzag.mzn[| 1, 2, 3, 4, 5, 6 | 20, 21, 22, 23, 24, 7 | 19, 32, 33, 34, 25, 8 | 18, 31, 36, 35, 26, 9 | 17, 30, 29, 28, 27, 10 | 16, 15, 14, 13, 12, 11 |]----------
/* NetRexx */optionsreplaceformatcommentsjavacrossrefsymbolsbinaryparseargsize.if\size.datatype('W')thendoprintArray(generateArray(3))sayprintArray(generateArray(4))sayprintArray(generateArray(5))sayendelsedoprintArray(generateArray(size))sayendreturn-------------------------------------------------------------------------------methodgenerateArray(dimension=int)privatestaticreturnsint[,]--theoutputarrayarray=int[dimension,dimension]--getthenumberofsquares,includingthecenteroneif--thedimensionisoddsquares=dimension%2+dimension//2--lengthofasideforthecurrentsquaresidelength=dimensioncurrent=0loopi_=0tosquares-1--doeachsideofthecurrentsquare--topsideloopj_=0tosidelength-1array[i_,i_+j_]=currentcurrent=current+1endj_--downtherightsideloopj_=1tosidelength-1array[i_+j_,dimension-1-i_]=currentcurrent=current+1endj_--acrossthebottomloopj_=sidelength-2to0by-1array[dimension-1-i_,i_+j_]=currentcurrent=current+1endj_--anduptheleftsideloopj_=sidelength-2to1by-1array[i_+j_,i_]=currentcurrent=current+1endj_--reducethelengthofthesidebytworowssidelength=sidelength-2endi_returnarray-------------------------------------------------------------------------------methodprintArray(array=int[,])privatestaticdimension=array[1].lengthrl=formatSize(array)loopi_=0todimension-1line=Rexx("|")loopj_=0todimension-1line=lineRexx(array[i_,j_]).right(rl)endj_line=line"|"saylineendi_return-------------------------------------------------------------------------------methodformatSize(array=int[,])privatestaticreturnsRexxdim=array[1].lengthmaxNum=Rexx(dim*dim-1).length()returnmaxNum
| 0 1 2 || 7 8 3 || 6 5 4 || 0 1 2 3 || 11 12 13 4 || 10 15 14 5 || 9 8 7 6 || 0 1 2 3 4 || 15 16 17 18 5 || 14 23 24 19 6 || 13 22 21 20 7 || 12 11 10 9 8 |
importsequtils,strutilsproc`$`(m:seq[seq[int]]):string=forrinm:letlg=result.lenforcinr:result.addSep(" ",lg)result.addalign($c,2)result.add'\n'procspiral(n:Positive):seq[seq[int]]=result=newSeqWith(n,repeat(-1,n))vardx=1vardy,x,y=0foriin0..<(n*n):result[y][x]=ilet(nx,ny)=(x+dx,y+dy)ifnxin0..<nandnyin0..<nandresult[ny][nx]==-1:x=nxy=nyelse:swapdx,dydx=-dxx+=dxy+=dyechospiral(5)
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
letnext_dir=function|1,0->0,-1|0,1->1,0|-1,0->0,1|0,-1->-1,0|_->assertfalseletnext_pos~pos:(x,y)~dir:(nx,ny)=(x+nx,y+ny)letnext_cellar~pos:(x,y)~dir:(nx,ny)=tryar.(x+nx).(y+ny)with_->-2letfor_loopninitfn=letrecauxiv=ifi<nthenaux(i+1)(fniv)inaux0initletspiral~n=letar=Array.make_matrixnn(-1)inletpos=0,0inletdir=0,1inletset(x,y)i=ar.(x).(y)<-iinletstep(pos,dir)=matchnext_cellarposdirwith|-1->(next_posposdir,dir)|_->letdir=next_dirdirin(next_posposdir,dir)infor_loop(n*n)(pos,dir)(funi(pos,dir)->setposi;step(pos,dir));(ar)letprint=Array.iter(funline->Array.iter(Printf.printf" %2d")line;print_newline())let()=print(spiral5)
Another implementation:
letspiraln=letar=Array.make_matrixnn(-1)inletouti=i<0||i>=ninlettoo_far(x,y)=outx||outy||ar.(x).(y)>=0inletstepxy(dx,dy)=(x+dx,y+dy)inletturn(i,j)=(j,-i)inletreciter(x,y)di=ar.(x).(y)<-i;ifi<n*n-1thenletd'=iftoo_far(stepxyd)thenturndelsediniter(stepxyd')d'(i+1)in(iter(0,0)(0,1)0;ar)letshow=Array.iter(funv->Array.iter(Printf.printf" %2d")v;print_newline())let_=show(spiral5)
functiona=spiral(n)a=ones(n*n,1);u=-(i=n)*(v=ones(n,1));fork=n-1:-1:1j=1:k;a(j+i)=u(j)=-u(j);a(j+(i+k))=v(j)=-v(j);i+=2*k;endfora(cumsum(a))=1:n*n;a=reshape(a,n,n)'-1;endfunction>>spiral(5)ans=0123415161718514232419613222120712111098
callprintArraygenerateArray(3)saycallprintArraygenerateArray(4)saycallprintArraygenerateArray(5)::routinegenerateArrayuseargdimension--theoutputarrayarray=.array~new(dimension,dimension)--getthenumberofsquares,includingthecenteroneif--thedimensionisoddsquares=dimension%2+dimension//2--lengthofasideforthecurrentsquaresidelength=dimensioncurrent=0loopi=1tosquares--doeachsideofthecurrentsquare--topsideloopj=0tosidelength-1array[i,i+j]=currentcurrent+=1end--downtherightsideloopj=1tosidelength-1array[i+j,dimension-i+1]=currentcurrent+=1end--acrossthebottomloopj=sidelength-2to0by-1array[dimension-i+1,i+j]=currentcurrent+=1end--anduptheleftsideloopj=sidelength-2to1by-1array[i+j,i]=currentcurrent+=1end--reducethelengthofthesidebytworowssidelength-=2endreturnarray::routineprintArrayuseargarraydimension=array~dimension(1)loopi=1todimensionline="|"loopj=1todimensionline=linearray[i,j]~right(2)endline=line"|"saylineend
| 0 1 2 || 7 8 3 || 6 5 4 || 0 1 2 3 || 11 12 13 4 || 10 15 14 5 || 9 8 7 6 || 0 1 2 3 4 || 15 16 17 18 5 || 14 23 24 19 6 || 13 22 21 20 7 || 12 11 10 9 8 |
Simple, recursive solution:
declare fun {Spiral N} %% create nested array Arr = {Array.new 1 N unit} for Y in 1..N do Arr.Y := {Array.new 1 N 0} end %% fill it recursively with increasing numbers C = {Counter 0} in {Fill Arr 1 N C} Arr end proc {Fill Arr S E C} %% go right for X in S..E do Arr.S.X := {C} end %% go down for Y in S+1..E do Arr.Y.E := {C} end %% go left for X in E-1..S;~1 do Arr.E.X := {C} end %% go up for Y in E-1..S+1;~1 do Arr.Y.S := {C} end %% fill the inner rectangle if E - S > 1 then {Fill Arr S+1 E-1 C} end end fun {Counter N} C = {NewCell N} in fun {$} C := @C + 1 end endin {Inspect {Spiral 5}}spiral(dim) = { my (M = matrix(dim, dim), p = s = 1, q = i = 0); for (n=1, dim, for (b=1, dim-n+1, M[p,q+=s] = i; i++); for (b=1, dim-n, M[p+=s,q] = i; i++); s = -s; ); M}Output:
spiral(7)[ 0 1 2 3 4 5 6][23 24 25 26 27 28 7][22 39 40 41 42 29 8][21 38 47 48 43 30 9][20 37 46 45 44 31 10][19 36 35 34 33 32 11][18 17 16 15 14 13 12]
programSpiralmat;typetDir=(left,down,right,up);tdxy=recorddx,dy:longint;end;tdeltaDir=array[tDir]oftdxy;constNextdir:array[tDir]oftDir=(down,right,up,left);cDir:tDeltaDir=((dx:1;dy:0),(dx:0;dy:1),(dx:-1;dy:0),(dx:0;dy:-1));cMaxN=32;typetSpiral=array[0..cMaxN,0..cMaxN]ofLongInt;functionFillSpiral(n:longint):tSpiral;varb,i,k,dn,x,y:longInt;dir:tDir;tmpSp:tSpiral;BEGINb:=0;x:=0;y:=0;//only for the first linek:=-1;dn:=n-1;tmpSp[x,y]:=b;dir:=left;repeati:=0;whilei<dndobegininc(b);tmpSp[x,y]:=b;inc(x,cDir[dir].dx);inc(y,cDir[dir].dy);inc(i);end;Dir:=NextDir[dir];inc(k);IFk>1thenbegink:=0;//shorten the line every second direction changedn:=dn-1;ifdn<=0thenBREAK;end;untilfalse;//the lasttmpSp[x,y]:=b+1;FillSpiral:=tmpSp;end;vara:tSpiral;x,y,n:LongInt;BEGINForn:=1to5{cMaxN}dobeginA:=FillSpiral(n);Fory:=0ton-1dobeginForx:=0ton-1dowrite(A[x,y]:4);writeln;end;writeln;end;END.
1 1 2 4 3.... 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
subspiral{my($n,$x,$y,$dx,$dy,@a)=(shift,0,0,1,0);foreach(0..$n**2-1){$a[$y][$x]=$_;my($nx,$ny)=($x+$dx,$y+$dy);($dx,$dy)=$dx==1&&($nx==$n||defined$a[$ny][$nx])?(0,1):$dy==1&&($ny==$n||defined$a[$ny][$nx])?(-1,0):$dx==-1&&($nx<0||defined$a[$ny][$nx])?(0,-1):$dy==-1&&($ny<0||defined$a[$ny][$nx])?(1,0):($dx,$dy);($x,$y)=($x+$dx,$y+$dy);}return@a;}foreach(spiral5){printf"%3d",$_foreach@$_;print"\n";}
Simple is better.
withjavascript_semanticsintegern=6,x=1,y=0,counter=0,len=n,dx=0,dy=1stringfmt=sprintf("%%%dd",length(sprintf("%d",n*n)))sequencem=repeat(repeat("??",n),n)fori=1to2*ndo-- 2n runs..forj=1tolendo-- of a length...x+=dxy+=dym[x][y]=sprintf(fmt,counter)counter+=1endforlen-=odd(i)-- ..-1 every other{dx,dy}={dy,-dx}-- in new directionendforprintf(1,"%s\n",{join(apply(m,join),"\n")})
0 1 2 3 4 519 20 21 22 23 618 31 32 33 24 717 30 35 34 25 816 29 28 27 26 915 14 13 12 11 10
This example uses 'grid' from "lib/simul.l", which maintains a two-dimensional structure and is normally used for simulations and board games.
(load "@lib/simul.l")(de spiral (N) (prog1 (grid N N) (let (Dir '(north east south west .) This 'a1) (for Val (* N N) (=: val Val) (setq This (or (with ((car Dir) This) (unless (: val) This) ) (with ((car (setq Dir (cdr Dir))) This) (unless (: val) This) ) ) ) ) ) ) )(mapc '((L) (for This L (prin (align 3 (: val)))) (prinl) ) (spiral 5) )
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
/* Generates a square matrix containing the integers from 0 to N**2-1, *//* where N is the length of one side of the square. *//* Written 22 February 2010. */ declare n fixed binary;put skip list ('Please type the size of the square:');get list (n);begin; declare A(n,n) fixed binary; declare (i, j, iinc, jinc, q) fixed binary; A = -1; i, j = 1; iinc = 0; jinc = 1; do q = 0 to n**2-1; if a(i,j) < 0 then a(i,j) = q; else do; /* back up */ j = j -jinc; i = i - iinc; /* change direction */ if iinc = 0 & jinc = 1 then do; iinc = 1; jinc = 0; end; else if iinc = 1 & jinc = 0 then do; iinc = 0; jinc = -1; end; else if iinc = 0 & jinc = -1 then do; iinc = -1; jinc = 0; end; else if iinc = -1 & jinc = 0 then do; iinc = 0; jinc = 1; end; /* Take one step in the new direction */ i = i + iinc; j = j + jinc; a(i,j) = q; end; if i+iinc > n | i+iinc < 1 then do; iinc = 0; jinc = 1; if j+1 > n then jinc = -1; else if j-1 < 1 then jinc = 1; if a(i+iinc,j+jinc) >= 0 then jinc = -jinc; /* j = j + jinc; /* to move on from the present (filled) position */ end; else i = i + iinc; if j+jinc > n | j+jinc < 1 then do; jinc = 0; iinc = 1; if i+1 > n then iinc = -1; else if i-1 < 1 then iinc = 1; if a(i+iinc,j+jinc) >= 0 then iinc = -iinc; i = i + iinc; /* to move on from the present (filled) position */ end; else j = j + jinc; end; /* Display the square. */ do i = 1 to n; put skip edit (A(i,*)) (F(4)); end;end;functionSpiral-Matrix([int]$N){# Initialize variables$X=0$Y=-1$i=0$Sign=1# Intialize array$A=New-Object'int[,]'$N,$N# Set top row1..$N|ForEach{$Y+=$Sign;$A[$X,$Y]=++$i}# For each remaining half spiral...ForEach($Min($N-1)..1){# Set the vertical quarter spiral1..$M|ForEach{$X+=$Sign;$A[$X,$Y]=++$i}# Curve the spiral$Sign=-$Sign# Set the horizontal quarter spiral1..$M|ForEach{$Y+=$Sign;$A[$X,$Y]=++$i}}# Convert the array to text output$Spiral=ForEach($Xin1..$N){(1..$N|ForEach{$A[($X-1),($_-1)]})-join"`t"}return$Spiral}Spiral-Matrix5""Spiral-Matrix7
1234516171819615242520714232221813121110912345672425262728298234041424330922394849443110213847464532112037363534331219181716151413
% Prolog implementation: SWI-Prolog 7.2.3replace([_|T],0,E,[E|T]):-!.replace([H|T],N,E,Xs):-succ(N1,N),replace(T,N1,E,Xs1),Xs=[H|Xs1].% True if Xs is the Original grid with the element at (X, Y) replaces by E.replace_in([H|T],(0,Y),E,Xs):-replace(H,Y,E,NH),Xs=[NH|T],!.replace_in([H|T],(X,Y),E,Xs):-succ(X1,X),replace_in(T,(X1,Y),E,Xs1),Xs=[H|Xs1].% True, if E is the value at (X, Y) in Xsget_in(Xs,(X,Y),E):-nth0(X,Xs,L),nth0(Y,L,E).create(N,Mx):-% NxN grid full of nilsnumlist(1,N,Ns),findall(X,(member(_,Ns),X=nil),Ls),findall(X,(member(_,Ns),X=Ls),Mx).% Depending of the direction, returns two possible coordinates and directions% (C,D) that will be used in case of a turn, and (A,B) otherwise.ops(right,(X,Y),(A,B),(C,D),D1,D2):-AisX,BisY+1,D1=right,CisX+1,DisY,D2=down.ops(left,(X,Y),(A,B),(C,D),D1,D2):-AisX,BisY-1,D1=left,CisX-1,DisY,D2=up.ops(up,(X,Y),(A,B),(C,D),D1,D2):-AisX-1,BisY,D1=up,CisX,DisY+1,D2=right.ops(down,(X,Y),(A,B),(C,D),D1,D2):-AisX+1,BisY,D1=down,CisX,DisY-1,D2=left.% True if NCoor is the right coor in spiral shape. Returns a new direction also.next(Dir,Mx,Coor,NCoor,NDir):-ops(Dir,Coor,C1,C2,D1,D2),(get_in(Mx,C1,nil)->NCoor=C1,NDir=D1;NCoor=C2,NDir=D2).% Returns an spiral with [H|Vs] elements called R, only work if the length of% [H|Vs], is the square of the size of the grid.spiralH(Dir,Mx,Coor,[H|Vs],R):-replace_in(Mx,Coor,H,NMx),(Vs=[]->R=NMx;next(Dir,Mx,Coor,NCoor,NDir),spiralH(NDir,NMx,NCoor,Vs,R)).% True if Mx is the grid in spiral shape of the numbers from 0 to N*N-1.spiral(N,Mx):-SqisN*N-1,numlist(0,Sq,Ns),create(N,EMx),spiralH(right,EMx,(0,0),Ns,Mx).
?- spiral(6,Mx), forall(member(X,Mx), writeln(X)).[0,1,2,3,4,5][19,20,21,22,23,6][18,31,32,33,24,7][17,30,35,34,25,8][16,29,28,27,26,9][15,14,13,12,11,10]
ProcedurespiralMatrix(size=1)Protectedi,x=-1,y,count=size,nDima(size-1,size-1)Fori=1Tocountx+1a(x,y)=nn+1NextRepeatcount-1Fori=1Tocounty+1a(x,y)=nn+1NextFori=1Tocountx-1a(x,y)=nn+1Nextcount-1Fori=1Tocounty-1a(x,y)=nn+1NextFori=1Tocountx+1a(x,y)=nn+1NextUntilcount<1PrintN("Spiral: "+Str(Size)+#CRLF$)ProtectedcolWidth=Len(Str(size*size-1))+1Fory=0Tosize-1Forx=0Tosize-1Print(""+LSet(Str(a(x,y)),colWidth," ")+"")NextPrintN("")NextPrintN("")EndProcedureIfOpenConsole()spiralMatrix(2)PrintN("")spiralMatrix(5)Print(#CRLF$+#CRLF$+"Press ENTER to exit")Input()CloseConsole()EndIf
Spiral: 20 13 2Spiral: 50 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
defspiral(n):dx,dy=1,0# Starting incrementsx,y=0,0# Starting locationmyarray=[[None]*nforjinrange(n)]foriinxrange(n**2):myarray[x][y]=inx,ny=x+dx,y+dyif0<=nx<nand0<=ny<nandmyarray[nx][ny]==None:x,y=nx,nyelse:dx,dy=-dy,dxx,y=x+dx,y+dyreturnmyarraydefprintspiral(myarray):n=range(len(myarray))foryinn:forxinn:print"%2i"%myarray[x][y],printprintspiral(spiral(5))
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
defspiral(n):defspiral_part(x,y,n):ifx==-1andy==0:return-1ify==(x+1)andx<(n//2):returnspiral_part(x-1,y-1,n-1)+4*(n-y)ifx<(n-y)andy<=x:returnspiral_part(y-1,y,n)+(x-y)+1ifx>=(n-y)andy<=x:returnspiral_part(x,y-1,n)+1ifx>=(n-y)andy>x:returnspiral_part(x+1,y,n)+1ifx<(n-y)andy>x:returnspiral_part(x,y-1,n)-1array=[[0]*nforjinxrange(n)]forxinxrange(n):foryinxrange(n):array[x][y]=spiral_part(y,x,n)returnarrayforrowinspiral(5):print" ".join("%2s"%xforxinrow)
Adding a cache for thespiral_part function it could be quite efficient.
Recursion by rotating the solution for rest of the square except the first row,
defrot_right(a):returnzip(*a[::-1])defsp(m,n,start=0):""" Generate number range spiral of dimensions m x n """ifn==0:yield()else:yieldtuple(range(start,m+start))forrowinrot_right(list(sp(n-1,m,m+start))):yieldrowdefspiral(m):returnsp(m,m)forrowinspiral(5):print(''.join('%3i'%iforiinrow))
Another way, based on preparing lists ahead
defspiral(n):dat=[[None]*nforiinrange(n)]le=[[i+1,i+1]foriinreversed(range(n))]le=sum(le,[])[1:]# for n = 5 le will be [5, 4, 4, 3, 3, 2, 2, 1, 1]dxdy=[[1,0],[0,1],[-1,0],[0,-1]]*((len(le)+4)/4)# long enoughx,y,val=-1,0,-1forsteps,(dx,dy)inzip(le,dxdy):x,y,val=x+dx,y+dy,val+1forjinrange(steps):dat[y][x]=valifj!=steps-1:x,y,val=x+dx,y+dy,val+1returndatforrowinspiral(5):# calc spiral and print itprint' '.join('%3s'%xforxinrow)
importitertoolsconcat=itertools.chain.from_iterabledefpartial_sums(items):s=0forxinitems:s+=xyieldsgrade=lambdaxs:sorted(range(len(xs)),key=xs.__getitem__)values=lambdan:itertools.cycle([1,n,-1,-n])counts=lambdan:concat([i,i-1]foriinrange(n,0,-1))reshape=lambdan,xs:zip(*([iter(xs)]*n))spiral=lambdan:reshape(n,grade(list(partial_sums(concat([v]*cforc,vinzip(counts(n),values(n)))))))forrowinspiral(5):print(' '.join('%3s'%xforxinrow))
Or, as an alternative to generative mutation:
'''Spiral Matrix'''# spiral :: Int -> [[Int]]defspiral(n):'''The rows of a spiral matrix of order N. '''defgo(rows,cols,x):return[range(x,x+cols)]+[reversed(x)forxinzip(*go(cols,rows-1,x+cols))]if0<rowselse[[]]returngo(n,n,0)# ------------------------- TEST -------------------------# main :: IO ()defmain():'''Spiral matrix of order 5, in wiki table markup. '''print(wikiTable(spiral(5)))# ---------------------- FORMATTING ----------------------# wikiTable :: [[a]] -> StringdefwikiTable(rows):'''Wiki markup for a no-frills tabulation of rows.'''return'{| class="wikitable" style="'+('width:12em;height:12em;table-layout:fixed;"|-\n')+'\n|-\n'.join('| '+' || '.join(str(cell)forcellinrow)forrowinrows)+'\n|}'# MAIN ---if__name__=='__main__':main()
| 0 | 1 | 2 | 3 | 4 |
| 15 | 16 | 17 | 18 | 5 |
| 14 | 23 | 24 | 19 | 6 |
| 13 | 22 | 21 | 20 | 7 |
| 12 | 11 | 10 | 9 | 8 |
defspiral_matrix(n):m=[[0]*nforiinrange(n)]dx,dy=[0,1,0,-1],[1,0,-1,0]x,y,c=0,-1,1foriinrange(n+n-1):forjinrange((n+n-i)//2):x+=dx[i%4]y+=dy[i%4]m[x][y]=cc+=1returnmforiinspiral_matrix(5):print(*i)
1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9
This task really lends itself to a turtle graphics metaphor.
[ stack ] is stepcount ( --> s ) [ stack ] is position ( --> s ) [ stack ] is heading ( --> s ) [ heading take behead join heading put ] is right ( --> ) [ heading share 0 peek unrot times [ position share stepcount share unrot poke over position tally 1 stepcount tally ] nip ] is walk ( [ n --> [ ) [ dip [ temp put [] ] temp share times [ temp share split dip [ nested join ] ] drop temp release ] is matrixify ( n [ --> [ ) [ 0 stepcount put ( set up... ) 0 position put ' [ 1 ] over join -1 join over negate join heading put 0 over dup * of over 1 - walk right ( turtle draws spiral ) over 1 - times [ i 1+ walk right i 1+ walk right ] 1 walk matrixify ( ...tidy up ) heading release position release stepcount release ] is spiral ( n --> [ ) 9 spiral witheach [ witheach [ dup 10 < if sp echo sp ] cr ]
0 1 2 3 4 5 6 7 8 31 32 33 34 35 36 37 38 9 30 55 56 57 58 59 60 39 10 29 54 71 72 73 74 61 40 11 28 53 70 79 80 75 62 41 12 27 52 69 78 77 76 63 42 13 26 51 68 67 66 65 64 43 14 25 50 49 48 47 46 45 44 15 24 23 22 21 20 19 18 17 16
spiral<-function(n)matrix(order(cumsum(rep(rep_len(c(1,n,-1,-n),2*n-1),n-seq(2*n-1)%/%2))),n,byrow=T)-1spiral(5)
[,1] [,2] [,3] [,4] [,5][1,] 0 1 2 3 4[2,] 15 16 17 18 5[3,] 14 23 24 19 6[4,] 13 22 21 20 7[5,] 12 11 10 9 8
spiral_matrix<-function(n){spiralv<-function(v){n<-sqrt(length(v))if(n!=floor(n))stop("length of v should be a square of an integer")if(n==0)stop("v should be of positive length")if(n==1)m<-matrix(v,1,1)elsem<-rbind(v[1:n],cbind(spiralv(v[(2*n):(n^2)])[(n-1):1,(n-1):1],v[(n+1):(2*n-1)]))m}spiralv(1:(n^2))}
Not the most elegant, but certainly distinct from the other R solutions. The key is the observation that we need to produce n elements from left to right, then n-1 elements down, then n-1 left, then n-2 right, then n-2 down, ... . This gives us two patterns. One in the direction that we need to write and another in the number of elements to write. After this, all that is left is battling R's indexing system.
spiralMatrix<-function(n){spiral<-matrix(0,nrow=n,ncol=n)firstNumToWrite<-0neededLength<-nstartPt<-cbind(1,0)#(1, 0) is needed for the first call to writeRight to work. We need to start in row 1.writingDirectionIndex<-0#These two functions select a collection of adjacent elements and replaces them with the needed sequence.#This heavily uses R's vector recycling rules.writeDown<-function(seq)spiral[startPt[1]+seq,startPt[2]]<<-seq_len(neededLength)-1+firstNumToWritewriteRight<-function(seq)spiral[startPt[1],startPt[2]+seq]<<-seq_len(neededLength)-1+firstNumToWritewhile(firstNumToWrite!=n^2){writingDirectionIndex<-writingDirectionIndex%%4+1seq<-seq_len(neededLength)switch(writingDirectionIndex,writeRight(seq),writeDown(seq),writeRight(-seq),writeDown(-seq))if(writingDirectionIndex%%2)neededLength<-neededLength-1max<-max(spiral)firstNumToWrite<-max+1startPt<-which(max==spiral,arr.ind=TRUE)}spiral}
#langracket(requiremath)(define(spiralrowscolumns)(define(indexxy)(+(*xcolumns)y))(do((N(*rowscolumns))(spiral(make-vector(*rowscolumns)#f))(dx1)(dy0)(x0)(y0)(i0(+i1)))((=iN)spiral)(vector-set!spiral(indexyx)i)(let((nx(+xdx))(ny(+ydy)))(cond((and(<-1nxcolumns)(<-1nyrows)(not(vector-refspiral(indexnynx))))(set!xnx)(set!yny))(else(set!-values(dxdy)(values(-dy)dx))(set!x(+xdx))(set!y(+ydy)))))))(vector->matrix44(spiral44))
(mutable-array#[#[0123]#[1112134]#[1015145]#[9876]])
(formerly Perl 6)
Suppose we set up a Turtle class like this:
classTurtle {my@dv = [0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1];my$points =8;# 'compass' points of neighbors on grid: north=0, northeast=1, east=2, etc.has@.loc =0,0;has$.dir =0;has%.world;has$.maxegg;has$.range-x;has$.range-y;methodturn-left ($angle =90) {$!dir -=$angle /45;$!dir %=$points; }methodturn-right($angle =90) {$!dir +=$angle /45;$!dir %=$points; }methodlay-egg($egg) {%!world{~@!loc} =$egg;$!maxeggmax=$egg;$!range-xminmax=@!loc[0];$!range-yminmax=@!loc[1]; }methodlook($ahead =1) {my$there =@!loc »+« @dv[$!dir] »*»$ahead;%!world{~$there}; }methodforward($ahead =1) {my$there =@!loc »+« @dv[$!dir] »*»$ahead;@!loc = @($there); }methodshowmap() {my$form ="%{$!maxegg.chars}s";my$endx =$!range-x.max;for$!range-y.listX$!range-x.list -> ($y,$x) {print (%!world{"$x $y"} //'').fmt($form);print$x ==$endx ??"\n" !!' '; } }}# Now we can build the spiral in the normal way from outside-in like this:subMAIN(Int$size =5) {my$t =Turtle.new(dir =>2);my$counter =0;$t.forward(-1);for0..^$size -> $ {$t.forward;$t.lay-egg($counter++);}for$size-1 ...1 ->$run {$t.turn-right;$t.forward,$t.lay-egg($counter++)for0..^$run;$t.turn-right;$t.forward,$t.lay-egg($counter++)for0..^$run;}$t.showmap;}
Or we can build the spiral from inside-out like this:
subMAIN(Int$size =5) {my$t =Turtle.new(dir => ($size %%2 ??4 !!0));my$counter =$size *$size;while$counter {$t.lay-egg(--$counter);$t.turn-left;$t.turn-rightif$t.look;$t.forward;}$t.showmap;}
Note that with these "turtle graphics" we don't actually have to care about the coordinate system, since theshowmap method can show whatever rectangle was modified by the turtle. So unlike the standard inside-out algorithm, we don't have to find the center of the matrix first.
subspiral_matrix ($n ) {my@sm;my$len =$n;my$pos =0;for ^($n/2).ceiling ->$i {my$j =$i +1;my$e =$n -$j;@sm[$i ][$i +$_] =$pos++for ^($len);# Top@sm[$j +$_][$e ] =$pos++for ^(--$len);# Right@sm[$e ][$i +$_] =$pos++forreverse ^($len);# Bottom@sm[$j +$_][$i ] =$pos++forreverse ^(--$len);# Left }return@sm;}say .fmt('%3d')forspiral_matrix(5);
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
Original logic borrowed (mostly) from theFortran example.
/*REXX program displays a spiral in a square array (of any size) starting at START. */parseargsizestart./*obtain optional arguments from the CL*/ifsize==''|size==","thensize=5/*Not specified? Then use the default.*/ifstart==''|start==","thenstart=0/*Not specified? Then use the default.*/tot=size**2;L=length(tot+start)/*total number of elements in spiral. */k=size/*K: is the counter for the spiral. */row=1;col=0/*start spiral at row 1, column 0. *//* [↓] construct the numbered spiral. */don=0fork;col=col+1;@.col.row=n+start;end;ifk==0thenexit/* [↑] build the first row of spiral. */dountiln>=tot/*spiral matrix.*/doone=1to-1by-2untiln>=tot;k=k-1/*perform twice.*/don=nfork;row=row+one;@.col.row=n+start;end/*for the row···*/don=nfork;col=col-one;@.col.row=n+start;end/* " " col···*/end/*one*//* ↑↓ direction.*/end/*until n≥tot*//* [↑] done with the matrix spiral. *//* [↓] display spiral to the screen. */dor=1forsize;_=right(@.1.r,L)/*construct display row by row. */doc=2forsize-1;_=_right(@.c.r,L)/*construct a line for the display. */end/*col*//* [↑] line has an extra leading blank*/say_/*display a line (row) of the spiral. */end/*row*//*stick a fork in it, we're all done. */
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
-70000 -69999 -69998 -69997 -69996 -69995 -69994 -69993 -69992 -69991-69965 -69964 -69963 -69962 -69961 -69960 -69959 -69958 -69957 -69990-69966 -69937 -69936 -69935 -69934 -69933 -69932 -69931 -69956 -69989-69967 -69938 -69917 -69916 -69915 -69914 -69913 -69930 -69955 -69988-69968 -69939 -69918 -69905 -69904 -69903 -69912 -69929 -69954 -69987-69969 -69940 -69919 -69906 -69901 -69902 -69911 -69928 -69953 -69986-69970 -69941 -69920 -69907 -69908 -69909 -69910 -69927 -69952 -69985-69971 -69942 -69921 -69922 -69923 -69924 -69925 -69926 -69951 -69984-69972 -69943 -69944 -69945 -69946 -69947 -69948 -69949 -69950 -69983-69973 -69974 -69975 -69976 -69977 -69978 -69979 -69980 -69981 -69982
{{out|output|text= (shown at3/4 size) using an array size of: 36
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 36 138 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 174 37 137 270 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 304 175 38 136 269 394 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 426 305 176 39 135 268 393 510 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 540 427 306 177 40 134 267 392 509 618 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 646 541 428 307 178 41 133 266 391 508 617 718 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 744 647 542 429 308 179 42 132 265 390 507 616 717 810 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 834 745 648 543 430 309 180 43 131 264 389 506 615 716 809 894 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 916 835 746 649 544 431 310 181 44 130 263 388 505 614 715 808 893 970 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 990 917 836 747 650 545 432 311 182 45 129 262 387 504 613 714 807 892 969 1038 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1056 991 918 837 748 651 546 433 312 183 46 128 261 386 503 612 713 806 891 968 1037 1098 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1114 1057 992 919 838 749 652 547 434 313 184 47 127 260 385 502 611 712 805 890 967 1036 1097 1150 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1164 1115 1058 993 920 839 750 653 548 435 314 185 48 126 259 384 501 610 711 804 889 966 1035 1096 1149 1194 1231 1232 1233 1234 1235 1236 1237 1238 1239 1206 1165 1116 1059 994 921 840 751 654 549 436 315 186 49 125 258 383 500 609 710 803 888 965 1034 1095 1148 1193 1230 1259 1260 1261 1262 1263 1264 1265 1240 1207 1166 1117 1060 995 922 841 752 655 550 437 316 187 50 124 257 382 499 608 709 802 887 964 1033 1094 1147 1192 1229 1258 1279 1280 1281 1282 1283 1266 1241 1208 1167 1118 1061 996 923 842 753 656 551 438 317 188 51 123 256 381 498 607 708 801 886 963 1032 1093 1146 1191 1228 1257 1278 1291 1292 1293 1284 1267 1242 1209 1168 1119 1062 997 924 843 754 657 552 439 318 189 52 122 255 380 497 606 707 800 885 962 1031 1092 1145 1190 1227 1256 1277 1290 1295 1294 1285 1268 1243 1210 1169 1120 1063 998 925 844 755 658 553 440 319 190 53 121 254 379 496 605 706 799 884 961 1030 1091 1144 1189 1226 1255 1276 1289 1288 1287 1286 1269 1244 1211 1170 1121 1064 999 926 845 756 659 554 441 320 191 54 120 253 378 495 604 705 798 883 960 1029 1090 1143 1188 1225 1254 1275 1274 1273 1272 1271 1270 1245 1212 1171 1122 1065 1000 927 846 757 660 555 442 321 192 55 119 252 377 494 603 704 797 882 959 1028 1089 1142 1187 1224 1253 1252 1251 1250 1249 1248 1247 1246 1213 1172 1123 1066 1001 928 847 758 661 556 443 322 193 56 118 251 376 493 602 703 796 881 958 1027 1088 1141 1186 1223 1222 1221 1220 1219 1218 1217 1216 1215 1214 1173 1124 1067 1002 929 848 759 662 557 444 323 194 57 117 250 375 492 601 702 795 880 957 1026 1087 1140 1185 1184 1183 1182 1181 1180 1179 1178 1177 1176 1175 1174 1125 1068 1003 930 849 760 663 558 445 324 195 58 116 249 374 491 600 701 794 879 956 1025 1086 1139 1138 1137 1136 1135 1134 1133 1132 1131 1130 1129 1128 1127 1126 1069 1004 931 850 761 664 559 446 325 196 59 115 248 373 490 599 700 793 878 955 1024 1085 1084 1083 1082 1081 1080 1079 1078 1077 1076 1075 1074 1073 1072 1071 1070 1005 932 851 762 665 560 447 326 197 60 114 247 372 489 598 699 792 877 954 1023 1022 1021 1020 1019 1018 1017 1016 1015 1014 1013 1012 1011 1010 1009 1008 1007 1006 933 852 763 666 561 448 327 198 61 113 246 371 488 597 698 791 876 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 853 764 667 562 449 328 199 62 112 245 370 487 596 697 790 875 874 873 872 871 870 869 868 867 866 865 864 863 862 861 860 859 858 857 856 855 854 765 668 563 450 329 200 63 111 244 369 486 595 696 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 770 769 768 767 766 669 564 451 330 201 64 110 243 368 485 594 695 694 693 692 691 690 689 688 687 686 685 684 683 682 681 680 679 678 677 676 675 674 673 672 671 670 565 452 331 202 65 109 242 367 484 593 592 591 590 589 588 587 586 585 584 583 582 581 580 579 578 577 576 575 574 573 572 571 570 569 568 567 566 453 332 203 66 108 241 366 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 333 204 67 107 240 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 205 68 106 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 69 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70
This REXX version automatically adjusts the width of the spiral matrix columns to minimize the area of the matrix display (so more elements may be shown on a display screen).
/*REXX program displays a spiral in a square array (of any size) starting at START. */parseargsizestart./*obtain optional arguments from the CL*/ifsize==''|size==","thensize=5/*Not specified? Then use the default.*/ifstart==''|start==","thenstart=0/*Not specified? Then use the default.*/tot=size**2;L=length(tot+start)/*total number of elements in spiral. */k=size/*K: is the counter for the spiral. */row=1;col=0/*start spiral at row 1, column 0. *//* [↓] construct the numbered spiral. */don=0fork;col=col+1;@.col.row=n+start;end;ifk==0thenexit/* [↑] build the first row of spiral. */dountiln>=tot/*spiral matrix.*/doone=1to-1by-2untiln>=tot;k=k-1/*perform twice.*/don=nfork;row=row+one;@.col.row=n+start;end/*for the row···*/don=nfork;col=col-one;@.col.row=n+start;end/* " " col···*/end/*one*//* ↑↓ direction.*/end/*until n≥tot*//* [↑] done with the matrix spiral. */!.=0/* [↓] display spiral to the screen. */dotwo=0for2/*1st time? Find max column and width.*/dor=1forsize;_=/*construct display row by row. */doc=1forsize;x=@.c.r/*construct a line column by column. */iftwothen_=_right(x,!.c)/*construct a line for the display. */else!.c=max(!.c,length(x))/*find the maximum width of the column.*/end/*c*//* [↓] line has an extra leading blank*/iftwothensaysubstr(_,2)/*this SUBSTR ignores the first blank. */end/*r*/end/*two*//*stick a fork in it, we're all done. */
{{out|output|text= (shown at3/4 size) using an array size of: 36
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 36138 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 174 37137 270 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 304 175 38136 269 394 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 426 305 176 39135 268 393 510 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 540 427 306 177 40134 267 392 509 618 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 646 541 428 307 178 41133 266 391 508 617 718 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 744 647 542 429 308 179 42132 265 390 507 616 717 810 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 834 745 648 543 430 309 180 43131 264 389 506 615 716 809 894 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 916 835 746 649 544 431 310 181 44130 263 388 505 614 715 808 893 970 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 990 917 836 747 650 545 432 311 182 45129 262 387 504 613 714 807 892 969 1038 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1056 991 918 837 748 651 546 433 312 183 46128 261 386 503 612 713 806 891 968 1037 1098 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1114 1057 992 919 838 749 652 547 434 313 184 47127 260 385 502 611 712 805 890 967 1036 1097 1150 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1164 1115 1058 993 920 839 750 653 548 435 314 185 48126 259 384 501 610 711 804 889 966 1035 1096 1149 1194 1231 1232 1233 1234 1235 1236 1237 1238 1239 1206 1165 1116 1059 994 921 840 751 654 549 436 315 186 49125 258 383 500 609 710 803 888 965 1034 1095 1148 1193 1230 1259 1260 1261 1262 1263 1264 1265 1240 1207 1166 1117 1060 995 922 841 752 655 550 437 316 187 50124 257 382 499 608 709 802 887 964 1033 1094 1147 1192 1229 1258 1279 1280 1281 1282 1283 1266 1241 1208 1167 1118 1061 996 923 842 753 656 551 438 317 188 51123 256 381 498 607 708 801 886 963 1032 1093 1146 1191 1228 1257 1278 1291 1292 1293 1284 1267 1242 1209 1168 1119 1062 997 924 843 754 657 552 439 318 189 52122 255 380 497 606 707 800 885 962 1031 1092 1145 1190 1227 1256 1277 1290 1295 1294 1285 1268 1243 1210 1169 1120 1063 998 925 844 755 658 553 440 319 190 53121 254 379 496 605 706 799 884 961 1030 1091 1144 1189 1226 1255 1276 1289 1288 1287 1286 1269 1244 1211 1170 1121 1064 999 926 845 756 659 554 441 320 191 54120 253 378 495 604 705 798 883 960 1029 1090 1143 1188 1225 1254 1275 1274 1273 1272 1271 1270 1245 1212 1171 1122 1065 1000 927 846 757 660 555 442 321 192 55119 252 377 494 603 704 797 882 959 1028 1089 1142 1187 1224 1253 1252 1251 1250 1249 1248 1247 1246 1213 1172 1123 1066 1001 928 847 758 661 556 443 322 193 56118 251 376 493 602 703 796 881 958 1027 1088 1141 1186 1223 1222 1221 1220 1219 1218 1217 1216 1215 1214 1173 1124 1067 1002 929 848 759 662 557 444 323 194 57117 250 375 492 601 702 795 880 957 1026 1087 1140 1185 1184 1183 1182 1181 1180 1179 1178 1177 1176 1175 1174 1125 1068 1003 930 849 760 663 558 445 324 195 58116 249 374 491 600 701 794 879 956 1025 1086 1139 1138 1137 1136 1135 1134 1133 1132 1131 1130 1129 1128 1127 1126 1069 1004 931 850 761 664 559 446 325 196 59115 248 373 490 599 700 793 878 955 1024 1085 1084 1083 1082 1081 1080 1079 1078 1077 1076 1075 1074 1073 1072 1071 1070 1005 932 851 762 665 560 447 326 197 60114 247 372 489 598 699 792 877 954 1023 1022 1021 1020 1019 1018 1017 1016 1015 1014 1013 1012 1011 1010 1009 1008 1007 1006 933 852 763 666 561 448 327 198 61113 246 371 488 597 698 791 876 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 853 764 667 562 449 328 199 62112 245 370 487 596 697 790 875 874 873 872 871 870 869 868 867 866 865 864 863 862 861 860 859 858 857 856 855 854 765 668 563 450 329 200 63111 244 369 486 595 696 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 770 769 768 767 766 669 564 451 330 201 64110 243 368 485 594 695 694 693 692 691 690 689 688 687 686 685 684 683 682 681 680 679 678 677 676 675 674 673 672 671 670 565 452 331 202 65109 242 367 484 593 592 591 590 589 588 587 586 585 584 583 582 581 580 579 578 577 576 575 574 573 572 571 570 569 568 567 566 453 332 203 66108 241 366 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 333 204 67107 240 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 205 68106 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 69105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70
# Project : Spiral matrixload "guilib.ring"load "stdlib.ring"new qapp { win1 = new qwidget() { setwindowtitle("Spiral matrix") setgeometry(100,100,600,400) n = 5 result = newlist(n,n) spiral = newlist(n,n) k = 1 top = 1 bottom = n left = 1 right = n while (k <= n*n) for i= left to right result[top][i] = k k = k + 1 next top = top + 1 for i = top to bottom result[i][right] = k k = k + 1 next right = right - 1 for i = right to left step -1 result[bottom][i] = k k = k + 1 next bottom = bottom - 1 for i = bottom to top step -1 result[i][left] = k k = k + 1 next left = left + 1 end for m = 1 to n for p = 1 to n spiral[p][m] = new qpushbutton(win1) { x = 150+m*40 y = 30 + p*40 setgeometry(x,y,40,40) settext(string(result[m][p])) } next next show() } exec() }Output:
« { 0 1 } → n step « { 1 1 } n DUP 2 →LIST -1 CON@ empty cell = -1 1 n SQFOR j OVER j PUT DUP2 SWAP step ADDIF IFERR GETTHEN DROP2 1ELSE -1 ≠END@ if next step is out of border or an already written cellTHEN step REVLIST { 1 -1 } * 'step' STOEND@ then turn right SWAP step ADD SWAPNEXT » » 'SPIRAL' STO5SPIRAL1: [[1 2 3 4 5] [16 17 18 19 6] [15 24 25 20 7] [14 23 22 21 8] [13 12 11 10 9]]
defspiral(n)spiral=Array.new(n){Array.new(n,nil)}# n x n array of nilsruns=n.downto(0).each_cons(2).to_a.flatten# n==5; [5,4,4,3,3,2,2,1,1,0]delta=[[1,0],[0,1],[-1,0],[0,-1]].cyclex,y,value=-1,0,-1forruninrunsdx,dy=delta.nextrun.times{spiral[y+=dy][x+=dx]=(value+=1)}endspiralenddefprint_matrix(m)width=m.flatten.map{|x|x.to_s.size}.maxm.each{|row|putsrow.map{|x|"%#{width}s "%x}.join}endprint_matrixspiral(5)
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
The other way
n=5m=Array.new(n){Array.new(n)}pos,side=-1,nforiin0..(n-1)/2(0...side).each{|j|m[i][i+j]=(pos+=1)}(1...side).each{|j|m[i+j][n-1-i]=(pos+=1)}side-=2side.downto(0){|j|m[n-1-i][i+j]=(pos+=1)}side.downto(1){|j|m[i+j][i]=(pos+=1)}endfmt="%#{(n*n-1).to_s.size}d "*nputsm.map{|row|fmt%row}
Output as above.
It processes the Array which is for work without creating it.
defspiral_matrix(n)x,y,dx,dy=-1,0,0,-1fmt="%#{(n*n-1).to_s.size}d "*nn.downto(1).flat_map{|x|[x,x-1]}.flat_map{|run|dx,dy=-dy,dx# turn 90run.times.map{[y+=dy,x+=dx]}}.each_with_index.sort.map(&:last).each_slice(n){|row|putsfmt%row}endspiral_matrix(5)
constVECTORS:[(isize,isize);4]=[(1,0),(0,1),(-1,0),(0,-1)];pubfnspiral_matrix(size:usize)->Vec<Vec<u32>>{letmutmatrix=vec![vec![0;size];size];letmutmovement=VECTORS.iter().cycle();let(mutx,muty,mutn)=(-1,0,1..);for(move_x,move_y)instd::iter::once(size).chain((1..size).rev().flat_map(|n|std::iter::repeat(n).take(2))).flat_map(|steps|std::iter::repeat(movement.next().unwrap()).take(steps)){x+=move_x;y+=move_y;matrix[yasusize][xasusize]=n.next().unwrap();}matrix}fnmain(){foriinspiral_matrix(4).iter(){forjini.iter(){print!("{:>2} ",j);}println!();}}
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
classFolder(){vardir=(1,0)varpos=(-1,0)defapply(l:List[Int],a:Array[Array[Int]])={var(x,y)=pos//start positionvar(dx,dy)=dir//directionl.foreach{e=>x=x+dx;y=y+dy;a(y)(x)=e}//copy l elements to array using current directionpos=(x,y)dir=(-dy,dx)//turn}}defspiral(n:Int)={defdup(n:Int)=(1ton).flatMap(i=>List(i,i)).toListvalfolds=n::dup(n-1).reverse//define fold part lengthsvararray=newArray[Array[Int]](n,n)valfold=newFolder()varseq=(0untiln*n).toList//sequence to foldfolds.foreach{len=>fold(seq.take(len),array);seq=seq.drop(len)}array}
Explanation: if you see the sequence of numbers to spiral around as a tape to fold around, you can see this pattern on the lenght of tape segment to fold in each step:
Using this the solution becomes very simple,
It's simple to make this generic, changing start position, initial direction, etc.The code could be more compact, but I'm leaving it like this for clarity.
function a = spiral(n) a = ones(n*n, 1) v = ones(n, 1) u = -n*v; i = n for k = n-1:-1:1 j = 1:k u(j) = -u(j) a(j+i) = u(j) v(j) = -v(j) a(j+(i+k)) = v(j) i = i+2*k end a(cumsum(a)) = (1:n*n)' a = matrix(a, n, n)'-1endfunction-->spiral(5) ans = 0. 1. 2. 3. 4. 15. 16. 17. 18. 5. 14. 23. 24. 19. 6. 13. 22. 21. 20. 7. 12. 11. 10. 9. 8.
$ include "seed7_05.s7i";const type: matrix is array array integer;const func matrix: spiral (in integer: n) is func result var matrix: myArray is matrix.value; local var integer: i is 0; var integer: dx is 1; var integer: dy is 0; var integer: x is 1; var integer: y is 1; var integer: nx is 0; var integer: ny is 0; var integer: swap is 0; begin myArray := n times n times 0; for i range 1 to n**2 do myArray[x][y] := i; nx := x + dx; ny := y + dy; if nx >= 1 and nx <= n and ny >= 1 and ny <= n and myArray[nx][ny] = 0 then x := nx; y := ny; else swap := dx; dx := -dy; dy := swap; x +:= dx; y +:= dy; end if; end for; end func;const proc: writeMatrix (in matrix: myArray) is func local var integer: x is 0; var integer: y is 0; begin for key y range myArray do for key x range myArray[y] do write(myArray[x][y] lpad 4); end for; writeln; end for; end func;const proc: main is func begin writeMatrix(spiral(5)); end func;
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
funcspiral(n){var(x,y,dx,dy,a)=(0,0,1,0,[]){|i|a[y][x]=ivar(nx,ny)=(x+dx,y+dy)(if(dx==1&&(nx==n||a[ny][nx]!=nil)){[0,1]}elsif(dy==1&&(ny==n||a[ny][nx]!=nil)){[-1,0]}elsif(dx==-1&&(nx<0||a[ny][nx]!=nil)){[0,-1]}elsif(dy==-1&&(ny<0||a[ny][nx]!=nil)){[1,0]}else{[dx,dy]}) »(\dx,\dy)x=x+dxy=y+dy}<<(1..n**2)returna} spiral(5).each{|row|row.map{"%3d"%_}.join(' ').say}
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
function spiral_mat(n) {a =J(n*n,1,1)u =J(n,1,-n)v =J(n,1,1)for (k=(i=n)-1; k>=1; i=i+2*k--) {j =1..ka[j:+i] = u[j] =-u[j]a[j:+(i+k)] = v[j] =-v[j]}return(rowshape(invorder(runningsum(a)),n):-1)}spiral_mat(5)12345+--------------------------+1 |01234 |2 |151617185 |3 |142324196 |4 |132221207 |5 |12111098 |+--------------------------+Usingprint_matrix fromMatrix Transpose#Tcl
packagerequireTcl8.5namespacepath{::tcl::mathop}procspiralsize{setm[lrepeat$size[lrepeat$size.]]setx0;setdx0sety-1;setdy1seti-1while{$i<$size**2-1}{if{$dy==0}{incrx$dxif{0<=$x&&$x<$size&&[lindex$m$x$y]eq"."}{lsetm$x$y[incri]}else{# back up and change directionincrx[-$dx]setdy[-$dx]setdx0}}else{incry$dyif{0<=$y&&$y<$size&&[lindex$m$x$y]eq"."}{lsetm$x$y[incri]}else{# back up and change directionincry[-$dy]setdx$dysetdy0}}}return$m}print_matrix[spiral5]
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
5->NDelVar [F]{N,N}→dim([F])1→A: N→B1→C: N→D0→E: E→G 1→I: 1→J For(K,1,N*N)K-1→[F](I,J)If E=0: Then If J<D: ThenJ+1→JElse: 1→GI+1→I: A+1→AEndEndIf E=1: Then If I<B: ThenI+1→IElse: 2→GJ-1→J: D-1→DEndEndIf E=2: ThenIf J>C: ThenJ-1→JElse: 3→GI-1→I: B-1→BEndEndIf E=3: Then If I>A: ThenI-1→IElse: 0→GJ+1→J: C+1→CEndEndG→EEnd[F][[0 1 2 3 4] [15 16 17 18 5] [14 23 24 19 6] [13 22 21 20 7] [12 11 10 9 8]]
// library: math: create: array: spiral: inwards <description></description> <version control></version control> <version>1.0.0.0.15</version> (filenamemacro=creamasi.s) [<Program>] [<Research>] [kn, ri, mo, 31-12-2012 01:15:43]PROC PROCMathCreateArraySpiralInwards( INTEGER nI ) // e.g. PROC Main() // e.g. STRING s1[255] = "5" // e.g. IF ( NOT ( Ask( "math: create: array: spiral: inwards: nI = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF // e.g. PROCMathCreateArraySpiralInwards( Val( s1 ) ) // e.g. END // e.g. // e.g. <F12> Main() // INTEGER columnEndI = 0 // INTEGER columnBeginI = nI - 1 // INTEGER rowEndI = 0 // INTEGER rowBeginI = nI - 1 // INTEGER columnI = 0 // INTEGER rowI = 0 // INTEGER minI = 0 INTEGER maxI = nI * nI - 1 INTEGER I = 0 // INTEGER columnWidthI = Length( Str( nI * nI - 1 ) ) + 1 // INTEGER directionRightI = 0 INTEGER directionLeftI = 1 INTEGER directionDownI = 2 INTEGER directionUpI = 3 // INTEGER directionI = directionRightI // FOR I = minI TO maxI // SetGlobalInt( Format( "MatrixS", columnI, ",", rowI ), I ) // SetGlobalInt( Format( "MatrixS", columnI, ",", rowI ), I ) // PutStrXY( ( Query( ScreenCols ) / 8 ) + columnI * columnWidthI, ( Query( ScreenRows ) / 8 ) + rowI, Str( I ), Color( BRIGHT RED ON WHITE ) ) // PutStrXY( ( Query( ScreenCols ) / 8 ) + columnI * columnWidthI, ( Query( ScreenRows ) / 8 ) + rowI, Str( I + 1 ), Color( BRIGHT RED ON WHITE ) ) // CASE directionI // WHEN directionRightI // IF ( columnI < columnBeginI ) // columnI = columnI + 1 // ELSE // directionI = directionDownI // rowI = rowI + 1 // rowEndI = rowEndI + 1 // ENDIF // WHEN directionDownI // IF ( rowI < rowBeginI ) // rowI = rowI + 1 // ELSE // directionI = directionLeftI // columnI = columnI - 1 // columnBeginI = columnBeginI - 1 // ENDIF // WHEN directionLeftI // IF ( columnI > columnEndI ) // columnI = columnI - 1 // ELSE // directionI = directionUpI // rowI = rowI - 1 // rowBeginI = rowBeginI - 1 // ENDIF // WHEN directionUpI // IF ( rowI > rowEndI ) // rowI = rowI - 1 // ELSE // directionI = directionRightI // columnI = columnI + 1 // columnEndI = columnEndI + 1 // ENDIF // OTHERWISE // Warn( Format( "PROCMathCreateArraySpiralInwards(", " ", "case", " ", ":", " ", Str( directionI ), ": not known" ) ) // RETURN() // ENDCASE // ENDFOR //ENDPROC Main()STRING s1[255] = "5"IF ( NOT ( Ask( "math: create: array: spiral: inwards: nI = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF PROCMathCreateArraySpiralInwards( Val( s1 ) )ENDThis recursive version is quite compact.
Input "Width: ";wInput "Height: ";hPrintFor i = 0 To h-1 For j = 0 To w-1 Print Using "__#"; FUNC(_Spiral(w,h,j,i)); Next PrintNextEnd_Spiral Param(4)If d@ Then Return (a@ + FUNC(_Spiral(b@-1, a@, d@ - 1, a@ - c@ - 1)))Else Return (c@)EndIf
spiralMatrix.spiralMatrix : Nat -> [[Nat]]spiralMatrix.spiralMatrix = cases 0 -> [] n -> go h w s = match h with 0 -> [] h' -> Nat.range s (s + w) +: (List.reverse >> List.transpose) (go w (h' - 1) (w + s)) go n n 1
Helpful hints from theJ example are gratefully acknowledged. The spiral function works for any n, and results are shown for n equal to 5, 6, and 7. The results are represented as lists of lists rather than arrays.
#import std#import nat#import intspiral =^H/block nleq-<lS&r+ -+ num@NiC+ sum:-0*yK33x+ (|\LL negation**)+ rlc ~&lh==1, ~&rNNXNXSPlrDlSPK32^lrtxiiNCCSLhiC5D/~& iota*+ iota+-#cast %nLLLexamples = spiral* <5,6,7>
< < <0,1,2,3,4>, <15,16,17,18,5>, <14,23,24,19,6>, <13,22,21,20,7>, <12,11,10,9,8>>, < <0,1,2,3,4,5>, <19,20,21,22,23,6>, <18,31,32,33,24,7>, <17,30,35,34,25,8>, <16,29,28,27,26,9>, <15,14,13,12,11,10>>, < <0,1,2,3,4,5,6>, <23,24,25,26,27,28,7>, <22,39,40,41,42,29,8>, <21,38,47,48,43,30,9>, <20,37,46,45,44,31,10>, <19,36,35,34,33,32,11>, <18,17,16,15,14,13,12>>>
Function build_spiral(n)botcol = 0 : topcol = n - 1botrow = 0 : toprow = n - 1'declare a two dimensional arrayDim matrix()ReDim matrix(topcol,toprow)dir = 0 : col = 0 : row = 0'populate the arrayFor i = 0 To n*n-1matrix(col,row) = iSelect Case dirCase 0If col < topcol Thencol = col + 1Elsedir = 1 : row = row + 1 : botrow = botrow + 1End IfCase 1If row < toprow Thenrow = row + 1Elsedir = 2 : col = col - 1 : topcol = topcol - 1End IfCase 2If col > botcol Thencol = col - 1Elsedir = 3 : row = row - 1 : toprow = toprow - 1End IfCase 3If row > botrow Thenrow = row - 1Elsedir = 0 : col = col + 1 : botcol = botcol + 1End IfEnd SelectNext'print the arrayFor y = 0 To n-1For x = 0 To n-1WScript.StdOut.Write matrix(x,y) & vbTabNextWScript.StdOut.WriteLineNextEnd Functionbuild_spiral(CInt(WScript.Arguments(0)))
F:\>cscript /nologo build_spiral.vbs 50 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8F:\>cscript /nologo build_spiral.vbs 70 1 2 3 4 5 623 24 25 26 27 28 722 39 40 41 42 29 821 38 47 48 43 30 920 37 46 45 44 31 1019 36 35 34 33 32 1118 17 16 15 14 13 12
This requires VB6.
Option ExplicitSub Main() print2dArray getSpiralArray(5)End SubFunction getSpiralArray(dimension As Integer) As Integer() ReDim spiralArray(dimension - 1, dimension - 1) As Integer Dim numConcentricSquares As Integer numConcentricSquares = dimension \ 2 If (dimension Mod 2) Then numConcentricSquares = numConcentricSquares + 1 Dim j As Integer, sideLen As Integer, currNum As Integer sideLen = dimension Dim i As Integer For i = 0 To numConcentricSquares - 1 ' do top side For j = 0 To sideLen - 1 spiralArray(i, i + j) = currNum currNum = currNum + 1 Next ' do right side For j = 1 To sideLen - 1 spiralArray(i + j, dimension - 1 - i) = currNum currNum = currNum + 1 Next ' do bottom side For j = sideLen - 2 To 0 Step -1 spiralArray(dimension - 1 - i, i + j) = currNum currNum = currNum + 1 Next ' do left side For j = sideLen - 2 To 1 Step -1 spiralArray(i + j, i) = currNum currNum = currNum + 1 Next sideLen = sideLen - 2 Next getSpiralArray = spiralArray()End FunctionSub print2dArray(arr() As Integer) Dim row As Integer, col As Integer For row = 0 To UBound(arr, 1) For col = 0 To UBound(arr, 2) - 1 Debug.Print arr(row, col), Next Debug.Print arr(row, UBound(arr, 2)) NextEnd Sub
Sub spiral() Dim n As Integer, a As Integer, b As Integer Dim numCsquares As Integer, sideLen As Integer, currNum As Integer Dim j As Integer, i As Integer Dim j1 As Integer, j2 As Integer, j3 As Integer n = 5 Dim spiralArr(9, 9) As Integer numCsquares = CInt(Application.WorksheetFunction.Ceiling(n / 2, 1)) sideLen = n currNum = 0 For i = 0 To numCsquares - 1 'do top side For j = 0 To sideLen - 1 currNum = currNum + 1 spiralArr(i, i + j) = currNum Next j 'do right side For j1 = 1 To sideLen - 1 currNum = currNum + 1 spiralArr(i + j1, n - 1 - i) = currNum Next j1 'do bottom side j2 = sideLen - 2 Do While j2 > -1 currNum = currNum + 1 spiralArr(n - 1 - i, i + j2) = currNum j2 = j2 - 1 Loop 'do left side j3 = sideLen - 2 Do While j3 > 0 currNum = currNum + 1 spiralArr(i + j3, i) = currNum j3 = j3 - 1 Loop sideLen = sideLen - 2 Next i For a = 0 To n - 1 For b = 0 To n - 1 Cells(a + 1, b + 1).Select ActiveCell.Value = spiralArr(a, b) Next b Next aEnd Sub
Sub spiral(n As Integer) Const FREE = -9 'negative number indicates unoccupied cell Dim A() As Integer Dim rowdelta(3) As Integer Dim coldelta(3) As Integer 'initialize A to a matrix with an extra "border" of occupied cells 'this avoids having to test if we've reached the edge of the matrix ReDim A(0 To n + 1, 0 To n + 1) 'Since A is initialized with zeros, setting A(1 to n,1 to n) to "FREE" 'leaves a "border" around it occupied with zeroes For i = 1 To n: For j = 1 To n: A(i, j) = FREE: Next: Next 'set amount to move in directions "right", "down", "left", "up" rowdelta(0) = 0: coldelta(0) = 1 rowdelta(1) = 1: coldelta(1) = 0 rowdelta(2) = 0: coldelta(2) = -1 rowdelta(3) = -1: coldelta(3) = 0 curnum = 0 'set current cell position col = 1 row = 1 'set current direction theDir = 0 'theDir = 1 will fill the matrix counterclockwise 'ok will be true as long as there is a free cell left ok = True Do While ok 'occupy current FREE cell and increase curnum A(row, col) = curnum curnum = curnum + 1 'check if next cell in current direction is free 'if not, try another direction in clockwise fashion 'if all directions lead to occupied cells then we are finished! ok = False For i = 0 To 3 newdir = (theDir + i) Mod 4 If A(row + rowdelta(newdir), col + coldelta(newdir)) = FREE Then 'yes, move to it and change direction if necessary theDir = newdir row = row + rowdelta(theDir) col = col + coldelta(theDir) ok = True Exit For End If Next i Loop 'print result For i = 1 To n For j = 1 To n Debug.Print A(i, j), Next Debug.Print Next End Sub
spiral 5 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8 spiral 6 0 1 2 3 4 5 19 20 21 22 23 6 18 31 32 33 24 7 17 30 35 34 25 8 16 29 28 27 26 9 15 14 13 12 11 10
Platform:.NET
From VB6. This requires Visual Basic .Net.
Module modSpiralArray Sub Main() print2dArray(getSpiralArray(5)) End Sub Function getSpiralArray(dimension As Integer) As Object Dim spiralArray(,) As Integer Dim numConcentricSquares As Integer ReDim spiralArray(dimension - 1, dimension - 1) numConcentricSquares = dimension \ 2 If (dimension Mod 2) Then numConcentricSquares = numConcentricSquares + 1 Dim j As Integer, sideLen As Integer, currNum As Integer sideLen = dimension Dim i As Integer For i = 0 To numConcentricSquares - 1 ' do top side For j = 0 To sideLen - 1 spiralArray(i, i + j) = currNum currNum = currNum + 1 Next ' do right side For j = 1 To sideLen - 1 spiralArray(i + j, dimension - 1 - i) = currNum currNum = currNum + 1 Next ' do bottom side For j = sideLen - 2 To 0 Step -1 spiralArray(dimension - 1 - i, i + j) = currNum currNum = currNum + 1 Next ' do left side For j = sideLen - 2 To 1 Step -1 spiralArray(i + j, i) = currNum currNum = currNum + 1 Next sideLen = sideLen - 2 Next getSpiralArray = spiralArray End Function Sub print2dArray(arr) Dim row As Integer, col As Integer, s As String For row = 0 To UBound(arr, 1) s = "" For col = 0 To UBound(arr, 2) s = s & " " & Right(" " & arr(row, col), 3) Next Debug.Print(s) Next End SubEnd Moduleimport "./fmt" for Conv, Fmtvar n = 5var top = 0var left = 0var bottom = n - 1var right = n - 1var sz = n * nvar a = List.filled(sz, 0)var i = 0while (left < right) { // work right, along top var c = left while (c <= right) { a[top*n+c] = i i = i + 1 c = c + 1 } top = top + 1 // work down right side var r = top while (r <= bottom) { a[r*n+right] = i i = i + 1 r = r + 1 } right = right - 1 if (top == bottom) break // work left, along bottom c = right while (c >= left) { a[bottom*n+c] = i i = i + 1 c = c - 1 } bottom = bottom - 1 r = bottom // work up left side while (r >= top) { a[r*n+left] = i i = i + 1 r = r - 1 } left = left + 1}// center (last) elementa[top*n+left] = i// printvar w = Conv.itoa(n*n - 1).counti = 0for (e in a) { Fmt.write("$*d ", w, e) if (i%n == n - 1) System.print() i = i + 1}0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
def N=5;int A(N,N);int I, J, X, Y, Steps, Dir;include c:\cxpl\codes;[Clear;I:= 0; X:= -1; Y:= 0; Steps:= N; Dir:= 0;repeat for J:= 1 to Steps do [case Dir&3 of 0: X:= X+1; 1: Y:= Y+1; 2: X:= X-1; 3: Y:= Y-1 other []; A(X,Y):= I; Cursor(X*3,Y); IntOut(0,I); I:= I+1; ]; Dir:= Dir+1; if Dir&1 then Steps:= Steps-1;until Steps = 0;Cursor(0,N);]
0 1 2 3 415 16 17 18 514 23 24 19 613 22 21 20 712 11 10 9 8
N is set at beginning of code (valid range 1..150-ish, then you soon run out of memory), sjasmplus syntax, CP/M executable:
; Spiral matrix in Z80 assembly (for CP/M OS - you can use `tnylpo` or `z88dk-ticks` on PC) OPT --syntax=abf : OUTPUT "spiralmt.com" ; asm syntax for z00m's variant of sjasmplus ORG $100spiral_matrix: ld a,5 ; N matrix size (argument for the code) (valid range: 1..150) ; setup phase push af ld l,a ld h,0 add hl,hl ld (delta_d),hl ; down-direction address delta = +N*2 neg ld l,a ld h,$FF add hl,hl ld (delta_u),hl ; up-direction address delta = -N*2 neg ld hl,matrix ld de,2 ; delta_r value to move right in matrix ld bc,0 ; starting value dec a ; first sequences will be N-1 long jr z,.finish ; 1x1 doesn't need any sequence, just set last element call set_sequence ; initial entry sequence has N-1 elements (same as two more) ; main loop - do twice same length sequence, then decrement length, until zero.loop: call set_sequence_twice dec a jr nz,.loop.finish: ; whole spiral is set except last element, set it now ld (hl),c inc hl ld (hl),b ; print matrix - reading it by POP HL (destructive, plus some memory ahead of matrix too) pop de ; d = N ld (.oldsp+1),sp ld sp,matrix ; set stack to beginning of matrix (call/push does damage memory ahead) ld c,d ; c = N (lines counter).print_rows: ld b,d ; b = N (value per row counter).print_row: pop hl push de push bc call print_hl pop bc pop de djnz .print_row push de call print_crlf pop de dec c jr nz,.print_rows.oldsp: ld sp,0 rst 0 ; return to CP/Mprint_crlf: ld e,10 call print_char ld e,13 jr print_charprint_hl: ld b,' ' ld e,b call print_char ld de,-10000 call extract_digit ld de,-1000 call extract_digit ld de,-100 call extract_digit ld de,-10 call extract_digit ld a,lprint_digit: ld b,'0' add a,b ld e,aprint_char: push bc push hl ld c,2 call 5 pop hl pop bc retextract_digit: ld a,-1.digit_loop: inc a add hl,de jr c,.digit_loop sbc hl,de or a jr nz,print_digit ld e,b jr print_charset_sequence_twice: call set_sequenceset_sequence: ; A = length, HL = next_to_matrix, DE = delta to advance hl, BC = next_value push af.set_loop: ld (hl),c inc hl ld (hl),b dec hl ; [HL] = BC add hl,de ; HL += DE inc bc ; ++BC dec a jr nz,.set_loop push hl ; change DE for next direction (right->down->left->up->right->...).d: ld hl,delta_d ; self-modify-code: pointer to next delta ld e,(hl) inc hl ld d,(hl) ; de = address delta for next sequence inc hl ld a,low delta_u+2 ; if hl == delta_u+2 => reset it back to delta_r cp l jr nz,.next_delta ld hl,delta_r.next_delta: ld (.d+1),hl ; self modify code pointer for next delta value pop hl pop af retdelta_r: dw +2 ; value to add to move right in matrixdelta_d: dw 0 ; value to add to move down in matrix (set to +N*2)delta_l: dw -2 ; value to add to move left in matrixdelta_u: dw 0 ; value to add to move up in matrix (set to -N*2)matrix: ; following memory is used for NxN matrix of uint16_t values (150x150 needs 45000 bytes)
$ tnylpo spiralmt.com 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
which turns out to be the same as Ruby
fcn spiralMatrix(n){ sm:=(0).pump(n,List,(0).pump(n,List,False).copy); //L(L(False,False..), L(F,F,..) ...) drc:=Walker.cycle(T(0,1,0), T(1,0,1), T(0,-1,0), T(-1,0,1)); // deltas len:=n; r:=0; c:=-1; z:=-1; while(len>0){ //or do(2*n-1){ dr,dc,dl:=drc.next(); do(len-=dl){ sm[r+=dr][c+=dc]=(z+=1); } } sm}foreach n in (T(5,-1,0,1,2)){ spiralMatrix(n).pump(Console.println,fcn(r){ r.apply("%4d".fmt).concat() }); println("---");}0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8--------- 0--- 0 1 3 2---