Würfelturm

schraube97

Mitglied
Hey liebe Leute,
ich bin mit meinem Teamkollegen völlig am verzweifeln. Wir sollen für die uni ein rekursives Programm schreiben.

Kleine Info zu dem Programm:
Vier Würfel mit farbigen Flächen werden aufeinandergetürmt und so rotiert, dass an den Seitenwänden keine der vier Farben(Rotblau,grün,gelb) doppelt auftaucht.

Aufgabenstellung:
Entwickeln Sie ein System von Klassen, welches für jeweils vier aufeinandergestapelte Würfel rekursiv alle durch Rotation möglichen Turmstellungen mit paarweise verschiedenfarbigen Seitenwänden berechnet und diese geeignet ausgibt. Dabei werden Rotationsinvariante Lösungen erkannt und nur einmal als Lösung aufgenommen.

Also unser größtes Problem liegt darin, die vier Würfel zu drehen. Wir haben absolut keine Ahnung wie wir die Rekursion umsetzen sollen.
Wir haben einen kleinen Lösungsansatz den ich kurz beschreiben kann.
Wir haben bisher drei Klassen erstellt. Eine Würfel,InputOutput und Turm Klasse.
In der Würfel Klasse haben wir festgelegt wie ein Würfel aussehen soll. Also haben wir ein charArray mit 6 Zeichen erstellt. Das Objekt Würfel wird in der InputOutput Klasse über die User Eingabe 4 mal in eine neue ArrayList mit den Namen Turm gespeichert. In dieser müssten dann 24 Zeichen enthalten sein. Wir haben uns überlegt die Würfel dann aus der Turm Liste zu holen und zu vergleichen (über den Index). Aber wir haben wie schon gesagt absolut keine Ahnung wie wir diese Rotationen und die Vergleiche implementieren sollen. Außerdem müssten die Farben den Würfel fest zugewiesen werden (oder?) also ich meine damit, dass z.B. die 1 der 6 gegenüberliegt. Also wenn der User zuerst rot und zuletzt blau eingibt dann müssen diese färben gegenüberliegend sein um bei der Rotation nicht durcheinander zu kommen und damit der Würfel nicht verfälscht wird. Wie kann man das am besten erreichen ? Wir haben uns überlegt eine Tupel Klasse zu erstellen mit den Klassenvariablen back, front,left,right (integer)..usw. und den Konstruktor dann irgendwie in der Turmklasse für die Rekusion zu übergeben.

Habt ihr vielleicht ein paar bessere Lösungsvorschläge oder könntet uns sagen ob wir mit den Grundgedanken richtig liegen und wie wir am besten die Rekursion angehen ?

Vielen Dank im Voraus und schöne Pfingsten.
 

schraube97

Mitglied
Warum wollt ihr die denn überhaupt drehen?
Erstmal danke für deine Antwort. Dein Lösungsvorschlag klingt ganz gut. Drehen müssen wir sie, da der ganze Turm betrachtet wird. Wir haben uns das jetzt so überlegt, dass man zuerst den obersten Würfel dreht und flippt, also in seine 24 positionen bringt und dann den zweiten 1 mal dreht, den obersten wieder 24 mal und den zweiten dann ein 2. mal .. den obersten dann wieder 24 mal und den 2. dann ein drittes mal .. usw. bis zum letzten Würfel. Somit werden alle möglichkeiten welche der Würfelturm annehmen kann abgedeckt.
 

Holunderbeere

Mitglied
Vielleicht etwas spät, aber das war unser Ansatz: https://pastebin.com/NEgkaeHu
Java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * Die Main Klasse fragt die Eingabe ab und ruft die Rekursion zur Loesung auf.
 */
public class Main {

