zeja
Erfahrenes Mitglied
Die Piste wird in einen binären Baum eingelesen. Die Ermittlung des längsten Pfades erfolgt dann von den Blattelementen zum Wurzelelement durch die Ermittlung des jeweils längsten Pfades unter dem aktuellen Element. Alternativen werden berücksichtigt.
Java:
package de.tutorials.quiz.pistenjodler;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Pistenjodler {
public static void main(String[] args) throws IOException {
final File f = new File("pisten.txt");
// Pisten einlesen
final BufferedReader br = new BufferedReader(new FileReader(f));
// Pistenname auf Pisteninfos
final Map<String, Piste> pisten = new HashMap<String, Piste>();
String name;
// Bis Ende der Datei oder Leerzeile einlesen
while ((name = br.readLine()) != null && !name.trim().equals("")) {
// Zeilen des Baums
final int numRows = Integer.parseInt(br.readLine());
// Array zum leichteren aufbauen des Baums
final Tree arr[][] = new Tree[numRows][numRows];
int maxLength = 0;
// alle Zeilen einlesen
for (int i = 0; i < numRows; i++) {
final String line = br.readLine();
final Tree previous[] = i != 0 ? arr[i - 1] : null;
final Tree current[] = arr[i];
final String[] times = line.split(" ");
// Über die Einträge der Zeile iterieren
for (int y = 0; y < i + 1; y++) {
final String num = times[y].trim();
// maximale Länge der Zahlen im Baum ermitteln
maxLength = Math.max(maxLength, num.length());
// Neues Baumelement erstellen
final Tree elem = new Tree(Integer.parseInt(num));
// Sofern es sicht nicht um das Wurzelelement
// handelt linken und rechten Baum des übergeordneten
// Elements setzen
if (i != 0) {
// Nur wenn es linkes Element gibt
if (y < i) {
previous[y].setLeft(elem);
}
// Nur wenn es rechtes Element gibt
if (y != 0) {
previous[y - 1].setRight(elem);
}
}
// In aktuelle Zeile des Array eintragen
current[y] = elem;
}
}
// Neue Piste aus den Daten erstellen und der Map hinzufügen
final Piste p = new Piste(name.trim(), numRows, arr, maxLength);
pisten.put(name.trim(), p);
}
for (final Piste piste : pisten.values()) {
final PathLength result = recursiveDepthSearch(piste);
System.out.println(piste.getName() + " " + result.getLength()
+ " (" + result.getNumberOfAlternatives() + ")");
// print(piste, result);
}
// Beispielpiste mit 2 gleich langen Alternativen ausgeben
final Piste piste = pisten.get("Ofterschwang");
final PathLength result = recursiveDepthSearch(piste);
print(piste, result);
}
/**
* Versucht die längsten Abfahrten für die Piste zu finden, indem der Baum
* von den Blättern aufwärts mit Informationen über den längsten Pfad
* versehen wird.
*
* @param piste Die Piste
* @return Das Suchergebnis.
*/
private static PathLength recursiveDepthSearch(final Piste piste) {
final Tree root = piste.getTree();
final Map<Tree, PathLength> map = new HashMap<Tree, PathLength>();
final PathLength result = search(root, map);
// Rückwärtige Pfade umdrehen
result.reversePaths();
return result;
}
private static PathLength search(final Tree tree,
final Map<Tree, PathLength> map) {
// Ist noch keine Länge für diesen Teilbaum berechnet worden
if (!map.containsKey(tree)) {
// Gibt es Kindknoten?
if (tree.hasChildren()) {
// Längen für den linken und rechten Teilbaum ermitteln
final PathLength leftLength = search(tree.getLeft(), map);
final PathLength rightLength = search(tree.getRight(), map);
final PathLength pathLength;
// Linker Baum hat längeren Pfad
if (leftLength.getLength() > rightLength.getLength()) {
pathLength = new PathLength(tree, leftLength);
}
// Beide Bäume haben gleich lange Pfade.
// Es entsteht eine Alternative.
else if (leftLength.getLength() == rightLength.getLength()) {
pathLength = new PathLength(tree, leftLength, rightLength);
}
// rechter Baum hat längere Pfad
else {
pathLength = new PathLength(tree, rightLength);
}
// Das Ergebnis der Map hinzufügen
map.put(tree, pathLength);
return pathLength;
} else {
// Es handelt sich um einen Blattknoten.
final PathLength pathLength = new PathLength(tree);
map.put(tree, pathLength);
return pathLength;
}
} else {
// Zuvor berechnetes Ergebnis zurückgeben
return map.get(tree);
}
}
/**
* Gibt die Piste als Baum aus und markiert optional die längsten Strecken.
*
* @param piste Die Piste.
* @param result Die Ergebnisse.
*/
private static void print(final Piste piste, final PathLength result) {
System.out.println(piste.getName());
if (result != null) {
System.out.printf("Maximale Länge von %d auf %d Strecken.%n",
result.getLength(), result.getNumberOfAlternatives());
// for (int i = 0; i < result.getNumberOfAlternatives(); i++) {
// System.out.println(result.getPath(i));
// }
}
// Für die Ausgabe das Array verwenden. Dies ist einfacher
// als über den Baum
final Tree[][] tree = piste.getArray();
// Zeichenbreiten dieses Baums für ordentlich formatierte
// Ausgaben
int maxLength = piste.getMaxLength();
// Wenn es sich um ein Ergebnis handelt um 2 für die Markierungen
// erhöhen
if (result != null) {
maxLength += 2;
}
// Einzug für das erste Element des Baums berechnen
final int initialIndent = (piste.getRows() - 1) * maxLength;
// Über die Alternativen iterieren, wenn vorhanden
int forCnt = result == null ? 1 : result.getNumberOfAlternatives();
int indent = initialIndent;
// Über die Zeilen iterieren
for (int i = 0; i < piste.getRows(); i++) {
final Tree[] row = tree[i];
// Zu markierendes Element für diese Zeile ermitteln
// final Tree mark = result == null ? null : path.get(i);
final List<Tree> mark = new ArrayList<Tree>();
if (result != null) {
for (int f = 0; f < forCnt; f++) {
final List<Tree> path = result.getPath(f);
mark.add(path.get(i));
}
}
// Leerzeichen für Einrückung ausgeben
if (indent != 0) {
System.out.printf("%" + indent + "s", " ");
}
// Über die Element des Baums in dieser Zeile iterieren
for (int y = 0; y < i + 1; y++) {
final Tree current = row[y];
// Element markieren
if (mark.contains(current)) {
System.out.printf("[%" + (maxLength - 2) + "d]" + "%"
+ maxLength + "s", current.getLabel(), " ");
}
// nur ausgeben
else {
System.out.printf("%" + maxLength + "d" + "%" + maxLength
+ "s", current.getLabel(), " ");
}
}
// Zeilenwechseln und Einzug dekrementieren
System.out.println("");
indent -= maxLength;
}
}
}
Java:
package de.tutorials.quiz.pistenjodler;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Enthält aktuellen Teilbaum, die Länge des Pfades bis zu diesem Teilbaum und
* alle möglichen Pfade mit dieser Länge.
*
*/
class PathLength {
/**
* Der aktuelle Teilbaum.
*/
private final Tree tree;
/**
* Die Länge bis zu diesem Teilbaum.
*/
private final int length;
/**
* Die möglichen Pfad mit der Länge.
*/
private final List<List<Tree>> alternativePaths = new ArrayList<List<Tree>>();
/**
* Erstellt einen neuen Pfad mit dem aktuellen Element.
*
* @param tree Ein Wurzel- oder Blattknoten.
*/
public PathLength(final Tree tree) {
this.tree = tree;
this.length = tree.getLabel();
// Neuen Pfad mit diesem Element erstellen und als einzige
// Alternative hinzufügen
final List<Tree> path = Collections.singletonList(tree);
alternativePaths.add(path);
}
/**
* Fügt dem bisherigen Pfad ein Element hinzu.
*
* @param tree Das hinzuzúfügende Element.
* @param previous Die bisherigen Pfade gleicher Länge.
*/
public PathLength(final Tree tree, final PathLength... previous) {
// Über die bisherigen Pfade iterieren
// und neuen Pfad mit aktuellem Element erstellen
for (PathLength l : previous) {
for (List<Tree> t : l.alternativePaths) {
final List<Tree> path = new ArrayList<Tree>(t);
path.add(tree);
alternativePaths.add(path);
}
}
this.tree = tree;
// Länge aktualisieren
this.length = previous[0].length + tree.getLabel();
}
/**
* Dreht alle alternativen Pfade um.
*/
public void reversePaths() {
for (List<Tree> path : alternativePaths) {
Collections.reverse(path);
}
}
public Tree getTree() {
return tree;
}
public int getLength() {
return length;
}
public boolean hasAlternatives() {
return alternativePaths.size() > 1;
}
public int getNumberOfAlternatives() {
return alternativePaths.size();
}
public List<Tree> getPath() {
return getPath(0);
}
public List<Tree> getPath(int num) {
return alternativePaths.get(num);
}
public String toString(){
return "(" + length + ")" + alternativePaths;
}
}
Java:
package de.tutorials.quiz.pistenjodler;
public class Piste {
private final String name;
private final Tree[][] arr;
private final int rows;
private final int maxLength;
private final Tree tree;
public Piste(String name, int rows, Tree[][] arr, int maxLength) {
this.name = name;
this.rows = rows;
this.arr = arr;
this.tree = arr[0][0];
this.maxLength = maxLength;
}
public String getName() {
return name;
}
public Tree[][] getArray() {
return arr;
}
public Tree getTree() {
return tree;
}
public int getRows() {
return rows;
}
public int getMaxLength() {
return maxLength;
}
}
Java:
package de.tutorials.quiz.pistenjodler;
public class Tree {
private final int label;
private Tree left;
private Tree right;
public Tree(int label) {
this.label = label;
}
public boolean hasChildren() {
return left != null && right != null;
}
public int getLabel() {
return label;
}
public Tree getLeft() {
return left;
}
public Tree getRight() {
return right;
}
public void setLeft(Tree left) {
this.left = left;
}
public void setRight(Tree right) {
this.right = right;
}
public String toString() {
return Integer.toString(label)+"/"+System.identityHashCode(this);
}
}
