Pętla w spiralę

154

Znajomy potrzebował algorytmu, który pozwoliłby mu przeglądać elementy macierzy NxM (N i M są nieparzyste). Wymyśliłem rozwiązanie, ale chciałem sprawdzić, czy moi koledzy z SO mogą znaleźć lepsze rozwiązanie.

W odpowiedzi na to pytanie zamieszczam moje rozwiązanie.

Przykładowe dane wyjściowe:

W przypadku macierzy 3x3 wynik powinien wyglądać następująco:

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

Macierz 3x3

Ponadto algorytm powinien obsługiwać macierze niekwadratowe, więc na przykład dla macierzy 5x3 wynik powinien wyglądać następująco:

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

Matryca 5x3

Czy Berk Güder
źródło
Czy możesz wyjaśnić, czego chcesz dla macierzy innych niż kwadratowe? Twoje rozwiązanie ma „skok” z (2,1) do (-2,1) - czy to jest zamierzone? [Np. Dla macierzy 7x3 miałaby jeszcze dwa "skoki", a dla macierzy (2k + 1) x3 miałaby 2k-3 skoki?]
ShreevatsaR
3
Tak, skoki są celowe. Zaktualizowałem pytanie o obraz matrycy 5x3. Jak widać na obrazku, pomijamy górny i dolny wiersz.
Can Berk Güder
Ok, Twój własny kod wydaje się najczystszy. I chociaż to jest offtopic: jak wygenerowałeś te obrazy? :)
ShreevatsaR
=)) Nie wygenerowałem ich. Właściwie sposób, w jaki je stworzyłem, jest dość głupi. Stworzyłem tabele w OO.org Calc, zrobiłem zrzut ekranu i zredagowałem zrzut w GIMP. =))
Can Berk Güder
1
@Ying: Naprawdę nie wiem, dlaczego mój przyjaciel tego potrzebuje, ale powiedział, że chce faworyzować członków macierzy bliżej środka algorytmu wyszukiwania.
Can Berk Güder

Odpowiedzi:

63

Oto moje rozwiązanie (w Pythonie):

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
Czy Berk Güder
źródło
1
To najlepszy sposób na zapisanie tego, o ile wiem. Jedynym możliwym ulepszeniem byłoby uczynienie go O (MN) zamiast O (max (M, N) ^ 2) poprzez bezpośrednie pominięcie tych (x, y), które nie będą drukowane, ale spowoduje to, że kod trochę bardziej brzydki.
ShreevatsaR
Optymalizuję swoje rozwiązanie i jest blisko tego, co już masz. Myślę, że to całkiem dobre rozwiązanie. Poza sugestią ShreevatsaR i takimi rzeczami jak nie obliczanie x / 2 i y / 2 w każdej iteracji, nie ma zbyt wiele do poprawienia poza stylem.
Tryptyk
Jakieś rozwiązania dla MATLAB ?!
Sam
Czy to zapewnia dobrą spójność pamięci podręcznej przy dostępie do danych bufora obrazu? (Jest tu tak wiele odpowiedzi, ale niewiele informacji dotyczących tego, które działa najlepiej w przypadku operacji na
obrazach
@ ideasman42 - to nie wchodzi w grę, ponieważ rezultatem jest zawsze ten sam spiralny wzór współrzędnych. To, czy wzór spiralny jest spójny w pamięci podręcznej, wydaje mi się, że zależy od implementacji bufora obrazu. (Domyślam się, że to rozwaliłoby pamięć podręczną bardziej niż inne sposoby poruszania się po obrazie, jak przejście linia po linii w kolejności). Ale wybór algorytmu do tworzenia tych współrzędnych prawdopodobnie nie wpłynie na pamięć podręczną.
Raptormeat
31

C ++ ktoś? Szybkie tłumaczenie z Pythona, opublikowane dla kompletności

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;
    }
}
Tom J Nowell
źródło
możesz również użyć s i ds, tak jak ja, aby wykryć rogi, które pozbywają się ogromnego warunku if
John La Rooy,
1
Zmienił na to stanowisko został zasugerował tutaj . Chociaż zmiana została odrzucona, ponieważ zmienia znaczenie Twojego posta, możesz rozważyć uwzględnienie sugerowanych zmian, jeśli ma to sens.
Robert Harvey
19
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

