sharelatex loop else algoritmos algoritmo algorithmic algorithm matrix loops spiral

algorithm - else - Looping en espiral



loop latex (30)

Un amigo necesitaba un algoritmo que le permitiera recorrer los elementos de una matriz NxM (N y M son impares). Se me ocurrió una solución, pero quería ver si mis compañeros So''ers podían encontrar una solución mejor.

Estoy publicando mi solución como una respuesta a esta pregunta.

Ejemplo de salida:

Para una matriz de 3x3, la salida debería ser:

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

Además, el algoritmo debería admitir matrices no cuadradas, por lo que, por ejemplo, para una matriz de 5x3, la salida debería 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)


// Implementación de 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 ''<pre>''; print_r(spiral($i)); echo ''</pre>''; }


Amo los generadores 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

Prueba con:

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

Usted obtiene:

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)


Aquí está c #, linq''ish.

public static class SpiralCoords { public static IEnumerable<Tuple<int, int>> GenerateOutTo(int radius) { //TODO trap negative radius. 0 is ok. foreach(int r in Enumerable.Range(0, radius + 1)) { foreach(Tuple<int, int> coord in GenerateRing(r)) { yield return coord; } } } public static IEnumerable<Tuple<int, int>> GenerateRing(int radius) { //TODO trap negative radius. 0 is ok. Tuple<int, int> 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); } } }

El primer ejemplo de la pregunta (3x3) sería:

var coords = SpiralCoords.GenerateOutTo(1);

El segundo ejemplo de la pregunta (5x3) sería:

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


Aquí está mi solución (En 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})," }


Aquí está mi solución (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


Aquí hay una solución O (1) para encontrar la posición en una espiral cuadrada: 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; }


Aquí hay una solución de C ++ que muestra que puede calcular las siguientes (x, y) coordenadas de manera directa y sencilla de las anteriores, sin necesidad de seguir la dirección actual, el radio o cualquier otra cosa:

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 todo lo que intenta hacer es generar los primeros N puntos en la espiral (sin la restricción del problema original de enmascarar a una región N x M), el código se vuelve muy 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); } }

El truco es que puedes comparar xey para determinar en qué lado del cuadrado estás, y eso te dice en qué dirección debes moverte.


C ++ alguien? Traducción rápida de python, publicada para completar

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


Esta es mi muy mala solución, hecha del mínimo conocimiento de Java. Aquí tengo que colocar unidades en un campo en espiral. Las unidades no se pueden colocar encima de otras unidades o en montañas o en el océano.

Para ser claro. Esta no es una buena solución. Esta es una solución muy mala añadida para la diversión de otras personas a reírse de lo malo que se puede hacer

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 a cualquiera que pueda leer esto

Pregunta de bonificación: ¿Cuál es el tiempo de ejecución de este "algoritmo"? :PAG


Esta es una versión ligeramente diferente: trata de usar recursion e iterators en LUA. En cada paso, el programa desciende más dentro de la matriz y gira. También agregué una bandera extra para girar en clockwise o anticlockwise . La salida comienza desde las esquinas inferiores derechas y gira repetidamente hacia el 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


Esto está en C.

Casualmente elegí malos nombres de variables. En los nombres T == top, L == left, B == bottom, R == right. Entonces, tli está arriba a la izquierda iy brj está abajo a la derecha j.

#include<stdio.h> 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]); } }


Esto se basa en su propia solución, pero podemos ser más inteligentes para encontrar las esquinas. Esto hace que sea más fácil ver cómo puede omitir las áreas externas si M y N son muy 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

y una solución basada en generador que es mejor que O (max (n, m) ^ 2), es O (nm + abs (nm) ^ 2) porque omite bandas completas si no son parte de la solución.

def spiral(X,Y): X = X+1>>1 Y = Y+1>>1 x = y = 0 d = side = 1 while x<X or y<Y: if abs(y)<Y: for x in range(x, x+side, d): if abs(x)<X: yield x,y x += d else: x += side if abs(x)<X: for y in range(y, y+side, d): if abs(y)<Y: yield x,y y += d else: y += side d =-d side = d-side


