En boucle dans une spirale

Un ami avait besoin d’un algorithme lui permettant de parcourir les éléments d’une masortingce NxM (N et M sont impairs). Je suis venu avec une solution, mais je voulais voir si mes collègues pouvaient trouver une meilleure solution.

Je poste ma solution en réponse à cette question.

Exemple de sortie:

Pour une masortingce 3×3, le résultat devrait être:

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

Matrice 3x3

De plus, l’algorithme devrait prendre en charge les masortingces non carrées, par exemple pour une masortingce 5×3, le résultat devrait être:

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

Matrice 5x3

Voici ma solution (en 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 ++ quelqu’un? Traduction rapide de python, publié pour être complet

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

J’adore les générateurs 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 

Test avec:

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

Vous obtenez:

 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) 

Voici une solution O (1) pour trouver la position dans une spirale carrée: 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 

Beaucoup de solutions proposées pour ce problème ont été écrites dans divers langages de programmation, mais elles semblent toutes provenir de la même approche compliquée. Je vais considérer le problème plus général du calcul d'une spirale qui peut être exprimé de manière concise en utilisant l'induction.

Cas de base: Commencez à (0, 0), avancez d'un carré, tournez à gauche, avancez d'un carré, tournez à gauche. Pas inductif: Avancer n + 1 carrés, tourner à gauche, avancer n + 1 carrés, tourner à gauche.

L'élégance mathématique de l'expression de ce problème suggère fortement qu'il devrait y avoir un algorithme simple pour calculer la solution. En gardant à l'esprit l'abstraction, j'ai choisi de ne pas implémenter l'algorithme dans un langage de programmation spécifique, mais plutôt en tant que pseudo-code.

Tout d'abord, je considérerai un algorithme pour calculer seulement 2 itérations de la spirale en utilisant 4 paires de boucles while. La structure de chaque paire est similaire mais distincte. Cela peut sembler fou au début (certaines boucles ne sont exécutées qu'une seule fois) mais pas à pas, je vais faire des transformations jusqu'à ce que nous arrivions à 4 paires de boucles identiques et donc remplaçables par une seule paire placée dans une autre boucle. Cela nous fournira une solution générale pour calculer n itérations sans utiliser de conditionnel.

 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 

La première transformation que nous allons faire est l'introduction d'une nouvelle variable d, pour la direction, qui contient la valeur +1 ou -1. La direction change après chaque paire de boucles. Puisque nous connaissons la valeur de d en tout point, nous pouvons multiplier chaque côté de chaque inégalité par elle, ajuster la direction de l'inégalité en conséquence et simplifier toute multiplication de d par une constante à une autre constante. Cela nous laisse avec ce qui suit.

 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 

Nous notons maintenant que x * d et le RHS sont des nombres entiers, de sorte que nous pouvons soustraire toute valeur réelle entre 0 et 1 du RHS sans affecter le résultat de l'inégalité. Nous choisissons de soustraire 0,5 aux inégalités de chaque autre paire de boucles while afin d'établir plus d'un motif.

 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 

Nous pouvons maintenant introduire une autre variable m pour le nombre de pas que nous prenons à chaque paire de boucles 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 

Enfin, on constate que la structure de chaque paire de boucles while est identique et peut être réduite à une seule boucle placée dans une autre boucle. En outre, pour éviter d'utiliser des nombres réels, j'ai multiplié la valeur initiale de m; la valeur m est incrémentée de; et les deux côtés de chaque inégalité par 2.

Cela conduit à la solution présentée au début de cette réponse.

Spirale Java “Code golf” tentative, basée sur la 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; } } 

Voici une solution C ++ qui montre que vous pouvez calculer les prochaines coordonnées (x, y) directement et facilement à partir des précédentes – pas besoin de suivre la direction, le rayon ou toute autre chose:

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

Si tout ce que vous essayez de faire est de générer les N premiers points de la spirale (sans la contrainte de masquage du problème d’origine dans une région N x M), le code devient très simple:

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

L’astuce est que vous pouvez comparer x et y pour déterminer quel côté de la case vous êtes et cela vous indique dans quelle direction aller.

Voici ma solution (In 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, en 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 Ssortingng strung(List points) { SsortingngBuffer sb = new SsortingngBuffer(); for (Point point : points) sb.append(strung(point)); return sb.toSsortingng().sortingm(); } private Ssortingng strung(Point point) { return Ssortingng.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, faites votre choix:

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

Ceci est en C.

J’ai choisi des mauvais noms de variables. Dans les noms T == top, L == left, B == bottom, R == right. Donc, tli est en haut à gauche i et brj est en bas à droite 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]); } } 

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

