Spirale schleifen

154

Ein Freund brauchte einen Algorithmus, mit dem er die Elemente einer NxM-Matrix durchlaufen konnte (N und M sind ungerade). Ich habe eine Lösung gefunden, aber ich wollte sehen, ob meine SO'-Kollegen eine bessere Lösung finden können.

Ich poste meine Lösung als Antwort auf diese Frage.

Beispielausgabe:

Für eine 3x3-Matrix sollte die Ausgabe sein:

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

3x3 Matrix

Darüber hinaus sollte der Algorithmus nicht quadratische Matrizen unterstützen, sodass die Ausgabe beispielsweise für eine 5x3-Matrix wie folgt lauten sollte:

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

5x3 Matrix

Kann Berk Güder
quelle
Können Sie erklären, was Sie für nicht quadratische Matrizen wollen? Ihre Lösung hat einen "Sprung" von (2,1) nach (-2,1) - ist das beabsichtigt? [ZB für eine 7x3-Matrix hätte es zwei weitere "Sprünge" und für eine (2k + 1) x3-Matrix hätte es 2k-3 Sprünge?]
ShreevatsaR
3
Ja, die Sprünge sind absichtlich. Ich habe die Frage mit einem 5x3-Matrixbild aktualisiert. Wie Sie auf dem Bild sehen können, überspringen wir die oberen und unteren Zeilen.
Kann Berk Güder
Ok, dann scheint dein eigener Code am saubersten zu sein. Und obwohl dies offtopisch ist: Wie haben Sie diese Bilder erzeugt? :)
ShreevatsaR
=)) Ich habe sie nicht generiert. Tatsächlich ist die Art und Weise, wie ich sie erstellt habe, ziemlich dumm. Ich habe die Tabellen in OO.org Calc erstellt, einen Screenshot gemacht und den Screenshot in GIMP bearbeitet. =))
Kann Berk Güder
1
@Ying: Ich weiß nicht wirklich, warum mein Freund das braucht, aber er sagte, er möchte Mitglieder der Matrix in einem Suchalgorithmus näher am Zentrum bevorzugen.
Kann Berk Güder

Antworten:

63

