| Die letzten 10 Beiträge |
| eulerscheZahl |
In colors stehen Werte in [0;3]. Man kann die Werte also einen nach dem anderen in eine Zahl mit Basis 4 schreiben, ohne Platz zu verschenken. So komprimiere ich alle Seitenflächen des Turms in ein einziges long. Auf die Weise kann ich bei anderen Türmen leicht prüfen, ob ich sie schon hatte.
Je nach Seitenfläche, mit der ich starte, kann das aber eine andere Zahl geben. Deshalb starte ich mit allen vier Seitenflächen und prüfe für jede, ob ich sie schon hatte.
Für dich gilt: du musst ja prüfen, ob du einen Turm schon hattest. Dazu könntest du jeden Turm mit jedem anderen vergleichen. Je mehr Türme, desto länger dauert das.
Alternativ kannst du das Comparable Interface implementieren und hashCode überschreiben. Dabei muss der Wert des Hashcodes rotationsinvariant sein. |
| Nago |
Erstmal vielen dank für deine Hilfe. Habs jetzt fast geschaft. Das einzige was noch ernste probleme bereitet is der Filter bezüglichd er Rotationsinvarianten. Es fällt mir ein wenig schwer deinen algorithmus um zu setzen, weil es sich ja bei mir um objekte handelt(enums, Würfel, Türme), vor allem aber weil ich teilweise ncihtmal versteht wie es funktioniert:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
|
if (index == 4) {
//check for duplicates
long[] values = new long[4]; //represent the towers by longs, fits in 64 bit
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
values[i] *= 4;
values[i] += colors[j][k];
}
}
}
|
|
Schätze ich steht einfach auf dem schlacuh, aber wozu die multiplikation/addition bei values[i]? |
| eulerscheZahl |
Hier mal nur der Algorithmus (ohne objektorientierte Programmierung). Der Testfall ist zufällig. Es kann also ein paar Versuche dauern, bis du eine Lösung findest.
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
|
import java.util.HashSet;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int[][] die = new int[4][6];
Random random = new Random();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 6; j++)
die[i][j] = random.nextInt(4);
}
System.out.println(countStates(die, 0, new int[4][4]));
}
static HashSet<Long> towers = new HashSet<Long>();
/**
* count number of ways to build a tower
*
* @param die
* the die to use
* index0: index of the die
* index1: color at face - two opposite faces have a difference
* of 3 in the index
* @param index
* next die to use
* @param colors
* the colors used at the sides
* index0: height
* index1: front, back, right, left
* @return
*/
private static int countStates(int[][] die, int index, int[][] colors) {
if (index == 4) {
//check for duplicates
long[] values = new long[4]; //represent the towers by longs, fits in 64 bit
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
values[i] *= 4;
values[i] += colors[j][k];
}
}
}
boolean dublicate = false;
for (int i = 0; i < 4; i++) {
if (towers.contains(values[i]))
dublicate = true;
}
if (!dublicate) {
towers.add(values[0]);
String[] text = new String[] { "front", "left", "back", "right" };
for (int face = 0; face < 4; face++) {
System.out.print(text[face] + ": ");
for (int height = 0; height < 4; height++)
System.out.print(colors[height][face]);
System.out.print("\t");
}
System.out.println();
return 1;
}
return 0;
}
int result = 0;
for (int topColor = 0; topColor < 6; topColor++) {
colors[index][0] = die[index][(topColor + 1) % 6];
colors[index][1] = die[index][(topColor + 2) % 6];
colors[index][2] = die[index][(topColor + 4) % 6];
colors[index][3] = die[index][(topColor + 5) % 6];
if (valid(colors, index))
result += countStates(die, index + 1, colors);
colors[index][1] = die[index][(topColor + 5) % 6];
colors[index][3] = die[index][(topColor + 2) % 6];
if (valid(colors, index))
result += countStates(die, index + 1, colors);
}
return result;
}
static boolean valid(int[][] colors, int index) {
for (int face = 0; face < 4; face++) {
boolean[] used = new boolean[4];
for (int height = 0; height <= index; height++) {
if (used[colors[height][face]])
return false;
used[colors[height][face]] = true;
}
}
return true;
}
} |
|
|
| Nago |
Die Würfel können, müssen aber nciht gleich sein. Wie die aussehen wird über eine Eingabe festgelegt.
Es gibt 4 Farben, ein Würfel kann alle farben haben, aber er kann zum Beispiel auch komplett blau sein.
Mit Rotationsinvariante ist gemeint, dass ein Turm, der nur durch drehung eines vorhanden Turms entsteht, als der Selbe angesehen wird, also er nicht nochmal in die Lösungsmenge kommt.
Die Würfel ändern ihre höhe nicht, der Würfel der zum Beispiel ganz unten steht, bleibt auhc unten. (Der unterste Würfel wird übrigens nicht rotiert).
| Zitat: |
| Sind zwei Türme gleich, wenn man einen auf den Kopf stellt und dann den anderen erhält? |
Nein. Es sei denn natürlich die Farben wären Symmetrisch. Aber dann ist der Turm ja eh keine Lösung.
| Zitat: |
| Kommt es nur auf die Boden- und Deckfläche an, oder auch auf Front und Seite? |
Für eine gültige Lösung kommt es nur auf die Seitenflächen an. Jede der 4 Seiten eines Turmes muss also jede Farbe einmal enthalten. Ob die Turmseiten gleich sind ist egal.
Die Boden und Deckel-flächen kommen erst ins spiel, wenn ein Würfel vertikal gedreht wird, weil sie ja dann zu Seitenflächen werden.
Der Ansatz oben wird wahrscheinlich wieder verworfen. Ich fang nochmal neu an, weil es irgendwie nicht alles ausgibt (das was oben steht ist auch nicht mehr 100%ig aktuell).
Und ich weiß leider nicht ob ich nah dran oder ewig weit weg bin.
Der Farbvergleich wird jetzt vermutlich einfach iterativ stattfinden. Es geht um grunde einfach nur noch um die verschiedenen Turmstellungen.
Ich hoffe ich habe etwas klarheit reingebracht. Musste neulich selber nochmal in der Uni nachfragen, weil mir plötzlich auch nich alles klar war.
Hier nochmal der aktuellste code der stellungen methode:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
|
public void stellungen(Turm turm, int a, int b, int c, int d){
/**
if(pruefung(turm))
{liste.addTurm(turm);}
if( vertikal > 0 && hoehe > 0){
turm.wuerfelListe[hoehe].vertikaleRotation1();
if(pruefung(turm))
{liste.addTurm(turm);}
horizontaleRotation();
stellungen(turm, seite ,hoehe, vertikal-1);}
if(seite > 0 && vertikal == 0 && hoehe > 0){
turm.wuerfelListe[hoehe].horizontaleRotation();
stellungen(turm, seite-1, hoehe, 3);}
if(seite == 0 && hoehe > 1 && vertikal == 0){
stellungen(turm, 3, hoehe-1, 3 );}
if (seite == 0 && hoehe == 1 && vertikal == 0) {
System.out.println("huhu");
liste.ausgabe();
}
|
|
Die mehtode wird mit stellungen(turm, 0,0,0,0); aufgerufen. |
| eulerscheZahl |
Mir ist die Aufgabe leider immer noch nicht komplett klar. Und das Fehlen der Initialisierung im deinem Codeausschnitt macht das nicht besser.
- Sind die Würfel gleich? Wenn verschieden, ist dann die Reihenfolge vertauschbar?
- Was verstehst du unter rotationsinvariant?
- Sind zwei Türme gleich, wenn man einen auf den Kopf stellt und dann den anderen erhält?
- Kommt es nur auf die Boden- und Deckfläche an, oder auch auf Front und Seite?
|
| Nago |
Sry, hab meinen code nochmal ergänzt.
Turm ist ein objekt mit attribut Würfel[ ] würfelliste, welches die 4 würfel des Turms enthält, mit den verschiedenen indizes wird gezählt welchen würfel, bzw. welche seite zum wie vielten mal wie gedreht oder vergleicht wird.Wie gesaagt, es sind schon wieder recht viele.
Das hat zwar nichts mehr mit rekursion zu tun, aber es gehört noch mit zur aufgabe und ich denke gerade darüber nach:
Die lösungsmenge sol keine rotationsinvarianten der Türme enthalten, aber ich ich keinen plan wie ich überprüfen soll, ob ein Turm schon gedreht enthalten ist.
Am anfang wurde mal contains() daher gesagt, aber das wird ja bei den Türmen nicht funktionieren, ich muss im Grunde ja die Farben im zusammenhang mit ihrer position verlgiechen. Es sei denn das geht klüger, aber da hab ich gar keine idee, wie man das bewerkstelligen soll. |
| eulerscheZahl |
Wenn ich mir das anschauen soll, brauche ich auch deinen kompletten Code.
Du rufst da Funktionen auf, die nirgends definiert sind. |
| Nago |
Ich danke dir nochmals für deine Hilfe.
Ich hatte ja versucht alles in einer Rekursiven funktion zu machen, habe mich jetzt aber entschieden, das ganze auf zu spalten. Eine methode, welche sämtliche würfelstellungen erzeugt und eine welche dann prüft welcher Turm als Lösung in Frage kommt. Die funktion für die Stellung sieht bis jetzt so aus:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
|
//soll prüfen, ob der mitgegebene Turm eine gültige lösung ist(ist aber noch nicht fertig)
public void pruefung(Turm turm, int n, int m){
if ( n > 0 && m > 0)
{
if(turm.wuerfelListe[n].getFarbe()[m]!= turm.wuerfelListe[n-1].getFarbe()[m])
{pruefung(turm, n - 1, m );
}
else {}
}
if (n == 0 && m > 0)
{ pruefung(turm, 3, m-1);}
if (n == 0 && m == 0){
//hängt turm an lösungslist ran (ArrayList<Turm>)
liste.addTurm(turm);}
}
public void stellungen(Turm turm, int seite, int hoehe, int vertikal){
pruefung(turm, 3,3);
if(seite>0 && vertikal > 0){
turm.wuerfelListe[hoehe].vertikaleRotation1();
stellungen(turm, seite ,hoehe, vertikal-1);}
else if(seite > 0 && vertikal == 0){
turm.wuerfelListe[hoehe].horizontaleRotation();
stellungen(turm, seite-1, hoehe, 4);}
else if(seite == 0 && hoehe > 0 && vertikal == 0){
stellungen(turm, 4, hoehe-1, 4 );
}
else if (hoehe==0){
System.out.println("huhu");
//gibt die lsite aus die die Türme enthält die gütlige lösungen sind
liste.ausgabe();}
} |
|
Der macht aber noch nciht so wirklich was er soll. das "huhu" am ende is nur um die ausgabe zu testen, aber anscheinend wird hoehe nicht 0, was ich nicht verstehe. Ich sitze jetzt auch schon seit einigen tagen der Aufgabe und werde glaube ich langsam blind für den code.
Es Sei denn der Fehler liegt in der anderen Methode, an der arbeite ich gerade noch, schreib ich dann später vllt noch.
Ich hab halt auch schon wieder so viele variablen. Bin mir nicht sicher ob das so nötig ist, oder ob ichs mir einfach kompliziert mache. |
| eulerscheZahl |
Ich wäre das etwa so angegangen:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
|
static Die[] dice = new Die[4]; //der Turm besteht aus 4 Würfeln
//TODO: Farben zuweisen, den Turm darfst du selbst reinwursteln
static void main(String[] args) {
System.out.println(count(0, -1));
}
static int count(int currentDie, int lastColor) { //hier evtl noch den Turm übergeben, statt als static member
if (currentDie == dice.length) return 1;
//...
} |
|
Du kannst natürlich auch einen Würfel statt des Index übergeben und dann auf null prüfen. |
| Nago |
Ich danke dir für deine Hilfe,werde mich gleich (oder vllt eher morgen früh) damit auseinander setzen. Mit "verfügbarer Würfel" meinst du einfach die Würfel dies Turms die noch nciht geprüft wurden oder?
Hab leider festgestellt das ich die aufgabe erst falsch verstanden hatte: Gültige Stellungen sind alle, bei denen keine Farbe an einer Seite doppelt vorkommt, bzw, an denen jede Farbe 1 mal vorkommt (ist bei 4 farben und 4 Würfeln ja das selbe). Die formulierung "paarweise verschieden" hat mich glaub ich verwirrt.
Ich programmiere in java, und das gnaze soll objektorientiert sein.
Ich hab also eine Klasse Würfel, mit den Farben als Attributen und eine Klasse Turm, die als Attribut 4 Würfel hat. Natürlich noch ein paar andere Klassen. Das UML ist auch schon abgenommen, die Grundstruktur steht also fest. |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
