Alle Ziele in einem Raster abknallen

lennero

Bekanntes Mitglied
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.

Code:
.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

Code:
.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

Super-Moderator
Mitarbeiter
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.

Code:
.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

Code:
.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?
 

mrBrown

Super-Moderator
Mitarbeiter

lennero

Bekanntes Mitglied
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

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

Code:
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:

Java:
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;
    }
 
B

BestGoalkeeper

Gast
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:
Java:
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:
1600160576781.png

Beispiel 7x7-Raster:
1600160640957.png

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

lennero

Bekanntes Mitglied
@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

Super-Moderator
Mitarbeiter
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

Bekanntes Mitglied
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.
Code:
..O..
O.X.O
..O..

In diesem Beispiel braucht sie 2 Umdrehungen
Code:
..O...
O.X.OO
..O...

Und in diesem Beispiel 3
Code:
.....O.
....O..
OOOX...
....O..
.....O.
 

mrBrown

Super-Moderator
Mitarbeiter
In diesem Beispiel braucht die Kanone genau eine Umdrehung um alle Ziele zu treffen.
Code:
..O..
O.X.O
..O..

In diesem Beispiel braucht sie 2 Umdrehungen
Code:
..O...
O.X.OO
..O...

Und in diesem Beispiel 3
Code:
.....O.
....O..
OOOX...
....O..
.....O.
Wobei das nur angefangene Umdrehungen sind, volle Umdrehungen braucht’s es jeweils eine weniger.
 
B

BestGoalkeeper

Gast
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

Bekanntes Mitglied
B

BestGoalkeeper