Hier ist meine Lösung (in 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
Kann Berk Güder
quelle
1
Soweit ich sehen kann, ist dies die beste Art, es zu schreiben. Die einzig mögliche Verbesserung wäre, O (MN) anstelle von O (max (M, N) ^ 2) zu machen, indem direkt über die (x, y) gesprungen wird, die nicht gedruckt werden sollen, aber den Code ergeben ein bisschen hässlicher.
ShreevatsaR
Ich optimiere meine Lösung und sie kommt dem, was Sie bereits haben, ziemlich nahe. Dies ist eine ziemlich gute Lösung, denke ich. Abgesehen von ShreevatsaRs Vorschlag und Dingen wie der Nichtberechnung von x / 2 und y / 2 bei jeder Iteration gibt es außer dem Stil nicht viel zu verbessern.
Triptychon
Irgendwelche Lösungen für Matlab?!
Sam
Gibt dies eine gute Cache-Kohärenz für den Zugriff auf Bildpufferdaten? (Es gibt hier so viele Antworten, aber nicht viele Informationen darüber, welche für Hochleistungsbildoperationen am besten geeignet sind)
ideasman42
@ ideasman42 - das kommt nicht ins Spiel, weil das Ergebnis immer das gleiche spiralförmige Koordinatenmuster ist. Ob das Spiralmuster Cache-kohärent ist, hängt vermutlich von der Implementierung des Bildpuffers ab. (Ich vermute, es würde den Cache mehr verprügeln als andere Arten, das Bild zu durchlaufen, wie z. B. Zeile für Zeile in der richtigen Reihenfolge). Die Wahl des Algorithmus zur Erzeugung dieser Koordinaten hat jedoch wahrscheinlich keinen Einfluss auf den Cache.
Raptormeat
31

C ++ jemand? Schnelle Übersetzung aus Python, der Vollständigkeit halber veröffentlicht

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
quelle
Sie können auch s und ds verwenden, wie ich es tue, um die Ecken zu erkennen, die den riesigen if-Zustand
beseitigen
1
Eine Bearbeitung dieses Beitrags wurde hier vorgeschlagen . Obwohl die Bearbeitung abgelehnt wurde, weil sie die Bedeutung Ihres Beitrags ändert, sollten Sie die vorgeschlagenen Änderungen in Betracht ziehen, wenn dies sinnvoll ist.
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

Es wurden viele Lösungen für dieses Problem vorgeschlagen, die in verschiedenen Programmiersprachen geschrieben wurden, aber alle scheinen aus demselben verschlungenen Ansatz zu stammen. Ich werde das allgemeinere Problem der Berechnung einer Spirale betrachten, die durch Induktion präzise ausgedrückt werden kann.

Basisfall: Beginnen Sie bei (0, 0), bewegen Sie sich 1 Feld vorwärts, biegen Sie links ab, bewegen Sie sich 1 Feld vorwärts, biegen Sie links ab. Induktiver Schritt: Bewegen Sie sich vorwärts n + 1 Quadrate, biegen Sie links ab, bewegen Sie sich vorwärts n + 1 Quadrate, biegen Sie links ab.

Die mathematische Eleganz, dieses Problem auszudrücken, legt nahe, dass es einen einfachen Algorithmus geben sollte, um die Lösung zu berechnen. Unter Berücksichtigung der Abstraktion habe ich mich entschieden, den Algorithmus nicht in einer bestimmten Programmiersprache zu implementieren, sondern als Pseudocode.

Zuerst werde ich einen Algorithmus betrachten, um nur 2 Iterationen der Spirale unter Verwendung von 4 Paaren von while-Schleifen zu berechnen. Die Struktur jedes Paares ist ähnlich, jedoch eigenständig. Dies mag zunächst verrückt erscheinen (einige Schleifen werden nur einmal ausgeführt), aber Schritt für Schritt werde ich Transformationen durchführen, bis wir zu 4 Paaren von Schleifen gelangen, die identisch sind und daher durch ein einzelnes Paar innerhalb einer anderen Schleife ersetzt werden können. Dies bietet uns eine allgemeine Lösung für die Berechnung von Iterationen ohne Verwendung von Bedingungen.

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

Die erste Transformation, die wir durchführen werden, ist die Einführung einer neuen Variablen d für die Richtung, die entweder den Wert +1 oder -1 enthält. Die Richtung wechselt nach jedem Schleifenpaar. Da wir den Wert von d an allen Punkten kennen, können wir jede Seite jeder Ungleichung damit multiplizieren, die Richtung der Ungleichung entsprechend anpassen und alle Multiplikationen von d mit einer Konstanten zu einer anderen Konstante vereinfachen. Dies lässt uns folgendes übrig.

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

Nun stellen wir fest, dass sowohl x * d als auch die RHS ganze Zahlen sind, sodass wir jeden reellen Wert zwischen 0 und 1 von der RHS subtrahieren können, ohne das Ergebnis der Ungleichung zu beeinflussen. Wir ziehen es vor, 0,5 von den Ungleichungen jedes zweiten Paares von while-Schleifen zu subtrahieren, um ein besseres Muster zu erhalten.

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

Wir können jetzt eine weitere Variable m für die Anzahl der Schritte einführen, die wir bei jedem Paar von while-Schleifen ausführen.

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

Schließlich sehen wir, dass die Struktur jedes Paares von while-Schleifen identisch ist und auf eine einzelne Schleife reduziert werden kann, die innerhalb einer anderen Schleife platziert ist. Um die Verwendung von reellen Zahlen zu vermeiden, habe ich den Anfangswert von m multipliziert. der Wert m wird erhöht um; und beide Seiten jeder Ungleichung um 2.

Dies führt zu der am Anfang dieser Antwort gezeigten Lösung.

Mike
quelle
1
Unter welchen Bedingungen würde Ihre endgültige Lösung enden?
Merlyn Morgan-Graham
1
Was ist die Anwendung einer solchen Art des Musterdrucks?
Ashish Shukla
1
@ MerlynMorgan-Graham Wird beendet, wenn dem Computer der Speicher oder die Stromversorgung ausgeht.
Mike
Es scheint, dass die Eleganz dieser Lösung darin besteht, Zeit- und Speicherbeschränkungen zu ignorieren. Ich empfehle, elegant eine Kündigungsbedingung hinzuzufügen (wenn möglich). Ich empfehle außerdem, es an den Anfang der Antwort zu verschieben und die Ableitung darunter anzuzeigen.
Merlyn Morgan-Graham
1
Während sich die ursprüngliche Frage auf eine NxM-Matrix bezog, ist dies tatsächlich eine sehr nützliche Antwort, wenn Sie endlos nach außen drehen müssen, bis Sie etwas finden (dh dann brechen oder zurückkehren). Natürlich müssen Sie, wie in den anderen Kommentaren erwähnt, diese Beendigungsbedingung definieren, sonst wird sie für immer ausgeführt.
Clogg
16

Hier ist eine O (1) -Lösung, um die Position in einer quadratischen Spirale zu finden: Geige

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
quelle
3
Um von der Mitte aus zu beginnen, fügen Sie zwei Zeilen hinzu. if (n === 0) return [0, 0, r]; --n;Siehe Fiddle: jsfiddle.net/Wishmesh/nwd9gt1s/2
Maris B.
15

Ich liebe Pythons Generatoren.

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

Testen mit:

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

Du erhältst:

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
quelle
8

Java-Spiralversuch "Code Golf", basierend auf der C ++ - Variante.

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

Hier ist eine C ++ - Lösung, die zeigt, dass Sie die nächsten (x, y) Koordinaten direkt und einfach aus den vorherigen berechnen können - ohne die aktuelle Richtung, den Radius oder irgendetwas anderes verfolgen zu müssen:

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

Wenn Sie nur versuchen, die ersten N Punkte in der Spirale zu generieren (ohne die Einschränkung des ursprünglichen Problems, einen N x M-Bereich zu maskieren), wird der Code sehr einfach:

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

Der Trick besteht darin, dass Sie x und y vergleichen können, um festzustellen, auf welcher Seite des Quadrats Sie sich befinden, und dass Sie wissen, in welche Richtung Sie sich bewegen müssen.

Michael
quelle
5

TDD in 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;
    }
}
Carl Manaster
quelle
@leppie: Vielleicht nicht - schon gar nicht kurz genug - aber ich denke, es ist eine gute Demonstration von TDD und einigermaßen sauberer, leicht verständlicher und korrekter Code. Ich lasse es in.
Carl Manaster
4