Było wiele propozycji rozwiązań tego problemu napisanych w różnych językach programowania, jednak wszystkie wydają się wynikać z tego samego zawiłego podejścia. Rozważę bardziej ogólny problem obliczania spirali, którą można zwięźle wyrazić za pomocą indukcji.

Podstawowy przypadek: zacznij od (0, 0), przejdź do przodu o 1 pole, skręć w lewo, przejdź do przodu o 1 pole, skręć w lewo. Krok indukcyjny: przesuń się do przodu o n + 1 pól, skręć w lewo, przejdź do przodu o n + 1 kwadratów, skręć w lewo.

Matematyczna elegancja wyrażenia tego problemu silnie sugeruje, że powinien istnieć prosty algorytm obliczania rozwiązania. Pamiętając o abstrakcji, zdecydowałem się nie implementować algorytmu w konkretnym języku programowania, ale raczej jako pseudokod.

Najpierw rozważę algorytm obliczający tylko 2 iteracje spirali przy użyciu 4 par pętli while. Struktura każdej pary jest podobna, ale odrębna na swój sposób. Na początku może się to wydawać szalone (niektóre pętle są wykonywane tylko raz), ale krok po kroku będę dokonywać transformacji, aż dojdziemy do 4 identycznych par pętli, które można zastąpić pojedynczą parą umieszczoną w innej pętli. To zapewni nam ogólne rozwiązanie obliczania n iteracji bez używania jakichkolwiek warunków.

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

Pierwszą transformacją, której dokonamy, będzie wprowadzenie nowej zmiennej d dla kierunku, która ma wartość +1 lub -1. Kierunek zmienia się po każdej parze pętli. Ponieważ znamy wartość d we wszystkich punktach, możemy pomnożyć przez nią każdą stronę każdej nierówności, odpowiednio dostosować kierunek nierówności i uprościć wszelkie mnożenia d przez stałą do innej stałej. Pozostaje nam to, co następuje.

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

Teraz zauważamy, że zarówno x * d, jak i RHS są liczbami całkowitymi, więc możemy odjąć dowolną wartość rzeczywistą z zakresu od 0 do 1 od RHS bez wpływu na wynik nierówności. Decydujemy się odjąć 0,5 od nierówności każdej innej pary pętli while, aby uzyskać więcej wzoru.

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

Możemy teraz wprowadzić inną zmienną m dla liczby kroków, które wykonujemy w każdej parze pętli 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

Wreszcie widzimy, że struktura każdej pary pętli while jest identyczna i można ją zredukować do pojedynczej pętli umieszczonej wewnątrz innej pętli. Ponadto, aby uniknąć używania liczb o wartościach rzeczywistych, pomnożyłem początkową wartość m; wartość m jest zwiększana o; i obie strony każdej nierówności o 2.

Prowadzi to do rozwiązania przedstawionego na początku tej odpowiedzi.

Mikrofon
źródło
1
W jakich warunkach zakończy się ostateczne rozwiązanie?
Merlyn Morgan-Graham
1
Jakie jest zastosowanie tego typu nadruku wzoru?
Ashish Shukla
1
@ MerlynMorgan-Graham Kończy się, gdy komputerowi zabraknie pamięci lub mocy.
Mike
Wydaje się, że elegancja tego rozwiązania wynika z ignorowania ograniczeń czasowych i pamięciowych. Polecam elegancko dodać warunek zakończenia (jeśli to możliwe). Zalecam również przeniesienie go na początek odpowiedzi i pokazanie wyprowadzenia poniżej.
Merlyn Morgan-Graham
1
Chociaż pierwotne pytanie dotyczyło macierzy NxM, jest to w rzeczywistości bardzo przydatna odpowiedź, jeśli potrzebujesz nieskończonej spirali na zewnątrz, aż coś znajdziesz (tj. Wtedy złamiesz lub powrócisz). Oczywiście, podobnie jak w przypadku innych uwag, musisz zdefiniować ten warunek zakończenia, w przeciwnym razie będzie on trwał wiecznie.
cclogg
16

Oto rozwiązanie O (1) pozwalające znaleźć pozycję w kwadratowej spirali: Skrzypce

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;
}
davidonet
źródło
3
Aby zacząć od środka, dodaj dwie linie. if (n === 0) return [0, 0, r]; --n;Zobacz Fiddle: jsfiddle.net/Wishmesh/nwd9gt1s/2
Maris B.,
15

