Alle Ziele in einem Raster abknallen

[lennero]

Hallo
Ich habe ein NxM grid auf welchem sich Vögel (chars) befinden. In der Mitte des Rasters liegt eine Kanone die nach Norden gerichtet ist.
So sieht das ganze aus.

.O....OOOOO...O..
OO...OO.OOOOO..OO
OOO..O...O.OOOOO.
..O.....X...OOO..
..O.O.....O....OO

'O' = Vogel
'X' = Kanone

Die Kanone bewegt sich im Uhrzeigersinn und kann immer nur 1 Vogel pro Schritt abschießen. Nachdem ein Vogel abgeschossen wurde, bewegt sich die Kanone einen Schritt nach rechts und visiert automatisch den nächsten Vogel an.

Die Reihenfolge für die ersten 9 Schüsse sieht so aus

.O....OOO24...O..
OO...OO.13O67..9O
OO...O...5.8OOOO.
..O.....X...OOO..
..O.O.....O....OO

Gesucht ist die Anzahl an vollen Umdrehungen die die Kanone durchführt um alle Vögel zu erschießen. Das ganze soll natürlich für jedes x-beliebige Grid genauso funktionieren.

Was ich gegeben habe ist das Feld (char[][]), eine Liste von Point Objekten für die Positionen der Vögel und ein Point Objekt für die Position der Kanone.

Das ganze soll nur mithilfe von standard java klassen und methoden gelöst werden.

Ich weiß jetzt leider nicht wie ich hier rangehen soll.

Mein erster Versuch sah ungefähr so aus:

Ich setze eine winkel Variable auf 90.
Ich loope über die Vögel Liste und sammle jeden Vogel dessen aufgespannter Winkel vom Ursprung == winkel ist. Von diesen Vögeln "lösche" ich dann den nächstgelegenen Vogel aus. Danach wird der Winkel um 1 verringert.
Den Winkel berechne ich mit arctan2 (-Pi bis Pi) .

und überführe diesen dann ins 0-359° System.

Klappt das so? Theoretisch müsste es gehen, nur weiß ich nicht, ob die 1° Schrittweite für den Winkel der Kanone ausreicht, um die richtige Reihenfolge zu bewahren.

Hat jemand einen einfacheren Weg?

 

[mrBrown]

Hallo
Ich habe ein NxM grid auf welchem sich Vögel (chars) befinden. In der Mitte des Rasters liegt eine Kanone die nach Norden gerichtet ist.
So sieht das ganze aus.

.O....OOOOO...O..
OO...OO.OOOOO..OO
OOO..O...O.OOOOO.
..O.....X...OOO..
..O.O.....O....OO

'O' = Vogel
'X' = Kanone

Die Kanone bewegt sich im Uhrzeigersinn und kann immer nur 1 Vogel pro Schritt abschießen. Nachdem ein Vogel abgeschossen wurde, bewegt sich die Kanone einen Schritt nach rechts und visiert automatisch den nächsten Vogel an.

Die Reihenfolge für die ersten 9 Schüsse sieht so aus

.O....OOO24...O..
OO...OO.13O67..9O
OO...O...5.8OOOO.
..O.....X...OOO..
..O.O.....O....OO

Gesucht ist die Anzahl an vollen Umdrehungen die die Kanone durchführt um alle Vögel zu erschießen. Das ganze soll natürlich für jedes x-beliebige Grid genauso funktionieren.

Was ist in dem Fall "Norden", was "Rechts", und was soll eine Umdrehungen sein?

 

[lennero]

Was ist in dem Fall "Norden", was "Rechts", und was soll eine Umdrehungen sein?

Die Himmelsrichtung.

Die Kanone bewegt sich im Uhrzeigersinn und zeigt am Anfang nach Norden. Eine Umdrehung = 360° Drehung zum Ursprung.

 

[mrBrown]

Die Himmelsrichtung.

Und auf dem Raster ist das oben?

Die Kanone bewegt sich im Uhrzeigersinn und zeigt am Anfang nach Norden. Eine Umdrehung = 360° Drehung zum Ursprung.

Und wie weit soll sie sich drehen?

Und was soll der Schritt nach Rechts sein:

Nachdem ein Vogel abgeschossen wurde, bewegt sich die Kanone einen Schritt nach rechts

 

[lennero]

Und wie weit soll sie sich drehen?

Solange bis alle Vögel tot sind.

Und auf dem Raster ist das oben?

Ja

Und was soll der Schritt nach Rechts sein:

Das versuche ich herauszufinden. Der Anfangszustand ist, das die Kanone geradeaus nach oben zeigt. Sie befindet sich also in 90° Stellung. Wenn ich die Kanone bei einer Schrittweite von 1°, 90 mal nach rechts bewege, zeigt sie genau nach rechts (0° Stellung).

 

[lennero]

Habs so gut wie gelöst, vorgehensweise hab ich oben schon beschrieben. Die Ausgabe vom Programm unten sieht dann so aus:

Calculating optimal cannon position...
Done.
Optimal position: [22, 25]
Destroyed bird number 1 [22, 21] , at 0.0 Degrees.
Destroyed bird number 2 [23, 0] , at 2.290610042638521 Degrees.
Destroyed bird number 3 [23, 5] , at 2.862405226111745 Degrees.
Destroyed bird number 4 [23, 8] , at 3.366460663429793 Degrees.
Destroyed bird number 5 [23, 11] , at 4.085616779974873 Degrees.
Destroyed bird number 6 [23, 13] , at 4.763641690726179 Degrees.
Destroyed bird number 7 [24, 3] , at 5.194428907734808 Degrees.
Destroyed bird number 8 [24, 7] , at 6.34019174590991 Degrees.

Wen es interessiert:

public int run2() {
    System.out.println("Calculating optimal cannon position...");
    // this takes a few seconds to calculate...
    Point2d canonPosition = run1().k();
    System.out.println("Done.");
    System.out.println("Optimal position: " + canonPosition);

    Set<Point2d> birdPositions = getBirdPositions();
    int dx = -canonPosition.x();
    int dy = -canonPosition.y();

    // shift the coordinate system to turn the cannon position into the origin
    birdPositions = shiftOriginOfCoordinateSystem(birdPositions, dx, dy);

    // map bird positions to angles, 0° = north, 90° = east, 180° = south....
    List<Pair<Point2d, Double>> pointsAndAngles = new ArrayList<>();
    Point2d origin = new Point2d(0, 0);
    for (Point2d point : birdPositions) {
        if (!point.equals(origin)) {
            pointsAndAngles
                .add(new Pair<Point2d, Double>(point, StaticUtils.calcRotationAngleInDegrees(origin, point)));
        }
    }

    // sort by position
    pointsAndAngles.sort(new Comparator<Pair<Point2d, Double>>() {
        @Override
        public int compare(Pair<Point2d, Double> o1, Pair<Point2d, Double> o2) {
            Point2d origin = new Point2d(0, 0);
            int distanceFromOriginP1 = o1.k().distanceL1(origin);
            int distanceFromOriginP2 = o2.k().distanceL1(origin);
            if (distanceFromOriginP1 > distanceFromOriginP2) {
                return 1;
            }
            if (distanceFromOriginP1 < distanceFromOriginP2) {
                return -1;
            }
            return 0;
        }
    });
    // sort by angle
    pointsAndAngles.sort(Comparator.comparing(Pair::v));

    int index = 0;
    int count = 1;
    while (!pointsAndAngles.isEmpty()) {
        Pair<Point2d, Double> birdAnglePair = pointsAndAngles.get(index);
        if (onlyDuplicateValuesLeft(pointsAndAngles) || pointsAndAngles.size() == 1) {
            while (!pointsAndAngles.isEmpty()) {
                System.out.println("Destroyed bird number" + (count++) + " ["
                    + (pointsAndAngles.get(0).k().x() + (-dx)) + ", " + (pointsAndAngles.get(0).k().y() + (-dy))
                    + "] , at " + pointsAndAngles.get(0).v() + " Degrees.");
                pointsAndAngles.remove(0);
            }
        } else {
              System.out.println("Destroyed bird number " + (count++) + " ["
                    + (pointsAndAngles.get(index).k().x() + (-dx)) + ", " + (pointsAndAngles.get(index).k().y() + (-dy))
                    + "] , at " + pointsAndAngles.get(index).v() + " Degrees.");
               pointsAndAngles.remove(index);
               index = index % pointsAndAngles.size();
               while (birdAnglePair.v().equals(pointsAndAngles.get(index).v())) {
                   index = (index + 1) % pointsAndAngles.size();
                   if(onlyDuplicateValuesLeft(pointsAndAngles))
                       break;
                }
        }
    }
    return -1;
    }

 

[BestGoalkeeper]

Klappt das so? Theoretisch müsste es gehen, nur weiß ich nicht, ob die 1° Schrittweite für den Winkel der Kanone ausreicht, um die richtige Reihenfolge zu bewahren.

Die Schrittweite ergibt sich aus der Länge des Raster und beträgt double a = Math.toRadians(360.0 / n2 * i);, wobei int n2 = (n - 2) * 4 + 4;, also double a = Math.toRadians(360.0 / ((n - 2) * 4 + 4) * i); und n die Anzahl der Felder ist.
Beispiel:

import java.awt.Canvas;
import java.awt.Graphics;

import javax.swing.JFrame;
import javax.swing.WindowConstants;

public class Raster {
    private final int n = 5;

    public void showGrid() {
        JFrame f = new JFrame();
        Canvas c = new Canvas() {
            @Override
            public void paint(Graphics g) {
                for (int i = 0; i <= n; i++) {
                    g.drawLine(0, i * 40, n * 40, i * 40);
                }
                for (int i = 0; i <= n; i++) {
                    g.drawLine(i * 40, 0, i * 40, n * 40);
                }
                int n2 = (n - 2) * 4 + 4;
                int cx = (int) (n / 2.0 * 40.0);
                int cy = (int) (n / 2.0 * 40.0);
                int r = (int) ((n - 1) / 2.0 * 40.0);
                for (int i = 0; i < n2; i++) {
                    double a = Math.toRadians(360.0 / n2 * i);
                    g.drawLine(cx, cy, (int) (cx + r * Math.cos(a)), (int) (cy + r * Math.sin(a)));
                }
            }
        };
        f.add(c);
        f.setSize(250, 250);
        f.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
        f.setVisible(true);
    }