Hier ist meine Lösung (In Ruby)

def spiral(xDim, yDim)
   sx = xDim / 2
   sy = yDim / 2

   cx = cy = 0
   direction = distance = 1

   yield(cx,cy)
   while(cx.abs <= sx || cy.abs <= sy)
      distance.times { cx += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } 
      distance.times { cy += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } 
      distance += 1
      direction *= -1
   end
end

spiral(5,3) { |x,y|
   print "(#{x},#{y}),"
}
Starkii
quelle
Immer noch O (max (n, m) ^ 2), aber schöner Stil.
Triptychon
1
Richtung = -Richtung statt Richtung * = - 1? Wenn Sie Golf gespielt haben, ist d = -d auch kürzer als d * = - 1
John La Rooy
3

Haskell, treffen Sie Ihre Wahl:

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] ]
kurzlebig
quelle
22
Bitte nimm das nicht als Schimpfen oder Trollkommentar, aber GOTT ist hässlich!
Petruza
1
Ich konnte dem obigen Kommentar nicht mehr zustimmen.
Sneakyness
Dieser Haskell sieht für mich sehr trendy aus.
1
Ja, aber beachten Sie, wie ausdrucksstark es ist. Vergleichen Sie die Länge mit einigen anderen hier veröffentlichten Beispielen.
Robert Harvey
@ Petruza Eigentlich ist es nicht die beste Lösung in Haskell. Werfen
polkovnikov.ph
2

Dies ist in C.

Ich habe zufällig schlechte Variablennamen gewählt. In den Namen T == oben, L == links, B == unten, R == rechts. Also ist tli oben links i und brj ist unten rechts 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
quelle
2

Ich habe eine Open-Source-Bibliothek, Pixelscan , eine Python-Bibliothek, die Funktionen zum Scannen von Pixeln in einem Raster in verschiedenen räumlichen Mustern bietet. Die enthaltenen räumlichen Muster sind kreisförmig, Ringe, Gitter, Schlangen und zufällige Spaziergänge. Es gibt auch verschiedene Transformationen (z. B. Clip, Swap, Rotate, Translate). Das ursprüngliche OP-Problem kann wie folgt gelöst werden

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

das ergibt die Punkte

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

Die Bibliotheksgeneratoren und -transformationen können verkettet werden, um die Punkte in einer Vielzahl von Ordnungen und räumlichen Mustern zu ändern.

dpmcmlxxvi
quelle
2

Hier ist eine Lösung in Python 3 zum Drucken aufeinanderfolgender Ganzzahlen im Uhrzeigersinn und gegen den Uhrzeigersinn.

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

Erläuterung

Eine Spirale besteht aus konzentrischen Quadraten, zum Beispiel sieht ein 5x5-Quadrat mit Drehung im Uhrzeigersinn folgendermaßen aus:

 5x5        3x3      1x1

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

