Цикл по спирали
Другу нужен был алгоритм, который позволял бы ему проходить по элементам матрицы NxM (N и M нечетные). Я придумал решение, но я хотел посмотреть, смогут ли мои коллеги-SO предложить лучшее решение.
Я публикую свое решение в качестве ответа на этот вопрос.
Пример вывода:
Для матрицы 3х3 вывод должен быть:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)
Кроме того, алгоритм должен поддерживать неквадратные матрицы, поэтому, например, для матрицы 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)
35 ответов
Вот мое решение (на 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++ кто-нибудь? Быстрый перевод с питона, выложен для полноты
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;
}
}
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
Было предложено много решений этой проблемы, написанных на разных языках программирования, но все они, похоже, основаны на одном и том же замысловатом подходе. Я собираюсь рассмотреть более общую проблему вычисления спирали, которую можно выразить кратко, используя индукцию.
Базовый случай: начать с (0, 0), двигаться вперед на 1 квадрат, повернуть налево, двигаться вперед на 1 квадрат, повернуть влево. Индуктивный шаг: двигаться вперед n+1 на квадраты, повернуть налево, двигаться вперед на n+1 квадрат, повернуть налево.
Математическая элегантность выражения этой проблемы настоятельно предполагает, что должен быть простой алгоритм для вычисления решения. Имея в виду абстракцию, я выбрал не реализацию алгоритма на конкретном языке программирования, а псевдокод.
Сначала рассмотрим алгоритм для вычисления всего 2 итераций спирали с использованием 4 пар циклов while. Структура каждой пары похожа, но сама по себе отлична. Поначалу это может показаться сумасшедшим (некоторые циклы выполняются только один раз), но шаг за шагом я буду выполнять преобразования, пока мы не получим 4 пары циклов, которые идентичны и, следовательно, могут быть заменены одной парой, размещенной внутри другого цикла. Это даст нам общее решение для вычисления 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
Первое преобразование, которое мы сделаем, - это введение новой переменной d для direction, которая содержит значение +1 или -1. Направление переключается после каждой пары петель. Поскольку мы знаем значение d во всех точках, мы можем умножить на него каждую сторону каждого неравенства, соответствующим образом скорректировать направление неравенства и упростить любые умножения d на постоянную до другой константы. Это оставляет нас со следующим.
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
Теперь отметим, что и x * d, и RHS являются целыми числами, поэтому мы можем вычесть из RHS любое действительное значение в диапазоне от 0 до 1, не влияя на результат неравенства. Мы выбираем вычитать 0.5 из неравенств любой другой пары циклов while, чтобы получить больше паттернов.
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
Теперь мы можем ввести другую переменную m для количества шагов, которые мы предпринимаем в каждой паре циклов 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
Наконец, мы видим, что структура каждой пары циклов while идентична и может быть сведена к одному циклу, помещенному внутри другого цикла. Кроме того, чтобы избежать использования вещественных чисел, я умножил начальное значение m; значение m увеличивается на; и обе стороны каждого неравенства по 2.
Это приводит к решению, показанному в начале этого ответа.
Вот решение O(1), чтобы найти положение в квадрате спирали: Скрипка
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;
}
Я люблю генераторы 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
Тестирование с:
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),
Ты получаешь:
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)
Вот решение C++, которое показывает, что вы можете легко и просто рассчитать следующие (x, y) координаты из предыдущих - не нужно отслеживать текущее направление, радиус или что-либо еще:
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);
}
}
Если все, что вы пытаетесь сделать, это сгенерировать первые N точек на спирали (без ограничения маскирования исходной задачи на область N x M), код становится очень простым:
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);
}
}
Хитрость в том, что вы можете сравнить x и y, чтобы определить, на какой стороне квадрата вы находитесь, и это говорит вам, в каком направлении двигаться.
Спираль Java "Код гольф" попытка, основанная на варианте 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;
}
}
TDD, на 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;
}
}
Хаскелл, сделай свой выбор:
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] ]
Ваш вопрос выглядит как вопрос, называемый спиральной памятью. В этой задаче каждый квадрат в сетке распределяется по спирали, начиная с числа 1, расположенного в начале координат. И затем считая, вращаясь по спирали наружу. Например:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 ---->
Мое решение для вычисления координат каждого числа, следующего за этим спиралевидным узором, размещено ниже:
def spiral_pattern(num):
x = y = 0
for _ in range(num-1):
x, y = find_next(x, y)
yield (x, y)
def find_next(x, y):
"""find the coordinates of the next number"""
if x == 0 and y == 0:
return 1, 0
if abs(x) == abs(y):
if x > 0 and y > 0:
x, y = left(x, y)
elif x < 0 and y > 0:
x, y = down(x, y)
elif x < 0 and y < 0:
x, y = right(x, y)
elif x > 0 and y < 0:
x, y = x+1, y
else:
if x > y and abs(x) > abs(y):
x, y = up(x, y)
elif x < y and abs(x) < abs(y):
x, y = left(x, y)
elif x < y and abs(x) > abs(y):
x, y = down(x, y)
elif x > y and abs(x) < abs(y):
x, y = right(x, y)
return x, y
def up(x, y):
return x, y+1
def down(x, y):
return x, y-1
def left(x, y):
return x-1, y
def right(x, y):
return x+1, y
Вот мое решение (в рубине)
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}),"
}
Вот итеративное решение этой проблемы с помощью JavaScript (ES6):
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;
}
}
}
Вот как это использовать:
spiralMatrix(0, 0, 1, 100);
Это создаст внешнюю спираль, начиная с координат (x = 0, y = 0) с шагом 1 и общим количеством элементов равным 100. Реализация всегда начинает движение в следующем порядке - вверх, вправо, вниз, оставил.
Обратите внимание, что эта реализация создает квадратные матрицы.
Это в с.
Я случайно выбрал плохие имена переменных. В именах T == вверху, L == слева, B == внизу, R == справа. Итак, tli это верхний левый угол i, а brj нижний правый угол 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]);
}
}
У меня есть библиотека с открытым исходным кодом, pixelscan, которая представляет собой библиотеку python, которая предоставляет функции для сканирования пикселей на сетке в различных пространственных структурах. Пространственные модели включают в себя круговые, кольца, сетки, змей и случайные прогулки. Существуют также различные преобразования (например, клип, своп, вращение, перевод). Исходная проблема ОП может быть решена следующим образом
for x, y in clip(swap(ringscan(0, 0, 0, 2)), miny=-1, maxy=1):
print x, y
который дает очки
(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)
Генераторы библиотек и преобразования могут быть объединены в цепочку для изменения точек в широком диапазоне порядков и пространственных структур.
Вот решение в Python 3 для печати последовательных целых чисел по спирали по часовой стрелке и против часовой стрелки.
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
объяснение
Спираль состоит из концентрических квадратов, например квадрат 5х5 с вращением по часовой стрелке выглядит следующим образом:
5x5 3x3 1x1
>>>>>
^ v >>>
^ v + ^ v + >
^ v <<<
<<<<v
(>>>>> означает "перейти в 5 раз вправо" или увеличить индекс столбца в 5 раз, v означает уменьшение или увеличение индекса строки и т. д.)
Все квадраты одинаковы по своим размерам, я перебрал концентрические квадраты.
Для каждого квадрата в коде есть четыре цикла (по одному на каждую сторону), в каждом цикле мы увеличиваем или уменьшаем столбцы или индекс строки. Если i это индекс строки и j Индекс столбца, а затем квадрат 5x5 может быть построен путем:
- увеличения j от 0 до 4 (5 раз)
- увеличение i от 1 до 4 (4 раза)
- по убыванию j от 3 до 0 (4 раза)
- убывающий i от 3 до 1 (3 раза)
Для следующих квадратов (3x3 и 1x1) мы делаем то же самое, но смещаем начальный и конечный индексы соответствующим образом. Я использовал индекс k для каждого концентрического квадрата есть n//2 + 1 концентрических квадратов.
Наконец, немного математики для красивой печати.
Чтобы распечатать индексы:
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)
Python зацикливает спиральный код по часовой стрелке, используя ответ 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
Это мое очень плохое решение, основанное на минимальных знаниях Java. Здесь я должен разместить юниты на поле по спирали. Юниты не могут быть размещены поверх других юнитов, в горах или в океане.
Чтобы было ясно. Это не хорошее решение. Это очень плохое решение, добавленное для того, чтобы другие люди смеялись над тем, как плохо это можно сделать.
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);
}
Слава всем, кто действительно может прочитать это
Бонусный вопрос: каково время работы этого "алгоритма"? :П
// реализация 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>';
}
Вот 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);
}
}
}
Первый пример вопроса (3x3) будет:
var coords = SpiralCoords.GenerateOutTo(1);
Второй пример вопроса (5x3) будет:
var coords = SpiralCoords.GenerateOutTo(2).Where(x => abs(x.Item2) < 2);
Версия C#, также обрабатывает неквадратные размеры.
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;
}
Это немного другая версия - пытаюсь использовать recursion а также iterators в LUA. На каждом шаге программа опускается дальше внутрь матрицы и зацикливается. Я также добавил дополнительный флаг в спираль clockwise или же anticlockwise, Выход начинается с правого нижнего угла и рекурсивно зацикливается по направлению к центру.
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
Вот ответ Джулии: мой подход заключается в назначении точек в концентрических квадратах ("спиралях") вокруг начала координат (0,0)где каждый квадрат имеет длину стороны m = 2n + 1, чтобы создать упорядоченный словарь с номерами местоположений (начиная с 1 для начала координат) в качестве ключей и соответствующей координатой в качестве значения.
Поскольку максимальное местоположение на спираль составляет (n,-n), остальные точки можно найти, просто работая в обратном направлении от этой точки, то есть из нижнего правого угла m-1 единиц, затем повторяя для перпендикулярных 3 сегментов m-1 единицы.
Этот процесс записан в обратном порядке ниже, что соответствует ходу спирали, а не обратному процессу подсчета, т.е. ra [правый возрастающий] сегмент уменьшается на 3(m+1), затем la [по возрастанию] 2(m+1)и так далее - надеюсь, это говорит само за себя.
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
Итак, для вашего первого примера, подключение m = 3 в уравнение, чтобы найти п дает n = (5-1)/2 = 2, а также walk(2) дает упорядоченный словарь местоположений для координат, который можно превратить в массив координат, открыв словарь vals поле:
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)
Обратите внимание, что для некоторых функций [например, norm] может быть предпочтительнее оставить координаты в массивах, чем Tuple{Int,Int}но здесь я превращаю их в кортежи(x,y)- по запросу, используя понимание списка.
Контекст для "поддержки" неквадратной матрицы не указан (обратите внимание, что это решение все еще вычисляет значения вне сетки), но если вы хотите фильтровать только по диапазону x от y (здесь для x=5,y=3) после расчета полной спирали intersect эта матрица против значений из 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)
Решение для 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
Я делюсь этим кодом, который я разработал для другой цели; речь идет о поиске номера столбца "X" и номера строки "Y" элемента массива @ спирального индекса "index ". Эта функция принимает ширину "w" и высоту "h" матрицы, а также необходимый "индекс". Конечно, эту функцию можно использовать для получения того же требуемого результата. Я думаю, что это самый быстрый способ (так как он перепрыгивает через ячейки, а не сканирует их).
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 };
}
А
Kotlin спираль.
data class Point(val x: Int, val y: Int) {
operator fun plus(p: Point): Point = Point(x + p.x, y + p.y)
override fun toString() = "($x, $y)"
companion object {
enum class Directions(val d: Point) {
RIGHT(Point(1, 0)),
UP(Point(0, 1)),
LEFT(Point(-1, 0)),
DOWN(Point(0, -1))
}
fun spiral() = sequence {
var p = Point(0, 0)
// Always start at the origin.
yield(p)
// 0, 2, 4, 6 ...
generateSequence(0) { it + 2 }.forEach { n ->
// For each of the 4 directions
Directions.values().forEach { d ->
// actual length depends slightly on direction
val l = n + when (d) {
Directions.RIGHT, Directions.UP -> 1
Directions.LEFT, Directions.DOWN -> 2
}
// run to the next corner
for (i in 1..l) {
p += d.d
yield(p)
}
}
}
}
}
}
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;
}
Это решение Python/numpy, которое заполняет любой прямоугольник спиралью. Он решает немного другую проблему, чем исходный вопрос, но это то, что мне нужно.
import numpy as np
import matplotlib.pyplot as plt
def spiral(m, n):
M = np.zeros([m, n], dtype=int)
i, j = 0, 0 # location of "turtle"
di, dj = 0, 1 # direction of movement
h = (np.min([m,n]))/2
for ii in range(m * n):
M[i, j] = ii
if (i < h and (i == j+1 or i+1 == n-j)) or (i >= m-h and (m-i == n-j or m-i == j+1)):
di, dj = dj, -di # turn clockwise
i, j = i + di, j + dj
return M
plt.imshow(spiral(16, 24))
htt ps:https://stackru.com/images/f9b46509fcbe68d3b2a8f400d17af4944d522048.png
Я сделал это с другом, который настраивает соотношение сторон спирали и холста в Javascript. Лучшее решение, которое я получил для эволюции изображения пиксель за пикселем, заполняя все изображение.
Надеюсь, это поможет кому-то.
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);
Вы можете видеть, как это работает на http://jsfiddle.net/hitbyatruck/c4Kd6/. Просто не забудьте изменить ширину и высоту холста в javascript vars и в атрибутах HTML.
Мне не удалось найти реализацию на Rust, поэтому я выбрал вариант от @neatsu в качестве вдохновения и написал его на Rust.
Моя реализация «заполняет» область, описаннуюsizeпеременной, т.е. он останавливается, как только следующий шаг выйдет за пределы заданных измерений, и начинается сoriginрасположение.
Я также изменил направление движенияRight -> Up -> Left -> Down.
use Direction::*;
enum Direction { Up, Down, Left, Right }
impl Direction {
fn next(&mut self) {
*self = match self { Up => Left, Down => Right, Left => Down, Right => Up }
}
}
fn spiral(origin: (f64, f64), size: (f64, f64), step: f64) -> Vec<(f64, f64)> {
let (mut distance, mut range, mut direction, mut x, mut y) = (0,1,Right, origin.0, origin.1);
let mut res_vec = Vec::<(f64, f64)>::new();
while x.abs() <= size.0/2.0 && y.abs() <= size.1/2.0 {
res_vec.push((x, y)); distance += 1;
match direction {
Up => { y += step; if distance >= range { direction.next(); distance = 0; range += 1;}},
Down => { y -= step; if distance >= range { direction.next(); distance = 0; range += 1; }},
Left => { x -= step; if distance >= range { direction.next(); distance = 0; }},
Right => { x += step; if distance >= range { direction.next(); distance = 0; }},
}
}
return res_vec;
}
Использование:
let res = spiral((0.0, 0.0), (2.0, 2.0), 0.2);
print!("{:?}", res);
Это основано на вашем собственном решении, но мы можем быть умнее в поиске углов. Это облегчает понимание того, как можно пропустить области снаружи, если M и N сильно различаются.
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
и решение на основе генератора, которое лучше, чем O(max(n,m)^2). Это O(nm+abs(nm) ^ 2), потому что оно пропускает целые полосы, если они не являются частью решения.
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