Uwielbiam generatory Pythona.

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

Testowanie z:

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

Dostajesz:

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)
Andrea Ambu
źródło
8

Próba spirali Java „Code golf”, oparta na wariancie 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;
    }
}
JHolta
źródło
7

Oto rozwiązanie w C ++, które pokazuje, że możesz obliczyć następne współrzędne (x, y) bezpośrednio i łatwo na podstawie poprzednich - nie ma potrzeby śledzenia bieżącego kierunku, promienia lub czegokolwiek innego:

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

Jeśli wszystko, co próbujesz zrobić, to wygenerować pierwsze N ​​punktów spirali (bez ograniczenia pierwotnego problemu do maskowania do regionu N x M), kod staje się bardzo prosty:

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

Sztuczka polega na tym, że możesz porównać x i y, aby określić, po której stronie kwadratu się znajdujesz, a to mówi ci, w jakim kierunku się poruszać.

Michael
źródło
5

TDD w Javie.

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;
    }
}
Carl Manaster
źródło
@leppie: Może nie - na pewno nie wystarczająco krótki - ale myślę, że to dobra demonstracja TDD i w miarę czysty, łatwy do zrozumienia, poprawny kod. Zostawię to.
Carl Manaster
4

Oto moje rozwiązanie (w języku 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}),"
}
Starkii
źródło
Nadal O (max (n, m) ^ 2), ale ładny styl.
Tryptyk
1
kierunek = -kierunek zamiast kierunku * = - 1? jeśli grałeś w golfa d = -d jest krótszy niż d * = - 1 też
John La Rooy,
3

Haskell, wybierz:

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] ]
ephemient
źródło
22
Proszę, nie traktuj tego jako tyrady lub komentarza trolla, ale BÓG jest brzydki!
Petruza
1
Nie mogłem się bardziej zgodzić z powyższym komentarzem.
Sneakyness
Ten Haskell wygląda dla mnie bardzo modnie.
1
Tak, ale zwróć uwagę, jakie to ekspresyjne. Porównaj jego długość z innymi przykładami zamieszczonymi tutaj.
Robert Harvey,
@Petruza Właściwie to nie jest najlepsze rozwiązanie w Haskell. Spójrz tutaj: rosettacode.org/wiki/Spiral_matrix#Haskell
polkovnikov.ph
2

To jest w C.

Zdarzyło mi się wybrać złe nazwy zmiennych. W nazwach T == góra, L == lewa, B == dół, R == prawa. Zatem tli jest lewym górnym i, a brj jest prawym dolnym 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]);
   }
}
Annu Gogatya
źródło
2

Mam bibliotekę open source, pixelscan , która jest biblioteką Pythona, która zapewnia funkcje do skanowania pikseli na siatce w różnych wzorach przestrzennych. Uwzględnione wzory przestrzenne to okrągłe, pierścienie, siatki, węże i przypadkowe spacery. Istnieją również różne transformacje (np. Przycinanie, zamiana, obracanie, tłumaczenie). Pierwotny problem z OP można rozwiązać w następujący sposób

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

co daje punkty

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

Biblioteki generatorów i transformacji można łączyć w łańcuchy, aby zmieniać punkty w wielu różnych porządkach i wzorach przestrzennych.

dpmcmlxxvi
źródło
2

Oto rozwiązanie w Pythonie 3 do drukowania kolejnych liczb całkowitych po spirali zgodnie z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara.

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

Wyjaśnienie

Spirala składa się z koncentrycznych kwadratów, na przykład kwadrat 5x5 obracający się w prawo wygląda następująco:

 5x5        3x3      1x1

>>>>>
^   v       >>>
^   v   +   ^ v   +   >
^   v       <<<
<<<<v

( >>>>>oznacza „idź 5 razy w prawo” lub zwiększ indeks kolumny 5 razy, voznacza zmniejsz lub zwiększ indeks wierszy itp.)

Wszystkie kwadraty są takie same, jeśli chodzi o ich rozmiar. Przejechałem pętlą po koncentrycznych kwadratach.