( >>>>>bedeutet "5-mal nach rechts gehen" oder Spaltenindex 5-mal erhöhen, Zeilenindex nach vunten oder erhöhen usw.)

Alle Quadrate sind bis zu ihrer Größe gleich, ich habe die konzentrischen Quadrate durchlaufen.

Für jedes Quadrat hat der Code vier Schleifen (eine für jede Seite). In jeder Schleife erhöhen oder verringern wir den Spalten- oder Zeilenindex. Wenn ies sich um den Zeilenindex und jden Spaltenindex handelt, kann ein 5x5-Quadrat erstellt werden durch: - Inkrementieren jvon 0 auf 4 (5 Mal) - Inkrementieren ivon 1 auf 4 (4 Mal) - Dekrementieren jvon 3 auf 0 (4 Mal) - Dekrementieren ivon 3 bis 1 (3 mal)

Für die nächsten Quadrate (3x3 und 1x1) machen wir dasselbe, verschieben jedoch den Anfangs- und den Endindex entsprechend. Ich habe kfür jedes konzentrische Quadrat einen Index verwendet , es gibt n // 2 + 1 konzentrische Quadrate.

Zum Schluss noch ein bisschen Mathe zum hübschen Drucken.

So drucken Sie die Indizes:

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
quelle
1

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

}

Das erste Beispiel der Frage (3x3) wäre:

var coords = SpiralCoords.GenerateOutTo(1);

Das zweite Beispiel der Frage (5x3) wäre:

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

Dies ist eine etwas andere Version - versucht, recursionund iteratorsin LUA zu verwenden. Bei jedem Schritt steigt das Programm weiter in die Matrix und die Schleifen ab. Ich habe auch eine zusätzliche Flagge zu Spirale clockwiseoder hinzugefügt anticlockwise. Die Ausgabe beginnt in den unteren rechten Ecken und verläuft rekursiv zur Mitte.

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.
quelle
1

// PHP-Implementierung

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
quelle
1

Hier ist eine iterative JavaScript (ES6) -Lösung für dieses 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;
        }
    }
}

So verwenden Sie es:

spiralMatrix(0, 0, 1, 100);

Dies erzeugt eine nach außen gerichtete Spirale, beginnend bei den Koordinaten (x = 0, y = 0) mit Schritt 1 und einer Gesamtzahl von Elementen gleich 100. Die Implementierung startet die Bewegung immer in der folgenden Reihenfolge - oben, rechts, unten, links.

Bitte beachten Sie, dass diese Implementierung quadratische Matrizen erstellt.

Neatsu
quelle
1

Hier ist eine Antwort in Julia: Mein Ansatz besteht darin, die Punkte in konzentrischen Quadraten ('Spiralen') um den Ursprung herum zuzuweisen (0,0), wobei jedes Quadrat eine Seitenlänge m = 2n + 1hat, um ein geordnetes Wörterbuch mit Positionsnummern (beginnend mit 1 für den Ursprung) als Schlüssel zu erstellen und die entsprechende Koordinate als Wert.

Da die maximale Position pro Spirale bei liegt (n,-n), können die restlichen Punkte gefunden werden, indem einfach von diesem Punkt aus rückwärts gearbeitet wird, dh von der unteren rechten Ecke nach m-1Einheiten, und dann für die senkrechten 3 Segmente von wiederholt wirdm-1 Einheiten .

Dieser Prozess wird unten in umgekehrter Reihenfolge geschrieben, entsprechend dem Verlauf der Spirale und nicht diesem umgekehrten Zählprozess, dh das raSegment [rechts aufsteigend] wird um dekrementiert 3(m+1), dann um la[links aufsteigend] 2(m+1)usw. - hoffentlich ist dies selbsterklärend .

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

Wenn Sie also für Ihr erstes Beispiel m = 3die Gleichung eingeben , um n zu finden n = (5-1)/2 = 2, erhalten Sie walk(2)ein geordnetes Wörterbuch mit Positionen für Koordinaten, das Sie durch Zugriff auf das valsFeld des Wörterbuchs in ein Array von Koordinaten umwandeln können:

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)

Beachten Sie, dass es für einige Funktionen [z. B. norm] vorzuziehen ist, die Koordinaten in Arrays Tuple{Int,Int}zu belassen (x,y), anstatt sie hier in Tupel umzuwandeln - wie gewünscht, unter Verwendung des Listenverständnisses.

Der Kontext für „Unterstützung“ eine nicht-quadratische Matrix nicht angegeben ist ( man beachte , dass diese Lösung immer noch die Off-Grid - Werte berechnet), aber wenn Sie filtern mögen nur auf den Bereich xvon y(hier x=5, y=3) nach der vollständigen Spirale Berechnung dann intersectdiese Matrix gegen die Werte von 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
quelle
1