    /**
     * main-Methode
     * @param args nicht genutzt
     */
    public static void main(String args[]) {
        Wuerfelturm turm = new Wuerfelturm();
         for (int i = 0; i < 4; i++)
             while (true) {
                 try {
                     System.out.println("Bitte geben Sie vier Würfel mit der jeweils gewünschten Farbkombination ein. \n" +
                             "Zur Auswahl stehen die folgenden vier Farben: \n" + "*rot\n" + "*blau\n" + "*grün\n" + "*gelb\n" +
                             "\n" + "Bitte trennen Sie die Farben mit jeweils einem Leerzeichen. \n" + "Ihre Eingabe:\n");
                     // Eingaben hier mit Scanner einfügen (Exceptions auffangen)
                     // String eingabeTop = ;
                     // String eingabeSeiten = ;
                     // String[] eingabeSeitenSplit = eingabeSeiten.split(" ");
                     // String eingabeBottom = ;

                     String[] eingabeFarben = new String[6];
                     eingabeFarben[0] = eingabeTop;
                     eingabeFarben[1] = eingabeSeitenSplit[0];
                     eingabeFarben[2] = eingabeSeitenSplit[1];
                     eingabeFarben[3] = eingabeSeitenSplit[2];
                     eingabeFarben[4] = eingabeSeitenSplit[3];
                     eingabeFarben[5] = eingabeBottom;

                     if (!(Wuerfel.getFarbe().contains(eingabeFarben[0]))) {
                         System.out.println("Sie haben einen Fehler bei 'Top' gemacht. Bitte überprüfen Sie Ihre Eingabe bezüglich Rechtschreibung und Leerzeichen.\n");
                         continue;
                     }

                     if (!(Wuerfel.getFarbe().contains(eingabeFarben[1]) && Wuerfel.getFarbe().contains(eingabeFarben[2]) &&
                             Wuerfel.getFarbe().contains(eingabeFarben[3]) && Wuerfel.getFarbe().contains(eingabeFarben[4]))) {
                         System.out.println("Sie haben einen Fehler bei 'Seiten' gemacht. Bitte überprüfen Sie Ihre Eingabe bezüglich Rechtschreibung und Leerzeichen.\n");
                         continue;
                     }

                     if (!(Wuerfel.getFarbe().contains(eingabeFarben[5]))) {
                         System.out.println("Sie haben einen Fehler bei 'Bottom' gemacht. Bitte überprüfen Sie Ihre Eingabe bezüglich Rechtschreibung und Leerzeichen.\n");
                         continue;
                     }
                     turm.neuerWuerfel(new Wuerfel(eingabeTop, new ArrayList<String>(Arrays.asList(eingabeSeitenSplit[0],
                             eingabeSeitenSplit[1], eingabeSeitenSplit[2], eingabeSeitenSplit[3])), eingabeBottom), i);
                     break;

                 } catch (ArrayIndexOutOfBoundsException e) {
                     System.out.println("Sie haben einen Fehler gemacht. Bitte überprüfen Sie Ihre Eingabe bezüglich Rechtschreibung und Leerzeichen.\n +" +
                             "Bitte beachten Sie, dass Sie bei Top und Bottom jeweils eine Farbe und bei Seiten genau vier Farben angeben müssen.\n");
                 }
             }
        HashSet<String> visitedTowers = new HashSet<>();
        HashSet<String> visitedTowersFull = new HashSet<>();

        turm.sortRecursive(0,0, visitedTowers, visitedTowersFull);
    }
}
Java:
import java.util.ArrayList;
import java.util.HashSet;

/**
 * Die Wurfel Klasse beschreibt einen Wuerfel
 */
public class Wuerfel {

    private static HashSet<String> farbe = new HashSet(){{
        add("rot");
        add("blau");
        add("grün");
        add("gelb");
    }};
    private ArrayList<String> seite = new ArrayList<>();
    private String top;
    private String bottom;
    private int state;

    /**
     * Konstruktor der Wuerfel Klasse
     * @param top Oberseite des Wuerfels
     * @param seite Seitenflaechen des Wuerfels (eins, zwei, drei, vier)
     * @param bottom Unterseite des Wuerfels
     */
    public Wuerfel(String top, ArrayList<String> seite, String bottom) {
        this.top = top;
        this.seite = seite;
        this.bottom = bottom;
        this.state = 1;
    }

    /**
     * Getter fuer Seitenflaechen
     * @return Seitenflaechen des Wuerfels
     */
    public ArrayList<String> getSeite() {
        return seite;
    }

    /**
     * Gibt moegliche Farbwerte fuer einen Wuerfel zurueck
     * @return
     */
    public static HashSet<String> getFarbe() {
        return farbe;
    }

    /**
     * Gibt alle Wuerfelseiten als ein String zurueck
     * @return alle Wuerfelseiten (oben, eins, zwei, drei, vier, unten)
     */
    @Override public String toString() {
        StringBuilder wuerfelString = new StringBuilder();
        wuerfelString.append(top).append("\n").append(seite).append("\n").append(bottom);
        return wuerfelString.toString();
    }

