Wie kann man rückwärts durch einen flachen 4-tree laufen?

Folgende Liste:
0,
1 2 3 4,
5 6 7 8, 9 10 11 12, usw.

Nun habe ich z. B. Index 1202. Das wäre Level y=300 und x=0. Wie kann ich alle parents des Index ausgeben lassen? (300, 75, 18, 4, 1, 0 passt nicht :sob:)

Also weil mir nichts Besseres Einfällt, würde ich sagen, dass das nur in Verbindung mit einem Suchindex geht. Obwohl… Haben einzelne Elemente einer solchen Struktur nicht auch stets eine Parent-Node?

Ich meine, für jedes Element gibt es genau einen Parent-Node…

	int[] getxy(int i) {
		int x = (int) Math.pow(i, 1.0 / 4.0);
		int y = i - (int) Math.pow(x, 4.0);
		return new int[] { x, y };
	}

	int geti(int x, int y) {
		return (int) (Math.pow(x, 4.0)) + y;
	}

so weit bin ich, wenn ich jetzt aber den parent bestimmen will mit

p = geti(getxy(j)[0] - 1, getxy(j)[1] / 4)

, kommt nur Sche*** dabei heraus.

Hast Du nen Tipp?


*: Ggf. ist auch mein tree falsch aufgebaut, ich muss das später mal sehen.

Verwende als Member „parentNode“ das Objekt Node und nicht irgendwelche berechneten Indices, IDs oder was auch immer dieses int-Gefudel da werden soll.

Nicht nur ggf. Denn das ist kein Tree. Du machst nur irgendwelche (sinnfreie) Berechnungen. Java ist eine Objektorientierte Sprache. Also nutze diese auch. Damit kannst du das Problem sehr einfach lösen (wie wurde bereits von Spacerat gepostet)

Das ist aber nicht der Sinn eines flachen n-trees.

Nö. Eine flache Struktur zu haben bedeutet nicht auf OOP zu verzichten und auch nicht, dass du irgendwelche komischen Berechnungen durchführen musst um an deine Objekte ran zu kommen. Dein Fall wäre ja noch „einfach“ - aber was ist wenn du die Anzahl an Kindelementen nicht mehr mathematisch bestimmen könntest? Spätestens hier sollte doch klar sein, dass dein Vorhaben kompletter Unsinn ist.

Flache Datenstrukturen nutzt man dafür, dass man gezielt sehr einfach seine Daten bearbeiten kann. Du hingegen baust eine unnötige Komplexität ein.

Ja, du hast recht. Aber eigentlich sind diese flachen trees nunmal mathematischer Natur. Eigentlich möchte ich deswegen nicht alles über Bord werfen oder heilige Kühe schlachten.
Aber Danke.

static List<Integer> parents(int index) {
    if (index == 0) {
        return new ArrayList<>();
    }
    int l0 = -1;
    int l1 = 0;
    while(l1 <= index) {
        l0 = l1;
        l1 = 4 * l1 + 4;
    }
    int parent = l0 - (l1 - index) / 4;
    List<Integer> ps = parents(parent);
    ps.add(0, parent);
    return ps;
}

parents(1202) liefert bei mir [300, 74, 18, 4, 0], was ungefähr hinkommen könnte…

Kann man natürlich noch optimieren.

Danke Landei. Thema gelöst.

Es geht um ein 8er-Schiebepuzzle. Könnt ihr mir erklären wieso eine NPE auftritt?

Zusammenfassung
import java.util.*;

public class Schiebepuzzle {
	int[][] senke = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
	int[][] quelle = { { 1, 2, 3 }, { 8, 0, 5 }, { 4, 7, 6 } };

