Looping em espiral

Um amigo estava precisando de um algoritmo que o deixasse percorrer os elementos de uma matriz NxM (N e M são ímpares). Eu encontrei uma solução, mas eu queria ver se meus companheiros SO”S poderiam encontrar uma solução melhor.

Estou postando minha solução como resposta a essa pergunta.

Exemplo de Saída:

Para uma matriz 3×3, a saída deve ser:

(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 )

Matriz 3x3

Além disso, o algoritmo deve suportar matrizes não quadradas, portanto, por exemplo, para uma matriz de 5×3, a saída deve ser:

(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 ) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)

Matriz 5x3

Aqui está a minha solução (em Python):

def spiral(X, Y): x = y = 0 dx = 0 dy = -1 for i in range(max(X, Y)**2): if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2): print (x, y) # DO STUFF... if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y): dx, dy = -dy, dx x, y = x+dx, y+dy 

C ++ alguém? Tradução rápida de python, postada para conclusão

 void Spiral( int X, int Y){ int x,y,dx,dy; x = y = dx =0; dy = -1; int t = std::max(X,Y); int maxI = t*t; for(int i =0; i < maxI; i++){ if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)){ // DO STUFF... } if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))){ t = dx; dx = -dy; dy = t; } x += dx; y += dy; } } 

Eu amo geradores de python.

 def spiral(N, M): x,y = 0,0 dx, dy = 0, -1 for dumb in xrange(N*M): if abs(x) == abs(y) and [dx,dy] != [1,0] or x>0 and y == 1-x: dx, dy = -dy, dx # corner, change direction if abs(x)>N/2 or abs(y)>M/2: # non-square dx, dy = -dy, dx # change direction x, y = -y+dx, x+dy # jump yield x, y x, y = x+dx, y+dy 

Testando com:

 print 'Spiral 3x3:' for a,b in spiral(3,3): print (a,b), print '\n\nSpiral 5x3:' for a,b in spiral(5,3): print (a,b), 

Você recebe:

 Spiral 3x3: (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) Spiral 5x3: (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1) 

Aqui está uma solução O (1) para encontrar a posição em uma espiral quadrada: Fiddle

 function spiral(n) { // given n an index in the squared spiral // p the sum of point in inner square // a the position on the current square // n = p + a var r = Math.floor((Math.sqrt(n + 1) - 1) / 2) + 1; // compute radius : inverse arithmetic sum of 8+16+24+...= var p = (8 * r * (r - 1)) / 2; // compute total point on radius -1 : arithmetic sum of 8+16+24+... var en = r * 2; // points by face var a = (1 + n - p) % (r * 8); // compute de position and shift it so the first is (-r,-r) but (-r+1,-r) // so square can connect var pos = [0, 0, r]; switch (Math.floor(a / (r * 2))) { // find the face : 0 top, 1 right, 2, bottom, 3 left case 0: { pos[0] = a - r; pos[1] = -r; } break; case 1: { pos[0] = r; pos[1] = (a % en) - r; } break; case 2: { pos[0] = r - (a % en); pos[1] = r; } break; case 3: { pos[0] = -r; pos[1] = r - (a % en); } break; } console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, " --> ", pos); return pos; } 
 let x = 0 let y = 0 let d = 1 let m = 1 while true while 2 * x * d < m print(x, y) x = x + d while 2 * y * d < m print(x, y) y = y + d d = -1 * d m = m + 1 

Muitas soluções propostas para este problema foram escritas em várias linguagens de programação, mas todas parecem derivar da mesma abordagem complicada. Vou considerar o problema mais geral de calcular uma espiral que pode ser expressa de forma concisa usando a indução.

Caso base: Comece em (0, 0), avance 1 quadrado, vire à esquerda, avance 1 quadrado, vire à esquerda. Etapa indutiva: Avance n + 1 quadrados, vire à esquerda, avance n + 1 quadrados, vire à esquerda.

A elegância matemática de expressar esse problema sugere fortemente que deve haver um algoritmo simples para calcular a solução. Mantendo a abstração em mente, optei por não implementar o algoritmo em uma linguagem de programação específica, mas sim como pseudo-código.

Primeiro, considerarei um algoritmo para calcular apenas duas iterações da espiral usando 4 pares de loops while. A estrutura de cada par é semelhante, mas distinta por si só. Isso pode parecer loucura no começo (alguns loops só são executados uma vez) mas passo a passo eu farei transformações até chegarmos a 4 pares de loops que são idênticos e, portanto, podem ser substituídos por um único par colocado dentro de outro loop. Isso nos fornecerá uma solução geral de computação n iterações sem o uso de condicionais.

 let x = 0 let y = 0 //RIGHT, UP while x < 1 print(x, y) x = x + 1 while y < 1 print(x, y) y = y + 1 //LEFT, LEFT, DOWN, DOWN while x > -1 print(x, y) x = x - 1 while y > -1 print(x, y) y = y - 1 //RIGHT, RIGHT, RIGHT, UP, UP, UP while x < 2 print(x, y) x = x + 1 while y < 2 print(x, y) y = y + 1 //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x > -2 print(x, y) x = x - 1 while y > -2 print(x, y) y = y - 1 

A primeira transformação que faremos é a introdução de uma nova variável d, para direção, que contém o valor +1 ou -1. A direção muda após cada par de loops. Como sabemos o valor de d em todos os pontos, podemos multiplicar cada lado de cada desigualdade por ele, ajustar a direção da desigualdade de acordo e simplificar quaisquer multiplicações de d por uma constante para outra constante. Isso nos deixa com o seguinte.

 let x = 0 let y = 0 let d = 1 //RIGHT, UP while x * d < 1 print(x, y) x = x + d while y * d < 1 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, DOWN, DOWN while x * d < 1 print(x, y) x = x + d while y * d < 1 print(x, y) y = y + d d = -1 * d //RIGHT, RIGHT, RIGHT, UP, UP, UP while x * d < 2 print(x, y) x = x + d while y * d < 2 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x * d < 2 print(x, y) x = x + d while y * d < 2 print(x, y) y = y + d 

Agora notamos que tanto x * d quanto o RHS são números inteiros, então podemos subtrair qualquer valor real entre 0 e 1 do RHS sem afetar o resultado da desigualdade. Escolhemos subtrair 0,5 das desigualdades de todos os outros pares de loops while para estabelecer mais de um padrão.

 let x = 0 let y = 0 let d = 1 //RIGHT, UP while x * d < 0.5 print(x, y) x = x + d while y * d < 0.5 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, DOWN, DOWN while x * d < 1 print(x, y) x = x + d while y * d < 1 print(x, y) y = y + d d = -1 * d //RIGHT, RIGHT, RIGHT, UP, UP, UP while x * d < 1.5 print(x, y) x = x + d while y * d < 1.5 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x * d < 2 print(x, y) x = x + d while y * d < 2 print(x, y) y = y + d 

Podemos agora introduzir outra variável m para o número de passos que damos em cada par de loops while.

 let x = 0 let y = 0 let d = 1 let m = 0.5 //RIGHT, UP while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d d = -1 * d m = m + 0.5 //LEFT, LEFT, DOWN, DOWN while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d d = -1 * d m = m + 0.5 //RIGHT, RIGHT, RIGHT, UP, UP, UP while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d d = -1 * d m = m + 0.5 //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d 

Finalmente, vemos que a estrutura de cada par de loops while é idêntica e pode ser reduzida a um único loop colocado dentro de outro loop. Além disso, para evitar o uso de números de valores reais, multipliquei o valor inicial de m; o valor m é incrementado por; e ambos os lados de cada desigualdade por 2.

Isso leva à solução mostrada no início desta resposta.

Tentativa “Code golf” em espiral de Java, baseada na variante C ++.

 public static void Spiral(int X, int Y) { int x=0, y=0, dx = 0, dy = -1; int t = Math.max(X,Y); int maxI = t*t; for (int i=0; i < maxI; i++){ if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)) { System.out.println(x+","+y); //DO STUFF } if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))) { t=dx; dx=-dy; dy=t; } x+=dx; y+=dy; } } 

Aqui está uma solução em C ++ que mostra que você pode calcular as próximas coordenadas (x, y) direta e facilmente das anteriores – sem necessidade de rastrear a direção atual, o raio ou qualquer outra coisa:

 void spiral(const int M, const int N) { // Generate an Ulam spiral centered at (0, 0). int x = 0; int y = 0; int end = max(N, M) * max(N, M); for(int i = 0; i < end; ++i) { // Translate coordinates and mask them out. int xp = x + N / 2; int yp = y + M / 2; if(xp >= 0 && xp < N && yp >= 0 && yp < M) cout << xp << '\t' << yp << '\n'; // No need to track (dx, dy) as the other examples do: if(abs(x) <= abs(y) && (x != y || x >= 0)) x += ((y >= 0) ? 1 : -1); else y += ((x >= 0) ? -1 : 1); } } 

Se tudo o que você está tentando fazer é gerar os primeiros N pontos na espiral (sem a restrição do problema original de mascarar para uma região N x M), o código se torna muito simples:

 void spiral(const int N) { int x = 0; int y = 0; for(int i = 0; i < N; ++i) { cout << x << '\t' << y << '\n'; if(abs(x) <= abs(y) && (x != y || x >= 0)) x += ((y >= 0) ? 1 : -1); else y += ((x >= 0) ? -1 : 1); } } 

O truque é que você pode comparar xey para determinar de que lado do quadrado você está, e isso indica em que direção se mover.

Aqui está a minha solução (em Ruby)

 def spiral(xDim, yDim) sx = xDim / 2 sy = yDim / 2 cx = cy = 0 direction = distance = 1 yield(cx,cy) while(cx.abs <= sx || cy.abs <= sy) distance.times { cx += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } distance.times { cy += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } distance += 1 direction *= -1 end end spiral(5,3) { |x,y| print "(#{x},#{y})," } 

TDD, em Java.

SpiralTest.java:

 import java.awt.Point; import java.util.List; import junit.framework.TestCase; public class SpiralTest extends TestCase { public void test3x3() throws Exception { assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)", strung(new Spiral(3, 3).spiral())); } public void test5x3() throws Exception { assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)", strung(new Spiral(5, 3).spiral())); } private String strung(List points) { StringBuffer sb = new StringBuffer(); for (Point point : points) sb.append(strung(point)); return sb.toString().trim(); } private String strung(Point point) { return String.format("(%s, %s) ", point.x, point.y); } } 

Spiral.java:

 import java.awt.Point; import java.util.ArrayList; import java.util.List; public class Spiral { private enum Direction { E(1, 0) {Direction next() {return N;}}, N(0, 1) {Direction next() {return W;}}, W(-1, 0) {Direction next() {return S;}}, S(0, -1) {Direction next() {return E;}},; private int dx; private int dy; Point advance(Point point) { return new Point(point.x + dx, point.y + dy); } abstract Direction next(); Direction(int dx, int dy) { this.dx = dx; this.dy = dy; } }; private final static Point ORIGIN = new Point(0, 0); private final int width; private final int height; private Point point; private Direction direction = Direction.E; private List list = new ArrayList(); public Spiral(int width, int height) { this.width = width; this.height = height; } public List spiral() { point = ORIGIN; int steps = 1; while (list.size() < width * height) { advance(steps); advance(steps); steps++; } return list; } private void advance(int n) { for (int i = 0; i < n; ++i) { if (inBounds(point)) list.add(point); point = direction.advance(point); } direction = direction.next(); } private boolean inBounds(Point p) { return between(-width / 2, width / 2, px) && between(-height / 2, height / 2, py); } private static boolean between(int low, int high, int n) { return low <= n && n <= high; } } 

Haskell, faça a sua escolha:

 spiral xy = (0, 0) : concatMap ring [1 .. max x' y'] where ring n | n > x' = left x' n ++ right x' (-n) ring n | n > y' = up ny' ++ down (-n) y' ring n = up nn ++ left nn ++ down nn ++ right nn up xy = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up right xy = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right (x', y') = (x `div` 2, y `div` 2) spiral xy = filter (\(x',y') -> 2*abs x' <= x && 2*abs y' <= y) . scanl (\(a,b) (c,d) -> (a+c,b+d)) (0,0) $ concat [ (:) (1,0) . tail $ concatMap (replicate n) [(0,1),(-1,0),(0,-1),(1,0)] | n <- [2,4..max xy] ] 

Isso está em C.

Por acaso eu escolhi nomes de variables ​​ruins. Nos nomes T == top, L == esquerda, B == inferior, R == direita. Então, tli é superior esquerdo i e brj é inferior direito j.

 #include typedef enum { TLTOR = 0, RTTOB, BRTOL, LBTOT } Direction; int main() { int arr[][3] = {{1,2,3},{4,5,6}, {7,8,9}, {10,11,12}}; int tli = 0, tlj = 0, bri = 3, brj = 2; int i; Direction d = TLTOR; while (tli < bri || tlj < brj) { switch (d) { case TLTOR: for (i = tlj; i <= brj; i++) { printf("%d ", arr[tli][i]); } tli ++; d = RTTOB; break; case RTTOB: for (i = tli; i <= bri; i++) { printf("%d ", arr[i][brj]); } brj --; d = BRTOL; break; case BRTOL: for (i = brj; i >= tlj; i--) { printf("%d ", arr[bri][i]); } bri --; d = LBTOT; break; case LBTOT: for (i = bri; i >= tli; i--) { printf("%d ", arr[i][tlj]); } tlj ++; d = TLTOR; break; } } if (tli == bri == tlj == brj) { printf("%d\n", arr[tli][tlj]); } } 

Aqui está c #, linq’ish.

 public static class SpiralCoords { public static IEnumerable> GenerateOutTo(int radius) { //TODO trap negative radius. 0 is ok. foreach(int r in Enumerable.Range(0, radius + 1)) { foreach(Tuple coord in GenerateRing(r)) { yield return coord; } } } public static IEnumerable> GenerateRing(int radius) { //TODO trap negative radius. 0 is ok. Tuple currentPoint = Tuple.Create(radius, 0); yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); //move up while we can while (currentPoint.Item2 < radius) { currentPoint.Item2 += 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move left while we can while (-radius < currentPoint.Item1) { currentPoint.Item1 -=1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move down while we can while (-radius < currentPoint.Item2) { currentPoint.Item2 -= 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move right while we can while (currentPoint.Item1 < radius) { currentPoint.Item1 +=1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move up while we can while (currentPoint.Item2 < -1) { currentPoint.Item2 += 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } } } 

O primeiro exemplo da questão (3x3) seria:

 var coords = SpiralCoords.GenerateOutTo(1); 

O segundo exemplo da pergunta (5x3) seria:

 var coords = SpiralCoords.GenerateOutTo(2).Where(x => abs(x.Item2) < 2); 

Esta é a minha solução muito ruim, feita a partir do conhecimento mínimo do Java. Aqui eu tenho que colocar unidades em um campo em uma espiral. As unidades não podem ser colocadas em cima de outras unidades ou em montanhas ou no oceano.

Para ser claro. Esta não é uma boa solução. Esta é uma solução muito ruim adicionada para a diversão de outras pessoas para rir de como isso pode ser ruim

 private void unitPlacementAlgorithm(Position p, Unit u){ int i = p.getRow(); int j = p.getColumn(); int iCounter = 1; int jCounter = 0; if (getUnitAt(p) == null) { unitMap.put(p, u); } else { iWhileLoop(i, j, iCounter, jCounter, -1, u); } } private void iWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u){ if(iCounter == 3) { for(int k = 0; k < 3; k++) { if(k == 2) { //This was added to make the looping stop after 9 units System.out.println("There is no more room around the city"); return; } i--; if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } iCounter--; } } while (iCounter > 0) { if (fortegn > 0) { i++; } else { i--; } if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } iCounter--; jCounter++; } fortegn *= -1; jWhileLoop(i, j, iCounter, jCounter, fortegn, u); } private void jWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u) { while (jCounter > 0) { if (fortegn > 0) { j++; } else { j--; } if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } jCounter--; iCounter++; if (jCounter == 0) { iCounter++; } } iWhileLoop(i, j, iCounter, jCounter, fortegn, u); } 

Cudos para quem pode realmente ler isso

Pergunta bônus: qual é o tempo de execução deste “algoritmo”? : P

Esta é uma versão ligeiramente diferente – tentando usar recursion e iterators no LUA. A cada passo, o programa desce mais dentro da matriz e faz um loop. Eu também adicionei uma bandeira extra para espiral clockwise anticlockwise clockwise ou anticlockwise . A saída começa nos cantos inferiores da direita e faz um loop recursivamente em direção ao centro.

 local row, col, clockwise local SpiralGen SpiralGen = function(loop) -- Generator of elements in one loop local startpos = { x = col - loop, y = row - loop } local IteratePosImpl = function() -- This function calculates returns the cur, next position in a loop. If called without check, it loops infinitely local nextpos = {x = startpos.x, y = startpos.y} local step = clockwise and {x = 0, y = -1} or { x = -1, y = 0 } return function() curpos = {x = nextpos.x, y = nextpos.y} nextpos.x = nextpos.x + step.x nextpos.y = nextpos.y + step.y if (((nextpos.x == loop or nextpos.x == col - loop + 1) and step.y == 0) or ((nextpos.y == loop or nextpos.y == row - loop + 1) and step.x == 0)) then --Hit a corner in the loop local tempstep = {x = step.x, y = step.y} step.x = clockwise and tempstep.y or -tempstep.y step.y = clockwise and -tempstep.x or tempstep.x -- retract next step with new step nextpos.x = curpos.x + step.x nextpos.y = curpos.y + step.y end return curpos, nextpos end end local IteratePos = IteratePosImpl() -- make an instance local curpos, nextpos = IteratePos() while (true) do if(nextpos.x == startpos.x and nextpos.y == startpos.y) then coroutine.yield(curpos) SpiralGen(loop+1) -- Go one step inner, since we're done with this loop break -- done with inner loop, get out else if(curpos.x < loop + 1 or curpos.x > col - loop or curpos.y < loop + 1 or curpos.y > row - loop) then break -- done with all elemnts, no place to loop further, break out of recursion else local curposL = {x = curpos.x, y = curpos.y} curpos, nextpos = IteratePos() coroutine.yield(curposL) end end end end local Spiral = function(rowP, colP, clockwiseP) row = rowP col = colP clockwise = clockwiseP return coroutine.wrap(function() SpiralGen(0) end) -- make a coroutine that returns all the values as an iterator end --test for pos in Spiral(10,2,true) do print (pos.y, pos.x) end for pos in Spiral(10,9,false) do print (pos.y, pos.x) end 

Python looping em espiral código no sentido horário usando Can Berk Güder resposta .

 def spiral(X, Y): x = y = 0 dx = 0 dy = 1 for i in range(max(X, Y)**2): if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2): print (x, y) # DO STUFF... if x == -y or (x < 0 and x == y) or (x > 0 and x-1 == y): dx, dy = dy, -dx x, y = x+dx, y+dy 

Isso é baseado em sua própria solução, mas podemos ser mais inteligentes em encontrar os cantos. Isso torna mais fácil ver como você pode pular as áreas externas se M e N forem muito diferentes.

 def spiral(X, Y): x = y = 0 dx = 0 dy = -1 s=0 ds=2 for i in range(max(X, Y)**2): if abs(x) <= X and abs(y) <= Y/2: print (x, y) # DO STUFF... if i==s: dx, dy = -dy, dx s, ds = s+ds/2, ds+1 x, y = x+dx, y+dy 

e uma solução baseada em gerador que é melhor que O (max (n, m) ^ 2), é O (nm + abs (nm) ^ 2) porque ela ignora tiras inteiras se elas não fizerem parte da solução.

 def spiral(X,Y): X = X+1>>1 Y = Y+1>>1 x = y = 0 d = side = 1 while x 
 Here is my attempt for simple C solution. First print the outer spiral and move one block inside..and repeat. #define ROWS 5 #define COLS 5 //int A[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {11, 12, 13, 14}, {15, 16, 17, 18} }; //int A[ROWS][COLS] = { {1, 2, 3}, {6, 7, 8}, { 12, 13, 14} }; //int A[ROWS][COLS] = { {1, 2}, {3, 4}}; int A[ROWS][COLS] = { {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} }; void print_spiral(int rows, int cols) { int row = 0; int offset = 0; while (offset < (ROWS - 1)) { /* print one outer loop at a time. */ for (int col = offset; col <= cols; col++) { printf("%d ", A[offset][col]); } for (row = offset + 1; row <= rows; row++) { printf("%d ", A[row][cols]); } for (int col = cols - 1; col >= offset; col--) { printf("%d ", A[rows][col]); } for (row = rows - 1; row >= offset + 1; row--) { printf("%d ", A[row][offset]); } /* Move one block inside */ offset++; rows--; cols--; } printf("\n"); } int _tmain(int argc, _TCHAR* argv[]) { print_spiral(ROWS-1, COLS-1); return 0; } 

Solução para AutoIt

 #include  #include  Func SpiralSearch($xMax,$yMax) $x = 0 $y = 0 $dx = 0 $dy = -1 for $i=0 To _max($xMax, $yMax)^2-1 Step 1 if -$xMax/2 < $x and $x <= $xMax/2 And -$yMax/2 < $y And $y <= $yMax/2 Then MsgBox(0, "We are here ", $x & " " & $y) EndIf if $x == $y or ($x < 0 and $x == -$y) or ($x > 0 and $x == 1-$y) Then _ArraySwap ($dx, $dy) $dx=-$dx EndIf $x += $dx $y += $dy Next EndFunc 

Recentemente, tive um desafio semelhante em que tive que criar um array 2D e usar um algoritmo de matriz espiral para classificar e imprimir os resultados. Este código C # funcionará com um array N, N 2D. É detalhado para maior clareza e pode ser reformulado para atender às suas necessidades.

 //CREATE A NEW MATRIX OF SIZE 4 ROWS BY 4 COLUMNS - SCALE MATRIX SIZE HERE SpiralMatrix SM = new SpiralMatrix(4, 4); string myData = SM.Read(); public class SpiralMatrix { //LETS BUILD A NEW MATRIX EVERY TIME WE INSTANTIATE OUR CLASS public SpiralMatrix(int Rows, int Cols) { Matrix = new String[Rows, Cols]; int pos = 1; for(int r = 0; r= 0 && Col < Matrix.GetLength(1) && Col >= 0) { //CHECK COORDINATE VALUE if (Matrix[Row, Col] != ConsumeChar) return true; else return false; } else { //WE ARE OUT OF BOUNDS return false; } } public string ConsumePos(int Row, int Col) { string n = Matrix[Row, Col]; Matrix[Row, Col] = ConsumeChar; return n; } public string ConsumeChar = "X"; public string[,] Matrix; } 

// Implementação PHP

 function spiral($n) { $r = intval((sqrt($n + 1) - 1) / 2) + 1; // compute radius : inverse arithmetic sum of 8+16+24+...= $p = (8 * $r * ($r - 1)) / 2; // compute total point on radius -1 : arithmetic sum of 8+16+24+... $en = $r * 2; // points by face $a = (1 + $n - $p) % ($r * 8); // compute de position and shift it so the first is (-r,-r) but (-r+1,-r) // so square can connect $pos = array(0, 0, $r); switch (intval($a / ($r * 2))) { // find the face : 0 top, 1 right, 2, bottom, 3 left case 0: $pos[0] = $a - $r; $pos[1] = -$r; break; case 1: $pos[0] = $r; $pos[1] = ($a % $en) - $r; break; case 2: $pos[0] = $r - ($a % $en); $pos[1] = $r; break; case 3: $pos[0] = -$r; $pos[1] = $r - ($a % $en); break; } return $pos; } for ($i = 0; $i < 168; $i++) { echo '
'; print_r(spiral($i)); echo '

'; }

Eu fiz este com um amigo que ajusta a espiral para a proporção de canvas em JavaScript. A melhor solução que obtive para uma evolução da imagem, pixel por pixel, preencheu toda a imagem.

Espero que ajude alguém.

 var width = 150; var height = 50; var x = -(width - height)/2; var y = 0; var dx = 1; var dy = 0; var x_limit = (width - height)/2; var y_limit = 0; var counter = 0; var canvas = document.getElementById("canvas"); var ctx = canvas.getContext('2d'); setInterval(function(){ if ((-width/2 < x && x <= width/2) && (-height/2 < y && y <= height/2)) { console.log("[ " + x + " , " + y + " ]"); ctx.fillStyle = "#FF0000"; ctx.fillRect(width/2 + x, height/2 - y,1,1); } if( dx > 0 ){//Dir right if(x > x_limit){ dx = 0; dy = 1; } } else if( dy > 0 ){ //Dir up if(y > y_limit){ dx = -1; dy = 0; } } else if(dx < 0){ //Dir left if(x < (-1 * x_limit)){ dx = 0; dy = -1; } } else if(dy < 0) { //Dir down if(y < (-1 * y_limit)){ dx = 1; dy = 0; x_limit += 1; y_limit += 1; } } counter += 1; //alert (counter); x += dx; y += dy; }, 1); 

Você pode vê-lo trabalhando em http://jsfiddle.net/hitbyatruck/c4Kd6/ . Apenas certifique-se de alterar a largura e a altura da canvas no javascript vars e nos atributos no HTML.

Eu tenho uma biblioteca de código aberto, pixelscan , que é uma biblioteca python que fornece funções para digitalizar pixels em uma grade em uma variedade de padrões espaciais. Padrões espaciais incluídos são circulares, anéis, grades, cobras e passeios randoms. Existem também várias transformações (por exemplo, clip, swap, rotate, translate). O problema OP original pode ser resolvido da seguinte forma

 for x, y in clip(swap(ringscan(0, 0, 0, 2)), miny=-1, maxy=1): print x, y 

que produz os pontos

 (0,0) (1,0) (1,1) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (2,0) (2,1) (-2,1) (-2,0) (-2,-1) (2,-1) 

As bibliotecas geradoras e transformações podem ser encadeadas para alterar os pontos em uma ampla variedade de ordens e padrões espaciais.

Apenas por diversão em Javascript:

 function spiral(x, y) { var iy = ix = 0 , hr = (x - 1) / 2 , vr = (y - 1) / 2 , tt = x * y , matrix = [] , step = 1 , dx = 1 , dy = 0; while(matrix.length < tt) { if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) { console.log(ix, iy); matrix.push([ix, iy]); } ix += dx; iy += dy; // check direction if(dx !== 0) { // increase step if(ix === step && iy === (step * -1)) step++; // horizontal range reached if(ix === step || (ix === step * -1)) { dy = (ix === iy)? (dx * -1) : dx; dx = 0; } } else { // vertical range reached if(iy === step || (iy === step * -1)) { dx = (ix === iy)? (dy * -1) : dy; dy = 0; } } } return matrix; } var sp = spiral(5, 3); 

Versão c #, lida com tamanhos não quadrados também.

 private static Point[] TraverseSpiral(int width, int height) { int numElements = width * height + 1; Point[] points = new Point[numElements]; int x = 0; int y = 0; int dx = 1; int dy = 0; int xLimit = width - 0; int yLimit = height - 1; int counter = 0; int currentLength = 1; while (counter < numElements) { points[counter] = new Point(x, y); x += dx; y += dy; currentLength++; if (dx > 0) { if (currentLength >= xLimit) { dx = 0; dy = 1; xLimit--; currentLength = 0; } } else if (dy > 0) { if (currentLength >= yLimit) { dx = -1; dy = 0; yLimit--; currentLength = 0; } } else if (dx < 0) { if (currentLength >= xLimit) { dx = 0; dy = -1; xLimit--; currentLength = 0; } } else if (dy < 0) { if (currentLength >= yLimit) { dx = 1; dy = 0; yLimit--; currentLength = 0; } } counter++; } Array.Reverse(points); return points; } 

I am sharing this code which I designed for a different purpose; it is about finding the Column number “X”, and the row number “Y” of array element @ spiral index “index”. This function takes the width “w” and height “h” of the matrix, and the required “index”. Of course, this function can be used to produce the same required output. I think it is the fastest possible method (as it jumps over cells instead of scanning them).

  rec BuildSpiralIndex(long w, long h, long index = -1) { long count = 0 , x = -1, y = -1, dir = 1, phase=0, pos = 0, length = 0, totallength = 0; bool isVertical = false; if(index>=(w*h)) return null; do { isVertical = (count % 2) != 0; length = (isVertical ? h : w) - count/2 - count%2 ; totallength += length; count++; } while(totallength 1 ? phase : w - phase); y = ((pos == 1 || pos == 2) ? h - phase : phase) + (1 * (pos == 3 ? 1 : 0)); dir = pos > 1 ? -1 : 1; if (isVertical) y -= (totallength - index - 1) * dir; else x -= (totallength - index -1) * dir; return new rec { X = x, Y = y }; } 

Here’s a JavaScript (ES6) iterative solution to this problem:

 let spiralMatrix = (x, y, step, count) => { let distance = 0; let range = 1; let direction = 'up'; for ( let i = 0; i < count; i++ ) { console.log('x: '+x+', y: '+y); distance++; switch ( direction ) { case 'up': y += step; if ( distance >= range ) { direction = 'right'; distance = 0; } break; case 'right': x += step; if ( distance >= range ) { direction = 'bottom'; distance = 0; range += 1; } break; case 'bottom': y -= step; if ( distance >= range ) { direction = 'left'; distance = 0; } break; case 'left': x -= step; if ( distance >= range ) { direction = 'up'; distance = 0; range += 1; } break; default: break; } } } 

Veja como usá-lo:

spiralMatrix(0, 0, 1, 100);

This will create an outward spiral, starting at coordinates (x = 0, y = 0) with step of 1 and a total number of items equals to 100. The implementation always starts the movement in the following order – up, right, bottom, left.

Please, note that this implementation creates square matrices.

Davidont’s excellent solution in VB.Net

  Public Function Spiral(n As Integer) As RowCol ' given n an index in the squared spiral ' p the sum of point in inner square ' a the position on the current square ' n = p + a ' starts with row 0 col -1 Dim r As Integer = CInt(Math.Floor((Math.Sqrt(n + 1) - 1) / 2) + 1) ' compute radius : inverse arithmetic sum of 8+16+24+...= Dim p As Integer = (8 * r * (r - 1)) \ 2 ' compute total point on radius -1 : arithmetic sum of 8+16+24+... Dim en As Integer = r * 2 ' points by face Dim a As Integer = (1 + n - p) Mod (r * 8) ' compute the position and shift it so the first is (-r,-r) but (-r+1,-r) ' so square can connect Dim row As Integer Dim col As Integer Select Case Math.Floor(a \ (r * 2)) ' find the face : 0 top, 1 right, 2, bottom, 3 left Case 0 row = a - r col = -r Case 1 row = r col = (a Mod en) - r Case 2 row = r - (a Mod en) col = r Case 3 row = -r col = r - (a Mod en) End Select Return New RowCol(row, col) End Function 

Here’s an answer in Julia: my approach is to assign the points in concentric squares (‘spirals’) around the origin (0,0) , where each square has side length m = 2n + 1 , to produce an ordered dictionary with location numbers (starting from 1 for the origin) as keys and the corresponding coordinate as value.

Since the maximum location per spiral is at (n,-n) , the rest of the points can be found by simply working backward from this point, ie from the bottom right corner by m-1 units, then repeating for the perpendicular 3 segments of m-1 units.

This process is written in reverse order below, corresponding to how the spiral proceeds rather than this reverse counting process, ie the ra [right ascending] segment is decremented by 3(m+1) , then la [left ascending] by 2(m+1) , and so on – hopefully this is self-explanatory.

 import DataStructures: OrderedDict, merge function spiral(loc::Int) s = sqrt(loc-1) |> floor |> Int if s % 2 == 0 s -= 1 end s = (s+1)/2 |> Int return s end function perimeter(n::Int) n > 0 || return OrderedDict([1,[0,0]]) m = 2n + 1 # width/height of the spiral [square] indexed by n # loc_max = m^2 # loc_min = (2n-1)^2 + 1 ra = [[m^2-(y+3m-3), [n,ny]] for y in (m-2):-1:0] la = [[m^2-(y+2m-2), [yn,n]] for y in (m-2):-1:0] ld = [[m^2-(y+m-1), [-n,yn]] for y in (m-2):-1:0] rd = [[m^2-y, [ny,-n]] for y in (m-2):-1:0] return OrderedDict(vcat(ra,la,ld,rd)) end function walk(n) cds = OrderedDict(1 => [0,0]) n > 0 || return cds for i in 1:n cds = merge(cds, perimeter(i)) end return cds end 

So for your first example, plugging m = 3 into the equation to find n gives n = (5-1)/2 = 2 , and walk(2) gives an ordered dictionary of locations to coordinates, which you can turn into just an array of coordinates by accessing the dictionary’s vals field:

 walk(2) DataStructures.OrderedDict{Any,Any} with 25 entries: 1 => [0,0] 2 => [1,0] 3 => [1,1] 4 => [0,1] ⋮ => ⋮ [(co[1],co[2]) for co in walk(2).vals] 25-element Array{Tuple{Int64,Int64},1}: (0,0) (1,0) ⋮ (1,-2) (2,-2) 

Note that for some functions [eg norm ] it can be preferable to leave the coordinates in arrays rather than Tuple{Int,Int} , but here I change them into tuples— (x,y) —as requested, using list comprehension.

The context for “supporting” a non-square matrix isn’t specified (note that this solution still calculates the off-grid values), but if you want to filter to only the range x by y (here for x=5 , y=3 ) after calculating the full spiral then intersect this matrix against the values from walk .

 grid = [[x,y] for x in -2:2, y in -1:1] 5×3 Array{Array{Int64,1},2}: [-2,-1] [-2,0] [-2,1] ⋮ ⋮ ⋮ [2,-1] [2,0] [2,1] [(co[1],co[2]) for co in intersect(walk(2).vals, grid)] 15-element Array{Tuple{Int64,Int64},1}: (0,0) (1,0) ⋮ (-2,0) (-2,-1) 

This is my approach for a square spiral in c#, i made this some time ago, i just thought i could add it, since it’s different from all the others, not the best, but just a different way, i am sure it can be adapted for a non-square too.

This approach i take the max number of steps in, instead of the max vector tho.

The main thing about this approach is the corners, there’s some adjustments for the first step and the “progress” step needed to go out of the “corner” in the right bottom corner.

 private void Spiral(int sequence) { const int x = 0; const int y = 1; int[,] matrix = new int[2, sequence]; int dirX, dirY, prevX, prevY, curr; dirX = dirY = prevX = prevY = curr = default(int); do { if (curr > 0) { prevX = matrix[x, curr - 1]; prevY = matrix[y, curr - 1]; } //Change direction based on the corner. if (Math.Abs(prevX) == Math.Abs(prevY) && curr > 0) { dirX = dirY = 0; if (prevY > 0 && prevX > 0) dirX = -1; else if (prevY > 0 && prevX < 0) dirY = -1; else if (prevY < 0 && prevX < 0) dirX = 1; else if (prevY < 0 && prevX > 0) //Move forward dirX = 1; else if (prevY == 0 && prevX == 0) //For the first step. dirX = 1; } else if (prevY < 0 && prevX > 0 && (Math.Abs(matrix[x, curr - 2]) == Math.Abs(matrix[y, curr - 2]))) //Move forward { dirX = 0; dirY = 1; } else if (prevX == 1 && prevY == 0) //For the second step. { dirY = 1; dirX = 0; } matrix[x, curr] = prevX + dirX; matrix[y, curr] = prevY + dirY; System.Console.Write($"({matrix[x, curr]},{matrix[y, curr]}) "); } while (++curr < sequence); } 

Here’s a solution in Python 3 for printing consecutive integers in a spiral clockwise and counterclockwise.

 import math def sp(n): # spiral clockwise a=[[0 for x in range(n)] for y in range(n)] last=1 for k in range(n//2+1): for j in range(k,nk): a[k][j]=last last+=1 for i in range(k+1,nk): a[i][j]=last last+=1 for j in range(nk-2,k-1,-1): a[i][j]=last last+=1 for i in range(nk-2,k,-1): a[i][j]=last last+=1 s=int(math.log(n*n,10))+2 # compute size of cell for printing form="{:"+str(s)+"}" for i in range(n): for j in range(n): print(form.format(a[i][j]),end="") print("") sp(3) # 1 2 3 # 8 9 4 # 7 6 5 sp(4) # 1 2 3 4 # 12 13 14 5 # 11 16 15 6 # 10 9 8 7 def sp_cc(n): # counterclockwise a=[[0 for x in range(n)] for y in range(n)] last=1 for k in range(n//2+1): for j in range(nk-1,k-1,-1): a[nk-1][j]=last last+=1 for i in range(nk-2,k-1,-1): a[i][j]=last last+=1 for j in range(k+1,nk): a[i][j]=last last+=1 for i in range(k+1,nk-1): a[i][j]=last last+=1 s=int(math.log(n*n,10))+2 # compute size of cell for printing form="{:"+str(s)+"}" for i in range(n): for j in range(n): print(form.format(a[i][j]),end="") print("") sp_cc(5) # 9 10 11 12 13 # 8 21 22 23 14 # 7 20 25 24 15 # 6 19 18 17 16 # 5 4 3 2 1 

Explicação

A spiral is made of concentric squares, for instance a 5×5 square with clockwise rotation looks like this:

  5x5 3x3 1x1 >>>>> ^ v >>> ^ v + ^ v + > ^ v <<< <<< 

( >>>>> means "go 5 times right" or increase column index 5 times, v means down or increase row index, etc.)

All squares are the same up to their size, I looped over the concentric squares.

For each square the code has four loops (one for each side), in each loop we increase or decrease the columns or row index. If i is the row index and j the column index then a 5x5 square can be constructed by: - incrementing j from 0 to 4 (5 times) - incrementing i from 1 to 4 (4 times) - decrementing j from 3 to 0 (4 times) - decrementing i from 3 to 1 (3 times)

For the next squares (3x3 and 1x1) we do the same but shift the initial and final indices appropriately. I used an index k for each concentric square, there are n//2 + 1 concentric squares.

Finally, some math for pretty-printing.

To print the indexes:

 def spi_cc(n): # counter-clockwise a=[[0 for x in range(n)] for y in range(n)] ind=[] last=n*n for k in range(n//2+1): for j in range(nk-1,k-1,-1): ind.append((nk-1,j)) for i in range(nk-2,k-1,-1): ind.append((i,j)) for j in range(k+1,nk): ind.append((i,j)) for i in range(k+1,nk-1): ind.append((i,j)) print(ind) spi_cc(5)