Le premier exemple de la question (3x3) serait:

 var coords = SpiralCoords.GenerateOutTo(1); 

Le deuxième exemple de la question (5x3) serait:

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

C’est ma très mauvaise solution, faite de la connaissance minimale de Java. Ici, je dois placer des unités sur un champ en spirale. Les unités ne peuvent pas être placées sur d’autres unités ou sur des montagnes ou dans l’océan.

Pour être clair. Ce n’est pas une bonne solution. Ceci est une très mauvaise solution ajoutée pour le plaisir des autres à rire à quel point cela peut être fait

 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)).getTypeSsortingng().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeSsortingng().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)).getTypeSsortingng().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeSsortingng().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 à quiconque peut réellement lire ceci

Question bonus: Quel est le temps d’exécution de cet “algorithme”? : P

C’est une version légèrement différente – en essayant d’utiliser la recursion et les iterators dans LUA. A chaque étape, le programme descend plus loin dans la masortingce et les boucles. J’ai également ajouté un drapeau supplémentaire en spirale ou en anticlockwise des clockwise anticlockwise . La sortie commence à partir des coins en bas à droite et des boucles récursives vers le centre.

 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 en boucle dans le sens des aiguilles d’une montre à l’aide de Can Berk Güder .

 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 

Ceci est basé sur votre propre solution, mais nous pouvons être plus intelligents pour trouver les coins. Cela facilite la lecture des zones extérieures si M et N sont très différents.

 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 

et une solution basée sur un générateur qui est meilleure que O (max (n, m) ^ 2), C’est O (nm + abs (nm) ^ 2) parce qu’elle saute des bandes entières si elles ne font pas partie de la solution.

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

Solution pour 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 

J’ai récemment eu un défi similaire où j’ai dû créer un tableau 2D et utiliser un algorithme de masortingce en spirale pour sortinger et imprimer les résultats. Ce code C # fonctionnera avec un tableau N, N 2D. Il est détaillé pour plus de clarté et peut probablement être modifié pour répondre à vos besoins.

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

// Implémentation 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 '

'; }

J’ai fait celui-ci avec un ami qui ajuste la spirale au format de la canvas sur Javascript. Meilleure solution que j’ai eu pour une évolution d’image pixel par pixel, remplissant toute l’image.

J’espère que ça aide quelqu’un.

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

Vous pouvez le voir fonctionner sur http://jsfiddle.net/hitbyatruck/c4Kd6/ . Veillez simplement à modifier la largeur et la hauteur du canevas sur les vars javascript et sur les atsortingbuts du code HTML.

J’ai une bibliothèque open source, pixelscan , qui est une bibliothèque Python qui fournit des fonctions pour parsingr les pixels sur une grid dans une variété de motifs spatiaux. Les schémas spatiaux inclus sont circulaires, anneaux, grids, serpents et marches aléatoires. Il existe également diverses transformations (p. Ex., Clip, swap, rotation, translation). Le problème OP initial peut être résolu comme suit

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

qui donne les points

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

Les générateurs et les transformations des bibliothèques peuvent être enchaînés pour modifier les points dans une grande variété d’ordres et de modèles spatiaux.

Juste pour le fun en Javascript:

 function spiral(x, y) { var iy = ix = 0 , hr = (x - 1) / 2 , vr = (y - 1) / 2 , tt = x * y , masortingx = [] , step = 1 , dx = 1 , dy = 0; while(masortingx.length < tt) { if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) { console.log(ix, iy); masortingx.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 masortingx; } var sp = spiral(5, 3); 

C# version, handles non-square sizes as well.

 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 masortingx, 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 spiralMasortingx = (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; } } } 

Voici comment l’utiliser:

spiralMasortingx(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 masortingces.

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 concensortingc 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 ensortinges: 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 masortingx 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 masortingx 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[,] masortingx = new int[2, sequence]; int dirX, dirY, prevX, prevY, curr; dirX = dirY = prevX = prevY = curr = default(int); do { if (curr > 0) { prevX = masortingx[x, curr - 1]; prevY = masortingx[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(masortingx[x, curr - 2]) == Math.Abs(masortingx[y, curr - 2]))) //Move forward { dirX = 0; dirY = 1; } else if (prevX == 1 && prevY == 0) //For the second step. { dirY = 1; dirX = 0; } masortingx[x, curr] = prevX + dirX; masortingx[y, curr] = prevY + dirY; System.Console.Write($"({masortingx[x, curr]},{masortingx[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 

Explication

A spiral is made of concensortingc 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 concensortingc 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 concensortingc square, there are n//2 + 1 concensortingc 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)