Haskell, elige:

spiral x y = (0, 0) : concatMap ring [1 .. max x'' y''] where ring n | n > x'' = left x'' n ++ right x'' (-n) ring n | n > y'' = up n y'' ++ down (-n) y'' ring n = up n n ++ left n n ++ down n n ++ right n n up x y = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up right x y = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right (x'', y'') = (x `div` 2, y `div` 2) spiral x y = 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 x y] ]


Hice este con un amigo que ajusta la relación de aspecto de la espiral a la lona en Javascript. La mejor solución que obtuve para una evolución de imagen píxel por píxel, llenando toda la imagen.

Espero que ayude a alguien.

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

Puedes verlo trabajando en http://jsfiddle.net/hitbyatruck/c4Kd6/ . Solo asegúrate de cambiar el ancho y alto del lienzo en javascript vars y en los atributos en el HTML.


Intento en espiral de Java "Code golf", basado en 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; } }


Python con un código espiral en el sentido de las agujas del reloj usando la respuesta 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


Recientemente tuve un desafío similar en el que tuve que crear una matriz 2D y usar un algoritmo de matriz en espiral para ordenar e imprimir los resultados. Este código C # funcionará con una matriz N, N 2D. Es detallado para mayor claridad y puede ser re-factorizado para satisfacer sus necesidades.

//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<Rows; r++){ for (int c = 0; c < Cols; c++) { //POPULATE THE MATRIX WITH THE CORRECT ROW,COL COORDINATE Matrix[r, c] = pos.ToString(); pos++; } } } //READ MATRIX public string Read() { int Row = 0; int Col = 0; string S = ""; bool isDone = false; //CHECK tO SEE IF POSITION ZERO IS AVAILABLE if(PosAvailable(Row, Col)){ S = ConsumePos(Row, Col); } //START READING SPIRAL //THIS BLOCK READS A FULL CYCLE OF RIGHT,DOWN,LEFT,UP EVERY ITERATION while(!isDone) { bool goNext = false; //READ ALL RIGHT SPACES ON THIS PATH PROGRESSION while (PosAvailable(Row, Col+1)) { //Is ReadRight Avail Col++; S += ConsumePos(Row, Col); goNext = true; } //READ ALL DOWN SPACES ON THIS PATH PROGRESSION while(PosAvailable(Row+1, Col)){ //Is ReadDown Avail Row++; S += ConsumePos(Row, Col); goNext = true; } //READ ALL LEFT SPACES ON THIS PATH PROGRESSION while(PosAvailable(Row, Col-1)){ //Is ReadLeft Avail Col--; S += ConsumePos(Row, Col); goNext = true; } //READ ALL UP SPACES ON THIS PATH PROGRESSION while(PosAvailable(Row-1, Col)){ //Is ReadUp Avail Row--; S += ConsumePos(Row, Col); goNext = true; } if(!goNext){ //DONE - SET EXIT LOOP FLAG isDone = true; } } return S; } //DETERMINE IF THE POSITION IS AVAILABLE public bool PosAvailable(int Row, int Col) { //MAKE SURE WE ARE WITHIN THE BOUNDS OF THE ARRAY if (Row < Matrix.GetLength(0) && Row >= 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; }


Solución para AutoIt

#include <Math.au3> #include <Array.au3> 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


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 String strung(List<Point> 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<Point> list = new ArrayList<Point>(); public Spiral(int width, int height) { this.width = width; this.height = height; } public List<Point> 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, p.x) && between(-height / 2, height / 2, p.y); } private static boolean between(int low, int high, int n) { return low <= n && n <= high; } }


Tengo una biblioteca de código abierto, pixelscan , que es una biblioteca de Python que proporciona funciones para escanear píxeles en una grilla en una variedad de patrones espaciales. Los patrones espaciales incluidos son circulares, anillos, cuadrículas, serpientes y paseos aleatorios. También hay varias transformaciones (por ejemplo, clip, swap, rotar, traducir). El problema OP original se puede resolver de la siguiente manera

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