    /**
     * Gibt nur die vier Seitenflaechen des Wuerfels als ein String zurueck
     * @return vier Wuerfelseitenflaechen
     */
    public String toStringSeiten() {
        return String.valueOf(seite);
    }


    /**
     * dreht den Wuerfel
     */
    private void drehen() {
        seite.add(seite.get(0));
        seite.remove(seite.get(0));
    }

    /**
     * kippt den Wuerfel
     */
    private void kippen() {
        String temp = this.top;
        this.top = this.seite.get(2);
        this.seite.set(2, this.bottom);
        this.bottom = this.seite.get(0);
        this.seite.set(0, temp);
    }

    /**
     * Rotiert den Wuerfel in alle 24 moeglichen Orientierungen
     */
    public void rotate() {
        if (this.state < 4) {
            this.drehen();
            state++;
        } else if (this.state == 4) {
            this.kippen();
            state++;
        } else if (this.state < 8) {
            this.drehen();
            state++;
        } else if (this.state == 8) {
            this.kippen();
            state++;
        } else if (this.state < 12) {
            this.drehen();
            state++;
        } else if (this.state == 12) {
            this.drehen();
            this.kippen();
            state++;
        } else if (this.state < 16) {
            this.drehen();
            state++;
        } else if (this.state == 16) {
            this.drehen();
            this.kippen();
            state++;
        } else if (this.state < 20) {
            this.drehen();
            state++;
        } else if (this.state == 20) {
            this.drehen();
            this.drehen();
            this.kippen();
            state++;
        } else if (this.state < 24) {
            this.drehen();
            state++;
        } else if (this.state == 24) {
            this.drehen();
            this.kippen();
            this.kippen();
            this.state = 1;
        }
    }
}
Java:
import java.util.HashSet;

/**
 * Die Wurfelturm Klasse enthaelt die Logik zur Loesung des Wuerfelturms.
 */
public class Wuerfelturm {
    private Wuerfel[] turm = new Wuerfel[4];
    public void neuerWuerfel(Wuerfel wuerfel, int index){
        this.turm[index] = wuerfel;
    }

    /**
     * Rekursive Methode zur Loesung des Wuerfelturms
     * @param wuerfel index des Wuerfels
     * @param rotationen Anzahl der Rotationen eines Wuerfels
     * @param visitedTowers bereits gespeicherte Loesungen ohne TOP und BOTTOM Seite
     * @param visitedTowersFull bereits gespeicherte Loesungen mit TOP und BOTTOM Seite
     */
    public void sortRecursive(int wuerfel, int rotationen, HashSet<String> visitedTowers, HashSet<String> visitedTowersFull) {
        if (this.isValid()) {
            String towerString = this.toString();
            String towerStringWithoutTopAndBot = this.getTowerStringIgnoringTopAndBottom();
            if (!visitedTowers.contains(towerStringWithoutTopAndBot) && !visitedTowersFull.contains(towerString) ) {
                visitedTowers.add(towerStringWithoutTopAndBot);
                visitedTowersFull.add(towerString);
                System.out.println(towerString);
            }
        }

        if (rotationen < 24) {
            if (wuerfel < 3) {
                for (int i = 0; i < 24; i++) {
                    this.turm[wuerfel].rotate();
                    sortRecursive(wuerfel + 1, 0, visitedTowers, visitedTowersFull);
                }
            } else {
                this.turm[wuerfel].rotate();
                sortRecursive(wuerfel, rotationen + 1, visitedTowers, visitedTowersFull);
            }
        }
    }

    /**
     * Methode zur Ueberpruefung einer Loesung
     * @return ist der Wuerfelturm eine echte Loesung
     */
    private boolean isValid() {
        HashSet<String> farben = new HashSet<>();
        for (int i = 0; i < 4; i++) {
            for (int k = 0; k < 4; k++) {
                if (!farben.contains(turm[k].getSeite().get(i))) {
                    farben.add(turm[k].getSeite().get(i));
                } else {
                    return false;
                }
            }
            farben.clear();
        }
        return true;
    }

