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.