Ihre Frage sieht aus wie eine Frage namens Spiralspeicher. In diesem Problem wird jedes Quadrat auf dem Gitter in einem Spiralmuster beginnend mit der Nummer 1 zugewiesen, die sich am Ursprung befindet. Und dann hochzählen, während wir uns nach außen drehen. Beispielsweise:

17  16  15  14  13

18   5   4   3  12

19   6   1   2  11

20   7   8   9  10

21  22  23  ---->

Meine Lösung zur Berechnung der Koordinaten jeder Zahl nach diesem Spiralmuster ist unten aufgeführt:

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
quelle
0

Dies basiert auf Ihrer eigenen Lösung, aber wir können klüger sein, wenn es darum geht, die Ecken zu finden. Auf diese Weise können Sie leichter erkennen, wie Sie die Bereiche außerhalb überspringen können, wenn M und N sehr unterschiedlich sind.

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

und eine generatorbasierte Lösung, die besser als O ist (max (n, m) ^ 2). Es ist O (nm + abs (nm) ^ 2), weil ganze Streifen übersprungen werden, wenn sie nicht Teil der Lösung sind.

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
quelle
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
quelle
0

Dies ist meine sehr, sehr schlechte Lösung, die aus minimalen Java-Kenntnissen besteht. Hier muss ich Einheiten spiralförmig auf ein Feld legen. Einheiten können nicht auf anderen Einheiten oder auf Bergen oder im Ozean platziert werden.

Deutlich sein. Dies ist keine gute Lösung. Dies ist eine sehr schlechte Lösung, die zum Spaß anderer Leute hinzugefügt wurde, um darüber zu lachen, wie schlecht es gemacht werden kann

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

Ein großes Lob an alle, die dies tatsächlich lesen können

Bonusfrage: Was ist die Laufzeit dieses "Algorithmus"? : P.

Schwarzer Bulle
quelle
1
+1 wegen " Dies ist eine sehr schlechte Lösung, die zum Spaß anderer Leute hinzugefügt wurde, um darüber zu lachen, wie schlecht es gemacht werden kann ".
Oriol
0

Lösung für 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
quelle
0

Ich hatte kürzlich eine ähnliche Herausforderung, bei der ich ein 2D-Array erstellen und einen Spiralmatrix-Algorithmus verwenden musste, um die Ergebnisse zu sortieren und zu drucken. Dieser C # -Code funktioniert mit einem N, N 2D-Array. Es ist aus Gründen der Klarheit ausführlich und kann wahrscheinlich an Ihre Bedürfnisse angepasst werden.

//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;
}
rauben
quelle
0

Ich habe dieses mit einem Freund gemacht, der die Spirale an das Seitenverhältnis der Leinwand in Javascript anpasst. Die beste Lösung für eine Bildentwicklung Pixel für Pixel, die das gesamte Bild ausfüllt.

Hoffe es hilft jemandem.

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

Sie können es auf http://jsfiddle.net/hitbyatruck/c4Kd6/ sehen . Stellen Sie nur sicher, dass Sie die Breite und Höhe der Zeichenfläche in den Javascript-Variablen und in den Attributen im HTML ändern.

HBT
quelle
0

Nur zum Spaß 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);
user5124517
quelle
0

C # -Version, auch nicht quadratische Größen.

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
quelle
0

Ich teile diesen Code, den ich für einen anderen Zweck entworfen habe. Es geht darum, die Spaltennummer "X" und die Zeilennummer "Y" des Array-Elements @ Spiral-Index "Index" zu finden. Diese Funktion verwendet die Breite "w" und Höhe "h" der Matrix sowie den erforderlichen "Index". Natürlich kann diese Funktion verwendet werden, um die gleiche erforderliche Ausgabe zu erzeugen. Ich denke, es ist die schnellstmögliche Methode (da sie über Zellen springt, anstatt sie zu scannen).

    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
quelle
0

Python-Schleifen-Spiralcode im Uhrzeigersinn mit der Antwort von 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
quelle
1
Es ist im Uhrzeigersinn 🔃 und ich zitierte Can Berk Güder. Die ursprüngliche Frage ist gegen den Uhrzeigersinn 🔄. Ich brauchte eine Funktion im Uhrzeigersinn, daher hielt ich es für nützlich, sie dort zu lassen.
Adrianmelic
0

Davidonts hervorragende Lösung 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
grinsender Mann
quelle