Gast
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Warum wird hier nur etwas in eine txt Datei geschrieben und nicht in alle drei (InputStream/OutputStream/Reader/Writer) Java Basics - Anfänger-Themen 1
H Nutzt Eclipse alle CPU-Threads beim Ausführen von Java-Programmen? Java Basics - Anfänger-Themen 4
B Alle Strings bis zu einer Maimallänge aufzählen, die Bedingung erfüllen Java Basics - Anfänger-Themen 13
D Apache HTTPClient für alle Fälle Java Basics - Anfänger-Themen 41
missy72 Methoden Alle rekusiven Aufrufe abbrechen Java Basics - Anfänger-Themen 21
S IntelliJ geht alle Klassen durch Java Basics - Anfänger-Themen 9
B Alle Zahlen finden, die 3 bestimmte Ziffern enthalten? Java Basics - Anfänger-Themen 9
K wie kann ich alle Attribute von dem Objekt(pagode) ausgeben lassen ? Java Basics - Anfänger-Themen 3
I Greenscreen, funktioniert nicht zu 100%... nicht alle Pixel werden geändert Java Basics - Anfänger-Themen 1
Butzibu Image Loader lädt nicht alle Bilder: Java Basics - Anfänger-Themen 4
sserio Wieso werden nicht alle Primzahlen bis 1000 in meine Liste gepackt ? Java Basics - Anfänger-Themen 8
E Select nimmt nicht alle Where /AND befehlen an Java Basics - Anfänger-Themen 4
K Erste Schritte Wie schnell ist LinkedHashMap im Vergleich zur ArrayList, wenn alle Entries durchlaufen werden? Java Basics - Anfänger-Themen 47
R Methoden Eclipse schlägt mir nicht alle Möglichkeiten vor Java Basics - Anfänger-Themen 4
melisax Alle Möglichkeiten eines Wortes angeben Java Basics - Anfänger-Themen 3
B Programm, dass alle 3 Tage eine Webseite öffnet? Java Basics - Anfänger-Themen 20
J Alle .java Dateien von einem Verzeichnis in eine Zip speichern Java Basics - Anfänger-Themen 2
J Alle Dateien aus einem Verzeichnis laden Java Basics - Anfänger-Themen 10
Bademeister007 Operatoren Alle Zahlen einer ArrayList die durch 5 teilbar ist Java Basics - Anfänger-Themen 2
E Wie gebe ich alle Daten zwischen zwei Zeitpunkten aus? Java Basics - Anfänger-Themen 2
crrnogorka Letzte Zeile einer Tabelle "überschreibt" alle anderen Zeilen Java Basics - Anfänger-Themen 1
C alle möglichen Kombinationen zweier Ziffern auf drei / vier / und 'n" Stellen Java Basics - Anfänger-Themen 11
H Alle Geraden zahlen bis 10 ausgeben Java Basics - Anfänger-Themen 11
J Alle Werte eines Strings zusammen addieren Java Basics - Anfänger-Themen 15
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
B Alle Links in einem Text suchen und ersetzen mit einem neuen Link Java Basics - Anfänger-Themen 18
K Array alle Werte aufsummieren und ausgeben Java Basics - Anfänger-Themen 6
Dimax Erste Schritte String replace alle Zeichen Java Basics - Anfänger-Themen 10
L Wie vergrößere ich ein Rechteck in alle Richtungen um eins und bekomme dessen Rand? Java Basics - Anfänger-Themen 2
L Breadth-First Search statt einem Pfad, alle Pfade herausfinden Java Basics - Anfänger-Themen 4
X Erste Schritte String: Alle doppelten Leerzeilen entfernen Java Basics - Anfänger-Themen 21
M Regex-Ausdruck: Alle Zeichen bis auf ein bestimmtes erlauben (p{L}) Java Basics - Anfänger-Themen 5
I Alle Elemente von zwei Listen vergleichen Java Basics - Anfänger-Themen 1
Kirby.exe Alle möglichen Error Möglichkeiten abfangen Java Basics - Anfänger-Themen 33
M Unterklasse soll nicht alle Methoden erben Java Basics - Anfänger-Themen 3
V Erste Schritte for-Schleife; Ausgabe soll alle 5 Sekunden erfolgen. Java Basics - Anfänger-Themen 4
A Alle true Werte eines boolean Arrays herausfiltern Java Basics - Anfänger-Themen 19
D Alle Möglichkeiten, n-Anzahl aus Elementen aus einem Array zu wählen, ausgeben? Java Basics - Anfänger-Themen 23
M prüfen ob alle array werte gleich sind Java Basics - Anfänger-Themen 27
F Alle Zeichenkombinationen eines Strings iterativ herausfinden Java Basics - Anfänger-Themen 26
L Classpath Alle Dateien im Classpath finden Java Basics - Anfänger-Themen 4
G Überprüfen ob alle Ziffern von 1-9 in einem Integer vorhanden sind Java Basics - Anfänger-Themen 6
J Erste Schritte Alle möglichen ausgaben von 5 Zahlen als Vector Java Basics - Anfänger-Themen 7
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
D Methoden Eigene Methode um alle Ausgaben aufzurufen Java Basics - Anfänger-Themen 17
F Ordner auf alle Unterdatein abfragen Java Basics - Anfänger-Themen 3
A In einem String alle Eigennamen zählen Java Basics - Anfänger-Themen 6
B Klassen Alle Unter-Objekte durchlaufen in der Hauptklasse Java Basics - Anfänger-Themen 10
W ArrayList löscht alle Elemente bis auf eines Java Basics - Anfänger-Themen 2
B Webservice -> alle parameter bekommen von form Java Basics - Anfänger-Themen 2
das_leon Alle Zeilen einer CSV-Datei auslesen Java Basics - Anfänger-Themen 1
C HashMap - alle keys haben values der letzten put-Anweisung Java Basics - Anfänger-Themen 3
F Eclipse alle Projekt weg Java Basics - Anfänger-Themen 6
V Alle Komponenten eines JPanels Java Basics - Anfänger-Themen 14
I gemeinsame Config-Datei für alle Windows-User Java Basics - Anfänger-Themen 5
H JButton - Wechsel der Textfarbe alle 500ms Java Basics - Anfänger-Themen 10
DaCrazyJavaExpert Alle Zahlenkombinationen aus 9 zahlen finden Java Basics - Anfänger-Themen 17
F Alle Objekte einer Klasse nach Eigenschaft durchsuchen Java Basics - Anfänger-Themen 8
M Alle Instanzen einer Klasse ansprechen Java Basics - Anfänger-Themen 4
S Problem: Array alle Einträge gleich Java Basics - Anfänger-Themen 10
Z Enter Taste alle 0,5 Sekunden ausführen Java Basics - Anfänger-Themen 1
U RegEx alle Kommas bei den Zahlen in Punkt umwandeln Java Basics - Anfänger-Themen 3
K alle Vorkommen einer bestimmten Ziffer in einer Zahl zählen Java Basics - Anfänger-Themen 2
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
C Alle Zweierpotenzen bis 2^10 ausgeben lassen Java Basics - Anfänger-Themen 15
B Alle Attribute von Klasse bekommen und ändern Java Basics - Anfänger-Themen 12
M Input/Output Alle Zeilen auslesen und in Variable speichern Java Basics - Anfänger-Themen 5
W Mozilla Thunderbird email an alle Kontakte Java Basics - Anfänger-Themen 3
F Methode alle 15min ausführen Java Basics - Anfänger-Themen 5
D Alle möglichen Kombinationen in einem Array ausgeben Java Basics - Anfänger-Themen 2
I Alle Laufwerke und deres Pfade ausgeben Java Basics - Anfänger-Themen 6
S Classpath: Alle .jars innerhalb eines Ordners einbinden Java Basics - Anfänger-Themen 4
G Alle Objekte und Variablen automatisch ausgeben Java Basics - Anfänger-Themen 7
I Programm, welches eine Textzeile einliest und alle darin enthaltenen Buchstaben umwandelt Java Basics - Anfänger-Themen 3
G Wie bekomme ich alle Ausgaben von runTime.exec() Java Basics - Anfänger-Themen 7
L Best Practice Alle Kombinationen aus Listenelementen, Anzahl Listen unterschiedlich Java Basics - Anfänger-Themen 6
M Compiler-Fehler Alle Methoden eines Interfaces Implementiert dennoch Fehler Java Basics - Anfänger-Themen 3
I Alle Zeitzonen in Liste speichern Java Basics - Anfänger-Themen 4
F alle 100ms Befehle ausführen Java Basics - Anfänger-Themen 26
M Alle Sublisten einer bestimmten Laenge berechnen Java Basics - Anfänger-Themen 2
F Alle DEMOS fast veraltet...? Java Basics - Anfänger-Themen 13
J Alle Leerzeichen aus String entfernen Java Basics - Anfänger-Themen 13
D Methoden Alle Siebenstelligen Primpalidrome von PI Java Basics - Anfänger-Themen 6
K Durch alle Attribute eines Objektes iterieren Java Basics - Anfänger-Themen 6
P Klassen Alle Strings einer ArrayList<eigeneKlasse> anspre Java Basics - Anfänger-Themen 2
W String von hinten alle drei Zeichen abschneiden und in umgekehrter Reihenfolge ausgeben. Java Basics - Anfänger-Themen 9
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
M Alle möglichen Strings Java Basics - Anfänger-Themen 5
J Alle Wörter der Länge n mit 0 und 1 Java Basics - Anfänger-Themen 17
T Alle Threads .notify() Java Basics - Anfänger-Themen 13
G Methoden Alle Objekte der ArrayList ausgeben funktioniert nicht. Java Basics - Anfänger-Themen 12
N Klassen Class nur einmal ausführen und sie speichert daten für alle anderen classes? Java Basics - Anfänger-Themen 3
M Klassen Auf Alle Array Methoden gleichzeitig zugreifen Java Basics - Anfänger-Themen 8
D Frame schließt gleich alle Frames Java Basics - Anfänger-Themen 5
T Wie mache ich einen Timer der alle 2 sekunden aufgerufen wird? Java Basics - Anfänger-Themen 5
G JFileChooser "alle Dateien" unterbinden Java Basics - Anfänger-Themen 3
S Aus zwei Dateipfaden alle Dateien auslesen Java Basics - Anfänger-Themen 11
B Frage zur Effizienz - alle Array-Felder initialisieren oder jedes Feld auf null prüfen? Java Basics - Anfänger-Themen 4
F Geht in alle Case rein, warum?? Java Basics - Anfänger-Themen 12
R Alle Klassen ermitteln, die Interface implementieren / Reflection Java Basics - Anfänger-Themen 51

Ähnliche Java Themen

Neue Themen


Oben