Aufgabe 6.3

Bachelor Algorithmen und Datenstrukturen
1

Skyline

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Aufgabe 6.3
Hi,

ich habe bei Aufgabe 6.3 ein paar eigene Testfälle ergänzt und dabei folgendes Verhalten des Programms entdeckt:

Testfälle:

		System.out.println("linke Towerwand doppelt");
		System.out.println(Arrays.toString(conquer(new int[][] {{1,11,5}, {2,6,7}, {3,13,9}})));
		System.out.println(Arrays.toString(conquer(new int[][] {{1,11,5}, {1, 5, 8}, {2,6,7}, {3,13,9}})));
		
		System.out.println("innenliegende Towerwand doppelt");
		System.out.println(Arrays.toString(conquer(new int[][] {{1,11,5}, {2,6,7}, {3,13,9}})));
		System.out.println(Arrays.toString(conquer(new int[][] {{1,11,5}, {2,5,8}, {2,6,7}, {3,13,9}})));
		
		System.out.println("rechte Towerwand doppelt");
		System.out.println(Arrays.toString(conquer(new int[][] {{1,11,5}, {2,6,7}, {3,13,9}})));
		System.out.println(Arrays.toString(conquer(new int[][] {{1,11,5}, {2,5,9}, {2,6,7}, {3,13,9}})));

Ausgabe:

linke Towerwand doppelt
[1, 11, 3, 13, 9, 0]
[1, 5, 1, 11, 3, 13, 9, 0]
innenliegende Towerwand doppelt
[1, 11, 3, 13, 9, 0]
[1, 11, 3, 13, 9, 0]
rechte Towerwand doppelt
[1, 11, 3, 13, 9, 0]
[1, 11, 3, 13, 9, 5, 9, 0]

D.h. ich habe bei allen drei Beispielen einen “für die Skyline redundanten Tower” hinzugefügt. Berührt dieser jedoch die linke oder rechte Außengrenze der Skyline, so wird in der konsolidierten Skyline ein weiterer Tower mit Breite 0 ergänzt.

Meines Achtens liegt dies an merge() - tritt das bei euren Lösungen ebenfalls auf?

3

Per Spezifikation folgt immer ein ‘leeres’ Gebäude, also die ganzen Häuser folgt eine weitere Koordinate mit der Höhe 0. Das muss übrigens immer so sein. Müsstest du bei der Implementierung der [m]area[/m] Methode gemerkt haben (und auch im vorgegebenem Testfall der [m]merge[/m] Methode).

4

Das Problem liegt an merge und genauer gesagt daran, dass man niemals gesondert den Fall if(left[l] == right[r]) abfragt.

edit: ich glaube, diese merge-Methode macht es besser.

public static int[] merge(int[] left, int[] right) {		
		ArrayList<Integer> internalRep = new ArrayList<>();
		int l = 0, r = 0;
		int lHeight = 0, rHeight = 0;
		while (l < left.length && r < right.length) {		
			if (left[l] < right[r]) {				
				add(internalRep, left[l], Math.max(left[l + 1], rHeight));
				lHeight = left[l + 1];
				l += 2;
			} else if (left[l] > right[r]) {
				add(internalRep, right[r], Math.max(right[r + 1], lHeight));
				rHeight = right[r + 1];
				r += 2;
			} else {
				if(left[l + 1] > right[r + 1]) {
					add(internalRep, left[l], Math.max(left[l + 1], rHeight));
					lHeight = left[l + 1];
					l += 2;
				} else {
					add(internalRep, right[r], Math.max(right[r + 1], lHeight));
					rHeight = right[r + 1];
					r += 2;
				}
			}
		}
		while (l < left.length) {
			add(internalRep, left[l], left[l + 1]);
			l += 2;
		}
		while (r < right.length) {
			add(internalRep, right[r], right[r + 1]);
			r += 2;
		}
		int[] ret = new int[internalRep.size()];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = internalRep.get(i);
		}
		return ret;
	}
5

Thx.
Hi,

@AnNyan: Thx für deine Rückmeldung. Das ist grundsätzlich natürlich richtig, jedoch geht es mir darum, dass zusätzlich noch ein weiteres Gebäude erscheint (vgl. jeweils die 2. Zeile im ersten und letzten Block). Das sollte nach Spezifikation so meines Achtens nicht sein.

@Chayyam: Damit ist im ersten Fall (linke Grenze der konsolidierten Skyline) das “leere” Gebäude weg - thx für die Info! Rein für die Abgabe gehe ich einfach mal davon aus, dass wir an der gegebenen Methode nichts manipulieren sollten, für meine “Spielecke” in Eclipse (bzw. mein Verständnis) ist deine Methode aber um so interessanter. :slight_smile:

6

Richtig, manipulieren soll man lieber nichts. Und eigentlich ist meine Methode auch nicht optimal, es fehlt der Fall left[l+1] = right[r+1]. Funktioniert die Methode bei dir in den anderen Testfällen?

7

Ich erhalte mit deiner Version korrekte Ergebnisse für die gegebenen und eigenen Testfälle (außer eben dem letzten oben aufgeführten).

D.h. anstelle der oben angegebenen Ergebnisse erscheint:

linke Towerwand doppelt
[1, 11, 3, 13, 9, 0]
[1, 11, 3, 13, 9, 0]
innenliegende Towerwand doppelt
[1, 11, 3, 13, 9, 0]
[1, 11, 3, 13, 9, 0]
rechte Towerwand doppelt
[1, 11, 3, 13, 9, 0]
[1, 11, 3, 13, 9, 5, 9, 0]
8

Ich erhalte dieselben Ergebnisse. Das liegt wie gesagt an fehlender Implementierung von left[l+1] = right[r+1].

edit: so müsste auch der rechte Testfall funktionieren:

public static int[] merge(int[] left, int[] right) { ArrayList<Integer> internalRep = new ArrayList<>(); int l = 0, r = 0; int lHeight = 0, rHeight = 0; while (l < left.length && r < right.length) { if (left[l] < right[r]) { add(internalRep, left[l], Math.max(left[l + 1], rHeight)); lHeight = left[l + 1]; l += 2; } else if (left[l] > right[r]) { add(internalRep, right[r], Math.max(right[r + 1], lHeight)); rHeight = right[r + 1]; r += 2; } else { break; } } while (l < left.length) { add(internalRep, left[l], left[l + 1]); l += 2; } while (r < right.length) { add(internalRep, right[r], right[r + 1]); r += 2; } int[] ret = new int[internalRep.size()]; for (int i = 0; i < ret.length; i++) { ret[i] = internalRep.get(i); } return ret; }