[QUIZ#04] zeja (Java)


zeja

Erfahrenes Mitglied
#1
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);
	}

}
 

zeja

Erfahrenes Mitglied
#2
Für Ofterschwang ergibt sich:
Code:
Ofterschwang
Maximale Länge von 641 auf 2 Strecken.
                                                                                                                                                                                                                                    [ 9]    
                                                                                                                                                                                                                                   3    [10]    
                                                                                                                                                                                                                               9    [12]       4    
                                                                                                                                                                                                                          12       7    [12]      12    
                                                                                                                                                                                                                      13      13    [10]    [14]      11    
                                                                                                                                                                                                                   6      11    [11]       8    [ 3]       7    
                                                                                                                                                                                                               7       7    [13]       4      14    [ 9]       8    
                                                                                                                                                                                                           7      13    [14]       4      11      13    [12]       7    
                                                                                                                                                                                                       3       6       6    [13]       3       9      13    [14]       7    
                                                                                                                                                                                                  14      14      10       3    [ 9]       3       4      10    [11]       5    
                                                                                                                                                                                              10      11       5       4       2    [ 9]       9       7      10    [13]      14    
                                                                                                                                                                                           2       5       5       3      11       2    [14]       5      11      14    [ 5]      10    
                                                                                                                                                                                       4      13       6       7       7       4    [ 4]       3       2      13      10    [ 9]      11    
                                                                                                                                                                                  14       2      10      13       4       2    [11]       8      11       6      10       6    [14]      12    
                                                                                                                                                                               7       3      12      14       3      10    [11]      14      11       4       9      14       3    [13]      12    
                                                                                                                                                                           5      14      14      11       9       9    [13]       8      13      12       8       8       7      10    [ 8]      13    
                                                                                                                                                                      11      13       4       7       3       4    [12]       7       8       6       7      11       4      11      14    [ 9]       6    
                                                                                                                                                                  14      13      13      14      14      12    [14]      13       4       2       7      12       9      14       2       4    [13]       7    
                                                                                                                                                              11      14       7      12       9       8    [ 5]       5      10      13       6      13      13       4       7       8       6    [10]       2    
                                                                                                                                                           7       6       7      12       7      14    [12]       8      11      13      10       9       5      14      12      12       5       9    [13]       6    
                                                                                                                                                       5       3       2       2       6      14    [12]       9       2      14      12       8      12       9       2      12       4      11       9    [ 3]      10    
                                                                                                                                                   2      12       3       7      12       7      12    [14]      10       3      12      14       8      11       7       3      11       4       3       2    [11]       9    
                                                                                                                                               4      12      14       6       4      11       7       8    [11]       2      12      10      11       4      10       5      10      12       5      11    [12]      11       3    
                                                                                                                                           6      12       4      13       6       2      12      12    [ 8]       5       9      11       7       8       3       6      14      12       6       4       9    [14]       2       4    
                                                                                                                                      10      12       3       4      12      10       8       9       6    [10]       7       6       3       4       8       4       7       5      13       5       7       3    [12]       7       7    
                                                                                                                                   7       9       5      12      14       7      10      10      11    [13]       5       8       9       5      10      11      14      10       6      10      10      14      13    [ 6]       8       9    
                                                                                                                               7      12      13      12       4       3       7       4       9       7    [ 9]       7      13       8       9      12       7       6      13      11       7       9       8      10    [ 8]      11      10    
                                                                                                                          13       4       4       5      13       7      11       8      12       3       5    [14]      11       5      13       9      12       8      11      13       3      12      13       2       4    [12]       5      13    
                                                                                                                      11      10       4       4       5       7      10       4       2       6       5    [14]      11       4       9       8       3      13       9      10       7       3      13       7       5       8    [13]       3       6    
                                                                                                                   7       2       9      12      13       5      12       2      10      10      12       4    [ 8]      11       5      11       7      14      12      13      10       6       2       2       3       4      12    [12]       3       5    
                                                                                                               6       7       6       6       6       9      12       2      11       2       7       7    [14]       5       2       5      10       4       5       2       9      13       2      12       3       8      10      14    [10]       4       5    
                                                                                                           7       7       2      14      12       3       9       8       5       3       4       9    [12]       7       3      13      11      11       7       2       6      10      12      12       8       9       9      13       4    [ 9]      12       4    
                                                                                                       2       4       2       5      12       9       6      14      11       9       2      13    [ 5]      12      13       5      11      10       6      10      13       2      13       9      11       7      10       4       2    [13]       9      10      12    
                                                                                                   4      11       6       6      10       2      12      11       8       8       5      12    [14]       8       4       8       2       6      11       8      14      14       2       5       2       8       3       9      11       4    [12]       5      10      14    
                                                                                               5      11      13       2       3      14      14      11       4       9       2       5    [14]      13       8      12       2      14       3       2      10       8       2      11       8       3      14       4       7       2      11    [11]      13       3      11    
                                                                                           7       5      12      11       3      11      11      10       7      13      11      14    [ 7]       3       9       2      13       3       7       2       4       2      13       7       6      12      12       9      11      14      11      13    [14]       3      12      10    
                                                                                       5       3      11      14       5      13       3       8       6      10       7       7       6    [11]       8      12      10      13      14      13       7      10       2      10       6       7       8      12       5       9       5       6      10    [12]       4       3       7    
                                                                                  13       5       8      11       7       3       2      12      10       6       7       2       4    [12]      12       5       4       9       6       9       2       5      13      13       7      13       6      11       8       2      14       3      11       7    [14]       4       5       2    
                                                                              12      12       3      14       3      13       6      10      13       4       9       8      13    [10]       2       8      11       7      13       2       7      14       8       4      13      11      10      11      12       7       7       4       9      14    [14]      10      10       2       7    
                                                                          14      12       8       4       5      13       7       7      10       7       5       8      11      11    [10]      11       4       2      13      10       5       4       9      12       5       6      11       8       3       9      11       2       6      11       3    [ 3]       3       5      14      10    
                                                                       9      14       4      11       9      12       6       5       9      11       8      12       9      11       7    [ 9]       7      13       4      10       8      10      14       8      11      11      12      12       3       9      14       5      14      14      12       5    [12]      12       6      14      11    
                                                                   6      13       9       5       8       6       4       3      12       3       9       8      11       5      12    [14]      13       5       5       6       6       6      10       8      11       3      11      10       6       7       4       3      12       7       3       6      11    [14]       5       9      12      13    
                                                               5       2       4       5       4      13       8      14       7      11       2       5       9       9       5       8    [12]       4       2       2      11       7       8       5      10       6      13      12       2       5      10       2       8       4       3      10       4      14    [13]      13       8      11       2    
                                                           9      11       6       8       3      14      11      11       2      10       8       7       7       2       3       6    [12]       9       4       2       8      11      11       6       9       2       7       9      13      10       3       6       2       4       3      10      11       8       6    [13]       6      13       8       9    
                                                       3      11       7       2      12       5      11       9       3       5       8       6       7      11       8       6       8    [12]       8       3      12       7      12      12      11      10       6      12       2       4      12       9       2      13      14       6       2      10       8    [13]       6       2      12       2      12    
                                                  14      11       8       6       7      11       2       6       4      12      10       2       8      11       6       6      13       3    [10]       6      11      12       7       8       2      14       6       5       3       5       6       5      13       2       2       6       9       7      12    [14]       9       6       9       4       2       7    
                                               8       8       8      11       4      14      14      10       2       9       8       3       7      12      13       5      10       4       2    [ 4]       6       9      12       7       5       4      11       4       4       8       4      10      12      11       3      12       8       6       6    [13]       4       9       6       9       3       3      12    
                                           2       5       6       9       6       9       8       9      14       8       6       3      14       6      10       7       3       5      14       9    [11]       3       6      10      14      14       9      14      14       4       4      13       7       6       8      14      14       4      11    [ 8]       5      11      12       9      13       2      13       3    
                                      10       5       8       6      13       7      14      13      10      10      14       5       8       2       6       7       6      13       6      13       2    [12]      14      12      14       5      10      12       6       6       9      14       6       9       6       3      11      13       8    [10]      11       6       4       9       7       6       6       4      11    
                                  13      13       3       4      11       8       6       6       8       4       7      14       8      14       6      14       4      14       6       6      13    [14]       4       2      14      11      10      11      13       6       6      11      12      12      13       8       3      13      11    [11]      10       9       9      14       8      12       6       6      12       8    
                               9      12      11       7       3       2       6       9      14       5       4       2       9       8       4      12       4      14      11       7      10      10    [ 6]       3       4       5       4       3       7       9      12       8       5       6      13       4       3       6       6    [11]       7       4      10       2      13       5       5      10       8       8      11    
                           3       7      11      12      14       2      10       4       8      10       2       8       2       2      14       8      14       5       3      12      13       2      13    [13]       6       2       7       5       4       9       6      14       9       6       3      13      12       6      13    [11]       3      12       4       8       4      13       4       8       4       3       7      11    
                       8       2       8      12       5      14      11       2       7      11       8       8      11       7       4      13       3      13       2       3      13       7      12       7    [13]      11       8       7      14       4       9       6       6      14      14       2       3      13       8       8    [11]      12      10       3       6      11       8      14       3      12       2      11      13    
                  12       6       9       2       6      11       9      10      11       7       3       6       9      12       8      13      11      11       6      11       9       8      13       6      10    [14]      10       6       8      12       6       5      12       2      14       2       5       9      13      10       7    [12]       7      14       2       4       2       6       6       3      10       5      14       8    
              12      13       8       3      14       2       2      10       4       3      11      10       2      12      13      12       3       5      13      11      11       7      11       2      13       3    [ 9]      14       2       2       3       7       7       5       3       3       8       5       2       9       6    [10]       3       3       3       2      10       5       7       5      11      14      10       5       6    
          10       2      13      13       8      12      12       2       9       2      12      10       5      11      13      12       8       5       6       9       3       5       2      11       2       7       4    [14]      14       3       2       7       4      10       5      12       4      10       2      12       4       6    [11]       5       6      12      10       7      14      10      13      12       3      12       6      14    
      11       2      12       7      10       5      13       7       2       6       6       8       9      12       9       9       5       2      14       8      13      14       3       6       6       3       9    [10]      14      12      11       5      12       7      12       7      13       6       8       6       3       5    [13]       2      10       7       2       4       4      11       9       6       5       5      12       5       9    
   8      10       5       8       2       2       4       7       4      10      10       7       5       2       4      12       8       5      12       4       8      10       2       2       5       6      10    [12]       2       2       8      12       3      12       4       3       3       8      13       9       3       4    [13]      12      11      12       9       8       3       6      11       9      11      11      11       6       2       7