Dla każdego kwadratu kod ma cztery pętle (po jednej na każdą stronę), w każdej pętli zwiększamy lub zmniejszamy indeks kolumn lub wierszy. Jeśli ijest indeksem wiersza i indeksem jkolumny, to kwadrat 5x5 można skonstruować przez: - zwiększanie jod 0 do 4 (5 razy) - zwiększanie iod 1 do 4 (4 razy) - zmniejszanie jod 3 do 0 (4 razy) - zmniejszanie iod 3 do 1 (3 razy)

Dla następnych kwadratów (3x3 i 1x1) robimy to samo, ale odpowiednio przesuwamy indeksy początkowy i końcowy. Użyłem indeksuk dla każdego koncentrycznego kwadratu, jest n // 2 + 1 koncentrycznych kwadratów.

Na koniec trochę matematyki do ładnego drukowania.

Aby wydrukować indeksy:

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)
user2314737
źródło
1

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

}

Pierwszy przykład pytania (3x3) brzmiałby:

var coords = SpiralCoords.GenerateOutTo(1);

Drugi przykład pytania (5x3) wyglądałby tak:

var coords = SpiralCoords.GenerateOutTo(2).Where(x => abs(x.Item2) < 2);
Amy B.
źródło
1

To jest nieco inna wersja - próbuję używać recursioniw iteratorsLUA. Na każdym kroku program schodzi dalej w matrycę i pętle. Dodałem również dodatkową flagę do spirali clockwiselub anticlockwise. Dane wyjściowe zaczynają się od dolnych prawych rogów i zapętlają się rekurencyjnie w kierunku środka.

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
Arun R
źródło
1

// Implementacja 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>';
}
Florin Gologan
źródło
1

Oto iteracyjne rozwiązanie tego problemu w 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;
        }
    }
}

Oto jak go używać:

spiralMatrix(0, 0, 1, 100);

Stworzy to zewnętrzną spiralę, zaczynającą się od współrzędnych (x = 0, y = 0) z krokiem 1 i całkowitą liczbą elementów równą 100. Realizacja zawsze rozpoczyna ruch w następującej kolejności - w górę, w prawo, w dół, lewo.

Proszę zauważyć, że ta implementacja tworzy macierze kwadratowe.

neatsu
źródło
1

Oto odpowiedź w Julii: moje podejście polega na przypisaniu punktów w koncentrycznych kwadratach (`` spiralach '') wokół początku (0,0), gdzie każdy kwadrat ma długość boku m = 2n + 1, w celu utworzenia uporządkowanego słownika z numerami lokalizacji (zaczynając od 1 dla początku) jako kluczy i odpowiednia współrzędna jako wartość.

Ponieważ maksymalne położenie na spiralę znajduje się w (n,-n), pozostałe punkty można znaleźć, po prostu wykonując od tego punktu wstecz, tj. Od prawego dolnego rogu, o m-1jednostki, a następnie powtarzając dla prostopadłych 3 segmentów m-1jednostek.

Ten proces jest zapisany poniżej w odwrotnej kolejności, odpowiadającej temu, jak przebiega spirala, a nie odwrotnemu procesowi liczenia, tj. raSegment [rosnący w prawo] jest zmniejszany o 3(m+1), a następnie la[rosnący w lewo] o 2(m+1)itd. - Mam nadzieję, że jest to oczywiste .

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

Tak więc w pierwszym przykładzie podłączenie m = 3się do równania w celu znalezienia n daje n = (5-1)/2 = 2i walk(2)daje uporządkowany słownik lokalizacji współrzędnych, który można przekształcić w tablicę współrzędnych, uzyskując dostęp do valspola słownika :

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)

Zauważ, że w przypadku niektórych funkcji [np. norm] Może być lepiej pozostawienie współrzędnych w tablicach niż Tuple{Int,Int}, ale tutaj zamieniam je na krotki (x,y)- - zgodnie z życzeniem, używając funkcji list złożonych .

Kontekst dla „wspieranie” non-kwadrat matryca nie jest określona (uwaga, że to rozwiązanie wciąż oblicza wartości off-grid), ale jeśli chcesz, aby filtrować tylko zakresie xprzez y(tutaj x=5, y=3) po obliczeniu pełną spiralę następnie intersectta macierz w stosunku do wartości z 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)
Louis Maddox
źródło
1