    public static void main(String[] args) {
        Raster r = new Raster();
        r.showGrid();
    }
}

Beispiel 5x5-Raster:


Beispiel 7x7-Raster:


Alles in allem aber eine sehr merkwürdige Frage und der Titel ist mangelhaft.

 

[BestGoalkeeper]

Also was ich damit sagen wollte... die Schrittweite kann auch < 1° sein.

 

[BestGoalkeeper]

und n die Anzahl der Felder ist

Moment, n ist die Dimension des Rasters, also die Anzahl der Felder die sich in einer Reihe befinden. Wenn man n-2 rechnet, dann hat man "den nächstkleineren Kreis". (Solange 1 < n gilt)

@lennero Wofür brauchst du das?

 

[lennero]

@lennero Wofür brauchst du das?

Für eine Aufgabe.

und die Schrittweite ist in meiner Lösung völlig egal da ich überhaupt nicht damit rechne. Ich berechne mit atan2 einfach alle Winkel, überführe diese ins standard 0-2pi System, sortiere nach Winkel und gehe ganz einfach die Liste durch. Außerdem wird nur der Mittelpunkt von jeder Zelle im Raster berücksichtigt. Alle Koordinaten sind Integer.

Hast aber recht, die Frage war blöd gestellt

 

[mrBrown]

Gesucht ist die Anzahl an vollen Umdrehungen die die Kanone durchführt um alle Vögel zu erschießen.

Und das ist die eigentliche Frage, die beantwortet werden soll?

wenn „Schrittweite“ auch 0 sein kann, dann ist’s eine Umdrehung (bzw. 359,99...)

wenn sie größer als 0 sein muss, dann so viele, wie Ziele von der Kanone aus in irgendeiner Richtung genau hintereinander angeordnet sind, minus 1. Für das Beispiel ganz oben zb 2 (da drei rechts neben der Kanone).

 

[lennero]

Und das ist die eigentliche Frage, die beantwortet werden soll?

Ne, ich hatte eigentlich keine spezifische Frage. Wollte wissen ob meine Vorgehensweise sich richtig angehört hat und ob es weitere Vorschläge gibt.

In diesem Beispiel braucht die Kanone genau eine Umdrehung um alle Ziele zu treffen.

..O..
O.X.O
..O..

In diesem Beispiel braucht sie 2 Umdrehungen

..O...
O.X.OO
..O...

Und in diesem Beispiel 3

.....O.
....O..
OOOX...
....O..
.....O.

 

[mrBrown]

In diesem Beispiel braucht die Kanone genau eine Umdrehung um alle Ziele zu treffen.

..O..
O.X.O
..O..

In diesem Beispiel braucht sie 2 Umdrehungen

..O...
O.X.OO
..O...

Und in diesem Beispiel 3

.....O.
....O..
OOOX...
....O..
.....O.

Wobei das nur angefangene Umdrehungen sind, volle Umdrehungen braucht’s es jeweils eine weniger.

 

[lennero]

Wobei das nur angefangene Umdrehungen sind, volle Umdrehungen braucht’s es jeweils eine weniger.

Ja das stimmt, sorry.

 

[BestGoalkeeper]

Außerdem wird nur der Mittelpunkt von jeder Zelle im Raster berücksichtigt.

Das ist völlig egal, weil ohnehin jede Zelle tangiert werden würde.

Naja, dann musst du deine Frage anders stellen - und vor allem hast du die Fragen von mrBrown noch nicht beantwortet... Wenn sich die "Kanone" beliebig drehen kann dann ist die Frage nach den benötigten Umdrehungen quatsch.

 

[lennero]

Naja, dann musst du deine Frage anders stellen

Nö. Bin schon fertig.

und vor allem hast du die Fragen von mrBrown noch nicht beantwortet...

Aha.

Wenn sich die "Kanone" beliebig drehen kann dann ist die Frage nach den benötigten Umdrehungen quatsch.

Und was lässt sich daraus schlussfolgern?

 

[BestGoalkeeper]

Du brauchst nicht bockig werden. Damit erreichst du bei mir nix.

 

[BestGoalkeeper]

Die Frage ist, ob sich die "Kanone" erst drehen muss und dann feststellen kann, ob dort ein Ziel ist - oder, ob sie die Ziele schon vorher kennt. (Dann wäre es natürlich ganz einfach). Die Frage ist auch, ob ein Raster (von dem du hier die ganze Zeit schreibst) überhaupt nötig ist - oder ob die Koordinaten der Ziele absolut sind...

Aber da du in den vorangegangenen Beiträgen unsere Fragen schon nicht beantwortet hast, rechne ich auch nicht mehr damit.