Einträge aus Tupeln nach Regeln in Liste speichern

[AshCatchem]

Guten Abend zusammen, ich komme bei meiner Programmieraufgabe nicht weiter und benötige eure Hilfe.

Ich muss Wegpunkte einer Route hinzufügen. Diese Wegpunkte haben einen Nachbarn und sind gemeinsam mit deren Score in einem Objekt gespeichert. Dieses Tupel hat widerum einen Score.
Als aufgeschriebene Liste sähe das so aus :

Wegpunkte, Bewertung
(3,5), 100
(4,6), 91
(1,7) 87
(3,6) 80
(5,6) 77 usw.

Ich muss nun die Wegpunkte absteigend nach deren Score in die Route speichern. In diesem Fall also 3,5,6,4,...

Auf dem Papier kann ich das, aber ich bekomme es nicht in den PC. Das sortieren der Tupel nach deren Score ist kein Problem, allerdings komme ich bei den ganzen erforderlichen Schleifen und Bedingungen durcheinander, wenn es darum geht, die Route zu bilden. Kann mit jemand auf die Sprünge helfen? Ich würde gerne selbst auf die Lösung kommen.

Viele Grüße

 

[mihe7]

In diesem Fall also 3,5,6,4,...

Wie kommt man anhand der gezeigten Liste auf 3,5,6,4?

 

[httpdigest]

Meine Vermutung ist, dass die Pfadsegmente in beide Richtungen traversierbar sind, und sie nur in irgendeiner kanonischen Form aufgeschrieben werden mussten (also niedrigste Zahl zuerst). Ich nehme an, dass ein (a, b) dasselbe ist wie ein (b, a).
Das heißt: (3, 5) -> (5, 6) -> (4, 6). Der letzte wäre dann 6 -> 4.

 

[AshCatchem]

Entschuldigt bitte die unklare Formulierung. Sowie es httpdigest beschreibt, ist es richtig, allerdings mit einem entscheidenden Hinweis: Standorte befinden sich nur einmal in einer Route . Die Werte in den Klammern sind Indizes für Standorte. (a, b) entspricht (b, a) und es wird nach absteigendem Score sortiert. Weil man einen Ort nicht doppelt besucht, fliegt der natürlich raus. Ich habe deshalb auch diese "doppelten" Einträge in meinem sortierten Array erlaubt (anders als hier aufgeschrieben), damit das einfacher zu handhaben ist. Mir fällt bloß keine allgemeingültige Vorschrift ein, wie ich das umsetzen soll. Mein Ansatz wäre mit vielen if Verzweigungen und das gefällt mir gar nicht. Wie gehe ich sowas am besten an?

 

[httpdigest]

Wenn die Paare reflexiv sind, dann ist mir eigentlich nur unklar, woher du weißt, mit welchem Ort/Knoten genau angefangen werden soll. Das Pfadsegment (3, 5) kann ja heißen, dass mit 3 oder mit 5 angefangen werden kann. Und das wiederum bedingt, welche nächsten Pfadsegmente verwendet werden können, die unterschiedliche Scores haben können. Woher weißt du also am Anfang bei (3, 5), dass auch mit 3 -> 5 und nicht eben mit 5 -> 3 begonnen werden soll?

Der letzte Weg ist nicht von 6 zu 4, da 4 bereits in der Route vorkommt.

Ach nein? Wo kommt denn 4 schon vor, wenn nicht ganz am Schluss von 6 -> 4? Und wie kommst du dann auf 3,5,6,4?

 

[AshCatchem]

Hab's in meinem Post korrigiert, alles gut. Das ist ein berechtigter Einwand. Als erster Ansatz wird beim ersten Weg vorgeschrieben, dass dieser in aufsteigender Reihenfolge der Indizes abzulaufen hat.

 

[httpdigest]

Hier ist schonmal eine mögliche inperformante Lösung:

import static java.lang.Integer.compare;
import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;
import java.util.*;
public class Path {
  public static void main(String[] args) {
    // Repräsentation eines Pfadsegmentes
    class Segment implements Comparable<Segment> {
      int a, b, score;
      Segment(int a, int b, int score) {
        this.a = a;
        this.b = b;
        this.score = score;
      }
      // Zum Sortieren nach Score und kanonischer
      // Reihenfolge (a, b) mit a < b
      public int compareTo(Segment o) {
        int byScoreDesc = compare(o.score, score);
        int byA = compare(a, o.a);
        int byB = compare(b, o.b);
        return byScoreDesc != 0
            ? byScoreDesc
            : byA != 0 ? byA : byB;
      }
      public String toString() {
        return "(" + a + ", " + b + "), " + score;
      }
      // Zum Entfernen von Duplikaten
      public int hashCode() {
        return a ^ b;
      }
      // Zum Entfernen von Duplikaten
      public boolean equals(Object obj) {
        Segment other = (Segment) obj;
        return a == other.a && b == other.b
            || a == other.b && b == other.a;
      }
    }
    // Eingabeliste (wie vom ersten Post, nur
    // shuffled und mit (a, b) == (b, a) Duplikaten)
    List<Segment> segments = asList(
      new Segment(4, 6, 91),
      new Segment(5, 6, 77),
      new Segment(6, 3, 80),
      new Segment(1, 7, 87),
      new Segment(6, 5, 77),
      new Segment(5, 3, 100),
      new Segment(7, 1, 87),
      new Segment(3, 6, 80),
      new Segment(6, 4, 91),
      new Segment(3, 5, 100)
    ).stream()
     .sorted() // <- sortieren nach Score und nach (a, b) mit a < b
     .distinct() // <- Entfernen von Duplikaten (a, b) == (b, a)
     .collect(toList());
    // Erstes Pfadsegment ist immer das mit
    // dem höchsten Score
    Segment first = segments.remove(0);
    // Erzeuge mutable result Liste mit initial
    // a -> b aus dem ersten Pfadsegment
    List<Integer> result = new ArrayList<>(
        asList(first.a, first.b)
    );
    // next enthält immer den als nächstes zu suchenden Startpunkt
    int next = first.b;
    // Ermittle alle nachfolgenden Pfadsegmente
    do {
      final int n = next;
      Integer i = segments
          .stream()
          // Ermittle erstes/höchstes Pfadsegment mit passendem Startpunkt
          .filter(s -> s.a == n && !result.contains(s.b)
                    || s.b == n && !result.contains(s.a))
          .findFirst()
          .map(s -> s.a == n ? s.b : s.a) // <- Endpunkt
          .orElse(null); // <- nichts mehr gefunden. Ende!
      if (i == null)
        break;
      result.add(next = i);
    } while (true);
    // Ergebnis ausgeben
    System.out.println(result);
  }
}

 