que cede los puntos

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

Los generadores y las transformaciones de las bibliotecas se pueden encadenar para cambiar los puntos en una amplia variedad de órdenes y patrones espaciales.


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


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

Here''s how to use it:

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.


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,n-k): a[k][j]=last last+=1 for i in range(k+1,n-k): a[i][j]=last last+=1 for j in range(n-k-2,k-1,-1): a[i][j]=last last+=1 for i in range(n-k-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(n-k-1,k-1,-1): a[n-k-1][j]=last last+=1 for i in range(n-k-2,k-1,-1): a[i][j]=last last+=1 for j in range(k+1,n-k): a[i][j]=last last+=1 for i in range(k+1,n-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_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

Explanation

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

5x5 3x3 1x1 >>>>> ^ v >>> ^ 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(n-k-1,k-1,-1): ind.append((n-k-1,j)) for i in range(n-k-2,k-1,-1): ind.append((i,j)) for j in range(k+1,n-k): ind.append((i,j)) for i in range(k+1,n-k-1): ind.append((i,j)) print(ind) spi_cc(5)


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,n-y]] for y in (m-2):-1:0] la = [[m^2-(y+2m-2), [y-n,n]] for y in (m-2):-1:0] ld = [[m^2-(y+m-1), [-n,y-n]] for y in (m-2):-1:0] rd = [[m^2-y, [n-y,-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)


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<index); count--; w--; h--; phase = (count / 4); pos = (count%4); x = (pos > 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 }; }


Just for fun in 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);


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


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

Se han presentado muchas soluciones propuestas para este problema en varios lenguajes de programación, sin embargo, todas parecen derivarse del mismo enfoque intrincado. Voy a considerar el problema más general de computar una espiral que puede expresarse de manera concisa mediante la inducción.

Caso base: comience en (0, 0), avance 1 casilla, gire a la izquierda, avance 1 casilla, gire a la izquierda. Paso inductivo: avanza n + 1 cuadrados, gira a la izquierda, avanza n + 1 cuadrados, gira a la izquierda.

La elegancia matemática de expresar este problema sugiere fuertemente que debería haber un algoritmo simple para calcular la solución. Teniendo en cuenta la abstracción, he decidido no implementar el algoritmo en un lenguaje de programación específico sino más bien como un pseudocódigo.

Primero consideraré un algoritmo para calcular solo 2 iteraciones de la espiral usando 4 pares de ciclos while. La estructura de cada par es similar, pero distinta por derecho propio. Esto puede parecer una locura al principio (algunos loops solo se ejecutan una vez) pero paso a paso voy a hacer transformaciones hasta llegar a 4 pares de loops que son idénticos y, por lo tanto, pueden ser reemplazados por un solo par colocado dentro de otro ciclo. Esto nos proporcionará una solución general de n iteraciones informáticas sin utilizar ninguna condición.

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 primera transformación que haremos será la introducción de una nueva variable d, para dirección, que contenga el valor +1 o -1. La dirección cambia después de cada par de bucles. Como conocemos el valor de d en todos los puntos, podemos multiplicar cada lado de cada desigualdad por él, ajustar la dirección de la desigualdad en consecuencia y simplificar cualquier multiplicación de d por una constante a otra constante. Esto nos deja con lo siguiente.

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

Ahora notamos que tanto x * dy el RHS son enteros, por lo que podemos restar cualquier valor real entre 0 y 1 del RHS sin afectar el resultado de la desigualdad. Optamos por restar 0.5 de las desigualdades de cada otro par de ciclos while para establecer más de un patrón.

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

Ahora podemos introducir otra variable m para la cantidad de pasos que tomamos en cada par de ciclos 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 la estructura de cada par de bucles while es idéntica y se puede reducir a un bucle único colocado dentro de otro bucle. Además, para evitar el uso de números reales, he multiplicado el valor inicial de m; el valor m se incrementa por; y ambos lados de cada desigualdad por 2.

Esto lleva a la solución que se muestra al comienzo de esta respuesta.