    /**
     * Methode zur Ausgabe des aktuellen Zustands des Wuerfelturms
     * @return Zeichenkette des Wuerfelturms
     */
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append("###########").append("\n");
        for (int i = 0; i < 4; i++) {
            result.append("\n").append(this.turm[i].toString()).append("\n");
        }
        result.append("\n");
        return result.toString();
    }
    /**
     * Methode zur Ausgabe des aktuellen Zustands des Wuerfelturms ohne TOP und BOTTOM Seiten der Wuerfel
     * @return Zeichenkette des Wuerfelturms
     */
    private String getTowerStringIgnoringTopAndBottom() {
        StringBuilder result = new StringBuilder();
        for (int i = 1; i < 4; i++) {
            result.append(this.turm[i].toStringSeiten());
        };
        return result.toString();
    }
}
 

Blender3D

Top Contributor
Vielleicht etwas spät, aber das war unser Ansatz: https://pastebin.com/NEgkaeHu
Hier ein anderer Ansatz für die Klasse Wuerfel.
Java:
import java.util.Arrays;
import java.util.List;
import wuerfelturm.Dice;

public class TestWuerfel {

    public static void main(String[] args) {
        List<Dice.COLOR> data = Arrays.asList(Dice.COLOR.BLUE, Dice.COLOR.YELLOW, Dice.COLOR.GREEN, Dice.COLOR.RED,
                Dice.COLOR.BLUE, Dice.COLOR.GREEN);
        Dice d = new Dice(data);
        rotate(d, 0, 0, 0);
    }

    public static void printDice(Dice d, int cnt) {
        System.out.println(d + "\t" + cnt);
    }

    public static void rotate(Dice d, int forward, int left, int cnt) {    
        if (left < 4) {
            printDice(d, ++cnt);
            rotate(d.turnForward(), forward, left + 1, cnt);
        } else if (forward < 4) {
            printDice(d, ++cnt);
            rotate(d.turnLeft(), forward + 1, 0, cnt);
        }
    }

}


Java:
import java.util.List;

public class Dice {
    public static enum COLOR {
        RED, YELLOW, GREEN, BLUE
    };

    private COLOR[] sides = new COLOR[6];
    public final static int TOP = 0;
    public final static int FRONT = 1;
    public final static int RIGHT = 2;
    public final static int BACK = 3;
    public final static int LEFT = 4;
    public final static int BOTTOM = 5;

    public Dice(List<COLOR> colors) throws IllegalStateException {
        if (colors.size() != sides.length)
            throw new IllegalStateException("Dice expects six colors not " + colors.size() + "!");
        if (!colors.contains(COLOR.RED))
            throw new IllegalStateException("Color red is missing!");
        if (!colors.contains(COLOR.YELLOW))
            throw new IllegalStateException("Color yellow is missing!");
        if (!colors.contains(COLOR.BLUE))
            throw new IllegalStateException("Color blue is missing!");
        if (!colors.contains(COLOR.GREEN))
            throw new IllegalStateException("Color green is missing!");
        for (int i = 0; i < sides.length; i++)
            sides[i] = colors.get(i);
    }

    public COLOR getSideColor(int id) throws IllegalArgumentException {
        if (id < 0 || id >= sides.length)
            throw new IllegalArgumentException(
                    "Unknown side id\nPlease use class constants\n-> '" + this.getClass().getName() + ".TOP' etc.");
        return sides[id];
    }

    /**
     * Gibt nur die vier Seitenflaechen des Wuerfels als ein String zurueck
     *
     * @return vier Wuerfelseitenflaechen
     */
    public String toStringSides() {
        StringBuilder tmp = new StringBuilder();
        for (int i = 1; i < sides.length - 1; i++)
            tmp.append(sides[i].toString().charAt(0));
        return tmp.toString();
    }

    public Dice turnForward() {
        COLOR tmp = sides[FRONT];
        sides[FRONT] = sides[TOP];
        sides[TOP] = sides[BACK];
        sides[BACK] = sides[BOTTOM];
        sides[BOTTOM] = tmp;
        return this;
    }

    public Dice turnLeft() {
        COLOR tmp = sides[FRONT];
        sides[FRONT] = sides[RIGHT];
        sides[RIGHT] = sides[BACK];
        sides[BACK] = sides[LEFT];
        sides[LEFT] = tmp;
        return this;
    }

    /**
     * Gibt alle Wuerfelseiten als ein String zurueck
     *
     * @return alle Wuerfelseiten (oben, eins, zwei, drei, vier, unten)
     */
    @Override
    public String toString() {
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i < sides.length; i++)
            tmp.append(sides[i].toString().charAt(0));
        return tmp.toString();
    }
}
 
Zuletzt bearbeitet:

Oben