	ArrayList<int[][]> nextes(int[][] a) {
		ArrayList<int[][]> nextes = new ArrayList<int[][]>();
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				if (a[i][j] == 0) {
					if (i - 1 >= 0) {
						nextes.add(copyAndShift(a, i, j, i - 1, j));
					} else {
						nextes.add(null);
					}
					if (i + 1 < a.length) {
						nextes.add(copyAndShift(a, i, j, i + 1, j));
					} else {
						nextes.add(null);
					}
					if (j - 1 >= 0) {
						nextes.add(copyAndShift(a, i, j, i, j - 1));
					} else {
						nextes.add(null);
					}
					if (j + 1 < a.length) {
						nextes.add(copyAndShift(a, i, j, i, j + 1));
					} else {
						nextes.add(null);
					}
					return nextes;
				}
			}
		}
		return null;
	}

	int[][] copyAndShift(int[][] a, int i, int j, int i2, int j2) {
		int[][] b = new int[a.length][a.length];
		for (int i3 = 0; i3 < a.length; i3++) {
			for (int i4 = 0; i4 < a.length; i4++) {
				b[i3][i4] = a[i3][i4];
			}
		}
		b[i][j] = b[i2][j2];
		b[i2][j2] = 0;
		return b;
	}

	void print() {
		ArrayList<int[][]> dummy = new ArrayList<int[][]>();
		dummy.add(null);
		dummy.add(null);
		dummy.add(null);
		dummy.add(null);
		ArrayList<int[][]> visited = new ArrayList<int[][]>();
		// visited.addAll(dummy);
		visited.add(quelle);
		for (int i = 0; i < 100000; i++) {
			int[][] a = visited.get(i);
			if (a != null) {
				if (Arrays.deepEquals(a, senke)) {
					for (int j = i;; j = (j / 4)) {
						System.out.println(j);
						for (int[] b : visited.get(j)) {
							System.out.println(Arrays.toString(b));
						}
						System.out.println();
						if (j == 0)
							break;
					}
					return;
				}
				ArrayList<int[][]> b = nextes(a);
				visited.addAll(b);
			} else {
				visited.addAll(dummy);
			}
		}
	}

	public static void main(String[] args) {
		new Schiebepuzzle().print();
	}
}
Zusammenfassung
3874
[1, 2, 3]
[4, 5, 6]
[7, 8, 0]

968
[1, 2, 3]
[4, 5, 0]
[7, 8, 6]

242
Exception in thread "main" java.lang.NullPointerException
	at Schiebepuzzle.print(Schiebepuzzle.java:66)
	at Schiebepuzzle.main(Schiebepuzzle.java:84)

Ist meine Frage so dämlich?

Keine Ahnung, ob Deine Frage dämlich ist. Allerdings steht in der Exception selbst, dass in Zeile 66 die NPE auftritt.
Hier im Forum haben wir keine IDE. Die Zeilen des eher interessanten Codes möchte ich nicht zählen.

Also, schau in Zeile 66. Wenn Du das Problem durch hinsehen nicht findest, nutze einen Debugger. Bist doch lange genug hier. So etwas würde ich Dir mittlerweile zutrauen.

Auf jeden Fall ist sie kurz davor, dass ich hier dicht mache! Nach dem was ich dir bisher versprochen habe, müsste das nämlich spätestens JETZT tun!

Der „Code“ ist alles andere als leserlich, die Exception versteckt in der zweiten Zusammenfassung und dann in Zeile 66. Ich glaube keiner will die Zeilen zählen.

Und letztendlich wäre es ein einfaches das Problem selber zu lösen - wie Sym sagt. Nutze zur Not einen Debugger. Fertig.

Könnt ihr mir erklären wieso eine NPE auftritt?

Weil du versuchst mit einem NULL-Wert zu arbeiten. Siehe Syms Post. Da ist der Hinweis drin, wie du erfährst, welcher wert es ist.

Moin, in Zeile 66 wird versuchst, rückwärts durch den 4-tree zu laufen, aber dabei gibt es null-Elem. Der 4-tree sollte vollständig sein, also immer genau 4 ausgehende Kanten habn. Und der 4-tree wird in den Methoden nextes und print aufgebaut. Deswegen vermute ich, das etwas mit der Verlinkung nicht hinkommt. Wäre das richtig?

Oh - Roflcopter, ich hab einfach nur ein (j - 1) vergessen. Das war wirklich nicht beabsichtigt.

int[][] senke = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
int[][] quelle = { { 1, 2, 3 }, { 8, 0, 5 }, { 4, 7, 6 } };

ArrayList<int[][]> nextes(int[][] a) {
	ArrayList<int[][]> nextes = new ArrayList<int[][]>();
	for (int i = 0; i < a.length; i++) {
		for (int j = 0; j < a.length; j++) {
			if (a[i][j] == 0) {
				if (i - 1 >= 0) {
					nextes.add(copyAndShift(a, i, j, i - 1, j));
				} else {
					nextes.add(null);
				}
				if (i + 1 < a.length) {
					nextes.add(copyAndShift(a, i, j, i + 1, j));
				} else {
					nextes.add(null);
				}
				if (j - 1 >= 0) {
					nextes.add(copyAndShift(a, i, j, i, j - 1));
				} else {
					nextes.add(null);
				}
				if (j + 1 < a.length) {
					nextes.add(copyAndShift(a, i, j, i, j + 1));
				} else {
					nextes.add(null);
				}
				return nextes;
			}
		}
	}
	return null;
}