Twoje pytanie wygląda jak pytanie zwane pamięcią spiralną. W tym zadaniu każdy kwadrat na siatce jest przydzielony spiralnie, zaczynając od cyfry 1, która znajduje się u początku. A potem zliczanie podczas spirali na zewnątrz. Na przykład:

17  16  15  14  13

18   5   4   3  12

19   6   1   2  11

20   7   8   9  10

21  22  23  ---->

Moje rozwiązanie do obliczania współrzędnych każdej liczby według tego wzoru spiralnego znajduje się poniżej:

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
Yossarian42
źródło
0

Jest to oparte na Twoim własnym rozwiązaniu, ale możemy być mądrzejsi w znajdowaniu narożników. Ułatwia to zorientowanie się, w jaki sposób można pominąć obszary na zewnątrz, jeśli M i N są bardzo różne.

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

i rozwiązanie oparte na generatorze, które jest lepsze niż O (max (n, m) ^ 2), to jest O (nm + abs (nm) ^ 2), ponieważ pomija całe paski, jeśli nie są częścią roztworu.

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
John La Rooy
źródło
0
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;
}
user1596193
źródło
0

To jest moje bardzo złe rozwiązanie, oparte na minimalnej znajomości języka Java. Tutaj muszę umieścić jednostki na polu w spiralę. Jednostki nie mogą być umieszczane na innych jednostkach ani na górach ani w oceanie.

Żeby było jasne. To nie jest dobre rozwiązanie. To bardzo złe rozwiązanie dodane dla zabawy innych ludzi, aby śmiać się z tego, jak źle można to zrobić

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 dla każdego, kto może to przeczytać

Pytanie dodatkowe: Jaki jest czas działania tego „algorytmu”? : P

Czarny byk
źródło
1
+1 z powodu „ To bardzo złe rozwiązanie dodane dla zabawy innych ludzi, aby śmiać się z tego, jak źle można to zrobić ”.
Oriol
0

Rozwiązanie dla 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
user3144509
źródło
0

Niedawno miałem podobne wyzwanie, w którym musiałem utworzyć tablicę 2D i użyć algorytmu matrycy spiralnej do sortowania i drukowania wyników. Ten kod C # będzie działał z tablicą 2D N, N. Dla jasności jest on rozwlekły i prawdopodobnie może zostać zmieniony w celu dostosowania do Twoich potrzeb.

//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;
}
Obrabować
źródło
0

Zrobiłem to z przyjacielem, który dostosowuje spiralę do proporcji płótna w JavaScript. Najlepsze rozwiązanie jakie otrzymałem dla ewolucji obrazu piksel po pikselu, wypełniając cały obraz.

Mam nadzieję, że to komuś pomoże.

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

Możesz zobaczyć, jak działa na http://jsfiddle.net/hitbyatruck/c4Kd6/ . Po prostu pamiętaj, aby zmienić szerokość i wysokość płótna w zmiennych javascript i atrybutach w HTML.

HBT
źródło
0

Dla zabawy w 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);
user5124517
źródło
0

Wersja C # obsługuje również rozmiary inne niż kwadratowe.

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;
}
ZimM
źródło
0

Dzielę się tym kodem, który zaprojektowałem w innym celu; chodzi o znalezienie numeru kolumny „X” i numeru wiersza „Y” elementu tablicy @ indeks spirali „indeks”. Ta funkcja pobiera szerokość „w” i wysokość „h” macierzy oraz wymagany „indeks”. Oczywiście ta funkcja może być użyta do uzyskania takiego samego wymaganego wyniku. Myślę, że jest to najszybsza możliwa metoda (przeskakuje komórki zamiast je skanować).

    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 };
    }
ABMoharram
źródło
0

Python zapętla spiralny kod zgodnie z ruchem wskazówek zegara, używając odpowiedzi 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
adrianmelic
źródło
1
Jest zgodnie z ruchem wskazówek zegara 🔃 i zacytowałem Can Berk Güder. Oryginalne pytanie dotyczy przeciwnej do ruchu wskazówek zegara 🔄. Potrzebowałem funkcji zgodnej z ruchem wskazówek zegara, więc uznałem, że warto ją tam zostawić.
adrianmelic
0

Doskonałe rozwiązanie firmy Davidont w 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
uśmiechnięty człowiek
źródło