[AshCatchem]

Danke für die Antwort, die Lösung sieht echt Klasse aus. Ich werde versuchen, die auf meine Art und Weise in meinen Code zu integrieren, aber ich habe noch einige Fragen. 1. Hast du Tipps, wie man seine Gedanken besser in Code bekommt? Dadurch, dass ich das auf dem Papier lösen kann, weiß ich ja, worum es geht. Wie formuliert man die einzelnen Schritte am besten? Kann man das einfach, muss man das lernen oder gibt es dafür Methoden? Ich bin echt beeindruckt, dass du das so schnell aus dem Ärmel geschüttelt hast. Ich hab da gestern den ganzen Tag dran gesessen und es nicht hinbekommen. Und ich will auch nicht als Ausrede nehmen, dass ich kein Informatiker bin.
2. Gehören deine genutzten Methoden in den Werkzeugkasten eines Anfängers oder ist das eher Wissen für Fortgeschrittene? Ich sehe bei dir keine einzige Schleife mit Laufvariable. Ich hab bei einem Ansatz 3 for Schleifen genutzt. Vermutlich denke ich noch zu kompliziert, aber das spornt mich irgendwie an, mich dahingened weiterzubilden. Ich war selten so oft davor, irgendwas hinzuschmeißen wie bei dem Projekt, obwohl das an sich ja echt leicht zu sein scheint. Wie lernt man am besten, so pragmatisch zu programmieren?

Viele Grüße

 

[httpdigest]

Hast du Tipps, wie man seine Gedanken besser in Code bekommt? Dadurch, dass ich das auf dem Papier lösen kann, weiß ich ja, worum es geht. Wie formuliert man die einzelnen Schritte am besten? Kann man das einfach, muss man das lernen oder gibt es dafür Methoden?

Du brauchst dafür ein Verständnis für grundlegende algorithmische Primitive. Im Studium beginnt man dafür meist mit Nassi-Shneidermann-Diagrammen.
Deine Aussage, du hast es auf dem Papier bereits gelöst, ist ja beliebig interpretierbar. Es kann heißen, dass du einfach nur deine Eingabeliste hingeschrieben hast und dann grafisch Pfeile vom 1. zum 2. zu verwendenden Wegpunkt, dann zum 3. und dann zum 4. gezogen hast und vielleicht noch eine Notiz "Erst das, dann das und dann den hier" geschrieben hast. Das ist natürlich noch kein Algorithmus, da es keine klar strukturierten Anweisungen enthält.
Bezüglich Methoden/Techniken, kenne ich eigentlich nur Abstraktion und Dekomposition. Google die mal.

Und ich will auch nicht als Ausrede nehmen, dass ich kein Informatiker bin.

Das wäre ehrlich gesagt aber eine sehr gute Ausrede. Ein M.Sc. Informatikstudium zum Beispiel dauert ja nicht ohne Grund mindestens 5 Jahre.

Gehören deine genutzten Methoden in den Werkzeugkasten eines Anfängers oder ist das eher Wissen für Fortgeschrittene? Ich sehe bei dir keine einzige Schleife mit Laufvariable.

Da wären wir bei dem Thema Abstraktion. In der genutzten Stream API von Java verstecken sich die Schleifen. Da eine Schleife zu sehen das Ganze meiner Meinung nach aber nur komplizierter zu verstehen macht, da man die Laufvariablen (sprich: den Zustand) hier und dort immer im Kopf haben muss, habe ich einfach eine Möglichkeit gewählt, von der tatsächlichen Iteration zu abstrahieren, damit das tatsächliche Problem erkennbar wird (nämlich das Finden des ersten Pfadsegmentes, das mit seinen Endpunkten passt). Aber ich würde sagen, solche funktionale Programmierung ist definitiv Fortgeschrittenen-Niveau.

Ich war selten so oft davor, irgendwas hinzuschmeißen wie bei dem Projekt, obwohl das an sich ja echt leicht zu sein scheint. Wie lernt man am besten, so pragmatisch zu programmieren?

Versuche dich vielleicht an einfacheren Problemen (deins war schon ein bisschen von der Sorte "für Fortgeschrittene"). Und dann einfach viiiieele viiieeele Jahre üben üben und nochmals üben.