int[][] copyAndShift(int[][] a, int i, int j, int i2, int j2) {
	int[][] b = new int[a.length][a.length];
	for (int i3 = 0; i3 < a.length; i3++) {
		for (int i4 = 0; i4 < a.length; i4++) {
			b[i3][i4] = a[i3][i4];
		}
	}
	b[i][j] = b[i2][j2];
	b[i2][j2] = 0;
	return b;
}

void print() {
	ArrayList<int[][]> dummy = new ArrayList<int[][]>();
	dummy.add(null);
	dummy.add(null);
	dummy.add(null);
	dummy.add(null);
	ArrayList<int[][]> visited = new ArrayList<int[][]>();
	visited.add(quelle);
	for (int i = 0; i < 100000; i++) {
		int[][] a = visited.get(i);
		if (a != null) {
			if (Arrays.deepEquals(a, senke)) {
				for (int j = i;; j = (j - 1) / 4) {
					System.out.println(j);
					for (int[] b : visited.get(j)) {
						System.out.println(Arrays.toString(b));
					}
					System.out.println();
					if (j == 0)
						break;
				}
				return;
			}
			ArrayList<int[][]> b = nextes(a);
			visited.addAll(b);
		} else {
			visited.addAll(dummy);
		}
	}
}

public static void main(String[] args) {
	new Schiebepuzzle().print();
}
3874
[1, 2, 3]
[4, 5, 6]
[7, 8, 0]

968
[1, 2, 3]
[4, 5, 0]
[7, 8, 6]

241
[1, 2, 3]
[4, 0, 5]
[7, 8, 6]

60
[1, 2, 3]
[4, 8, 5]
[7, 0, 6]

14
[1, 2, 3]
[4, 8, 5]
[0, 7, 6]

3
[1, 2, 3]
[0, 8, 5]
[4, 7, 6]

0
[1, 2, 3]
[8, 0, 5]
[4, 7, 6]

@Landei Ist es richtig, dass man wirklich immer nur rückwärts durch den tree laufen kann?

Um vorwärts durch den Baum zu laufen musst du immer wissen, mit welchem der Kind-Knoten es weiter geht. Ansonsten spricht nichts dagegen.

Danke. Danke. Hier nochmal refactored (null kann man auch nur in nextes anlegen):

Zusammenfassung
int[][] senke = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
int[][] quelle = { { 1, 2, 3 }, { 8, 0, 5 }, { 4, 7, 6 } };

ArrayList<int[][]> nextes(int[][] a) {
	ArrayList<int[][]> nextes = new ArrayList<int[][]>();
	if (a != null) {
		b: for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				if (a[i][j] == 0) {
					if (i - 1 >= 0) {
						nextes.add(copyAndShift(a, i, j, i - 1, j));
					} else {
						nextes.add(null);
					}
					if (i + 1 < a.length) {
						nextes.add(copyAndShift(a, i, j, i + 1, j));
					} else {
						nextes.add(null);
					}
					if (j - 1 >= 0) {
						nextes.add(copyAndShift(a, i, j, i, j - 1));
					} else {
						nextes.add(null);
					}
					if (j + 1 < a.length) {
						nextes.add(copyAndShift(a, i, j, i, j + 1));
					} else {
						nextes.add(null);
					}
					break b;
				}
			}
		}
		return nextes;
	} else {
		nextes.add(null);
		nextes.add(null);
		nextes.add(null);
		nextes.add(null);
		return nextes;
	}
}

int[][] copyAndShift(int[][] a, int i, int j, int i2, int j2) {
	int[][] b = new int[a.length][a.length];
	for (int i3 = 0; i3 < a.length; i3++) {
		for (int i4 = 0; i4 < a.length; i4++) {
			b[i3][i4] = a[i3][i4];
		}
	}
	b[i][j] = b[i2][j2];
	b[i2][j2] = 0;
	return b;
}

void print() {
	ArrayList<int[][]> visited = new ArrayList<int[][]>();
	visited.add(quelle);
	for (int i = 0; i < 100000; i++) {
		int[][] a = visited.get(i);
		if (a != null && Arrays.deepEquals(a, senke)) {
			for (int j = i;; j = (j - 1) / 4) {
				System.out.println(j);
				for (int[] b : visited.get(j)) {
					System.out.println(Arrays.toString(b));
				}
				System.out.println();
				if (j == 0) {
					return;
				}
			}
		}
		visited.addAll(nextes(a));
	}
}

Viell hat jemand Lust, das Schiebepuzzle mal zu spielen: https://schiebepuzzle.herokuapp.com/ Bitte nicht über die Grafik beschweren.

  • Warum muss man noch auf die 0 klicken? Es ist doch klar, dass das immer das Zielfeld ist
  • Was ist die Gewinnstellung? Ich hatte 123/456/780, aber nix ist passiert