Wie oft passt ein Quader in einen größeren Quader?

Ja, so weit war ich auch schon:

@NoIDE sagte in Wie oft passt ein Quader in einen größeren Quader?:

etwas stimmt mit meinem Code nicht

Dieser Beitrag wurde gelöscht!

Hm, jeder Beitrag wird downgevoted, dann nehme ich die Frage zurück.

DocShoe

@NoIDE
Liegt nicht an der Frage...

@DocShoe sagte in Wie oft passt ein Quader in einen größeren Quader?:

@NoIDE
Liegt nicht an der Frage...

Ja, dass man die Leute nicht sehen kann, die downvoten, ist auch eine Plage...

Auf Stackoverflow braucht man wenigstens eine gewisse Reputation, bevor man Fragen downvoten kann... hier darf das jeder Hanswurst.

wob

In meiner ersten Antwort steht schon alles drin. Niemand sollte sich einen Code mit so tief verschachtelten Schleifen auch nur angucken (ich habe beispielsweise ausschließlich die for-Schleifen gezählt und dann sofort aufgehört, irgendwas anzugucken - sicherheitshalber habe ich dann nochmal nachgezählt, aber es wurde nicht weniger... - leider konnte ich das switch-case auch nicht übersehen: was bedeutet zum Beispiel "case 4"? Wer soll das wissen/beurteilen? In den Fall wird bei dir irgendwas addiert). Das kann nur schief gehen. Da bringt es auch niemandem etwas (auch dir nicht!), wenn man Fehler finden (und berichtigen) würde, denn das gesamte Konstrukt ist baufällig. Also abreißen und neu machen. Funktionen benutzen! Sprachlich hast du gewisse Operationen benannt. Wäre ja irgendwie gut, wenn sich davon irgendwas im Code wiederfinden würde.

Die Downvotes sind schon teilweise gerechtfertigt. Einfach nur "hier ist irgendeine Aufgabe, dort Schrott-Code, der nicht funktioniert, findet Fehler" ist nicht sehr hilfreich.

Swordfish

@NoIDE sagte in Wie oft passt ein Quader in einen größeren Quader?:

Auf Stackoverflow braucht man wenigstens eine gewisse Reputation, bevor man Fragen downvoten kann... hier darf das jeder Hanswurst.

Hm. Ich hab' auf SO die Rep so ziemlich alles und jeden wegzuvoten, hab' ich aber mit Deinen Posts hier nicht getan. *hanswurstet weiter*

DocShoe

@NoIDE sagte in Wie oft passt ein Quader in einen größeren Quader?:

...
Auf Stackoverflow braucht man wenigstens eine gewisse Reputation, bevor man Fragen downvoten kann... hier darf das jeder Hanswurst.

Ja dann geh doch zu StackOverflow, das ist eine Win-Win Entscheidung.

Diese Häme kannst du dir sparen, Bösewicht

*john 0

@wob sagte in Wie oft passt ein Quader in einen größeren Quader?:

Niemand sollte sich einen Code mit so tief verschachtelten Schleifen auch nur angucken

Sorry, aber in einigen Teilbereichen sind solche Schleifentiefen normal und rein gar nichts außergewöhnliches. Beispielcode von Kazushige Goto für eine hochoptimierte DGEMM Routine hat 9 verschachtelte Schleifen, die auch allesamt notwendig sind, und besser auch in nicht in eigenen Funktionen ausgelagert werden, weil sonst die Compiler ggf. Probleme machen.

wob

@john-0 In Spezialfällen mit Rechtfertigung: ok. Ansonsten nicht.

@john-0
Der Code könnte korrekt sein, aber vielleicht gibt es zu der Aufgabe, die ich in einem anderen Forum gefunden hatte, gar keine Lösung:

Eine große Box hat die Innenmaße 5x5x5. In ihr sollen kleinere Boxen (Quader) platziert werden, bis diese komplett gefüllt ist.

Zur Verfügung stehen folgende kleine Boxen:

1x1x1, 6-mal (Volumen 1)
1x2x4, 6-mal (Volumen 8)
2x2x3, 6-mal (Volumen 12)

Es soll mit Backtracking-Verfahren gelöst werden.

6+6x8+6x12=126 also wäre 1x 1x1x1 übrig, aber dann müssten alle anderen genau passen, und daran zweifele ich gerade.

Um einen 1x2x4 einzufügen, wir immer ein 1x1x1 gebraucht, damit fallen alle 1x1x1 schon einmal weg.

Und 1x2x4 lässt sich glaube ich nicht lückenlos mit 2x2x3 kombinieren.

Quiche Lorraine

@NoIDE sagte in Wie oft passt ein Quader in einen größeren Quader?:

Es soll mit Backtracking-Verfahren gelöst werden.

Und warum kommst du mit einer iterativen Lösung um die Ecke? Schon mal den Suchbaum überlegt?

Davon mal abgesehen scheint diese Aufgabe nicht effizient lösbar. Ich zähle einen Verzweigungsgrad von 18 (Verschiebung = 6, Drehung = 6, Kippen = 3, Element = 3). Dazu müssen 17 Elemente positioniert werden. Das heißt mal in Blaue geschätzt hast du ${18}^{17}$ Kombinationen = 2.185912E+21 Kombinationen. Und das ist mehr als ein Brute Force Angriff auf DES welcher, so glaube ich, 24h dauert.

@Quiche-Lorraine sagte in Wie oft passt ein Quader in einen größeren Quader?:

Und warum kommst du mit einer iterativen Lösung um die Ecke? Schon mal den Suchbaum überlegt?

Nicht so frech, bitte.

Das war ja nur ein Teil des Codes (das Einsetzen), den ich als problematisch oder falsch empfinde.

Mit 18^18 (oder 17) hast du vollkommen recht. Es kommen aber nicht alle Kombinationen infrage... Sobald eine Lücke entstanden ist, kann der ganze Zweig nicht weiter untersucht werden.

Soll ich vielleicht meinen Beitrag mal wiederherstellen?

Quiche Lorraine

@NoIDE sagte in Wie oft passt ein Quader in einen größeren Quader?:

Soll ich vielleicht meinen Beitrag mal wiederherstellen?

Nein danke, nach deiner pampigen Anwort ist mir die Lust vergangen.

So, bitte nicht lachen, ich habe mir jetzt extra eine Box besorgt und ein Buch:

https://postimg.cc/68GM0PSB

Es kann also in 6 Richtungen gedreht werden.

Nun ist nur noch die Frage, ob das mein Code oben (die switch-cases...) auch tut?

Und hier wird eine 90-Drehung erklärt: https://www.youtube.com/watch?v=wd9_eSOAFR0 aber leider nur eine, nicht alle.

Super! Nach einer Nacht, wo ich gut geschlafen hab... Hab ich den Fehler in meinen Code gefunden! (Man sagt ja immer, im Schlaf überdenkt man den Vortag.)

Die gute Nachricht ist:

Der Code zum Drehen bzw. zum Einsetzen oben war richtig.

Und das ist in Java gerade so lösbar.

Mein Fehler im Code war:

Ich hatte nicht daran gedacht, dass es auch notwendig ist, an einer Stelle keinen keinen Kandidaten einzufügen und diese Stelle vorerst leer zu lassen, und erst hinter zu befüllen.

Zwei mögliche Lösungen wären:

Start solving with: maxCandidates = 23, withMagicCuboid = true, nextRandom = true
true
[17, 19, 2]
[[0, 0, 0, 2, 2], [0, 0, 0, 2, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [2, 2, 2, 2, 1]]
[[0, 0, 0, 2, 2], [0, 0, 0, 1, 1], [0, 0, 2, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]]
[[0, 0, 2, 2, 2], [0, 0, 2, 1, 2], [0, 0, 2, 1, 2], [0, 0, 1, 1, 2], [0, 0, 1, 1, 2]]
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 2, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]]
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 2, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]]
Start solving with: maxCandidates = 6, withMagicCuboid = true, nextRandom = true
true
[0, 0, 1]
[[1, 1, 1, 1, 2], [1, 1, 1, 1, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1], [1, 1, 0, 0, 1]]
[[0, 0, 0, 1, 1], [0, 0, 0, 2, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1], [1, 1, 0, 0, 1]]
[[0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 2, 0, 0], [0, 0, 0, 0, 0], [1, 1, 0, 0, 0]]
[[1, 0, 0, 1, 1], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 2, 0, 0, 0], [1, 1, 0, 0, 0]]
[[1, 0, 0, 1, 1], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [2, 1, 1, 1, 1]]

wobei:
0 = 2x2x3
1 = 1x2x4
2 = 1x1x1

Anbei noch der Code, ist ja vielleicht interessant:

import java.util.Arrays;

public class Box {
    final int len = 5;
    final int empty = -1;
    final boolean withMagicCuboid;
    final int[][][] solution = new int[len][len][len];
    final int[][] candidates = {
            {2, 2, 3},
            {1, 2, 4},
            {1, 1, 1},
    };
    final int[][] randomCandidates = {
            {0, 1, 2},
            {0, 2, 1},
            {1, 0, 2},
            {1, 2, 0},
            {2, 0, 1},
            {2, 1, 0},
    };
    final int[] available = new int[candidates.length];
    final int[] xyz = new int[3];
    int freeSpace = len * len * len;

    Box(final int maxCandidates, final boolean withMagicCuboid) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < len; k++) {
                    solution[i][j][k] = empty;
                }
            }
        }
        Arrays.fill(available, maxCandidates);

        this.withMagicCuboid = withMagicCuboid;
        if (withMagicCuboid) {
            // insert magic cuboid
            solution[2][2][2] = 2;
            available[2]--;
            freeSpace--;
        }
    }

    void fillCoordinates(final int dir, final int x, final int y, final int z, final int i, final int j, final int k) {
        xyz[0] = x;
        xyz[1] = y;
        xyz[2] = z;
        switch (dir) {
            case 0 -> {
                xyz[0] += i;
                xyz[1] += j;
                xyz[2] += k;
            }
            case 1 -> {
                xyz[0] += i;
                xyz[1] += k;
                xyz[2] += j;
            }
            case 2 -> {
                xyz[0] += j;
                xyz[1] += i;
                xyz[2] += k;
            }
            case 3 -> {
                xyz[0] += j;
                xyz[1] += k;
                xyz[2] += i;
            }
            case 4 -> {
                xyz[0] += k;
                xyz[1] += i;
                xyz[2] += j;
            }
            case 5 -> {
                xyz[0] += k;
                xyz[1] += j;
                xyz[2] += i;
            }
        }
    }

    boolean isInsertable(final int c, final int x, final int y, final int z, final int dir) {
        if (available[c] <= 0) {
            return false;
        }
        int[] a = candidates[c];
        for (int i = 0; i < a[0]; i++) {
            for (int j = 0; j < a[1]; j++) {
                for (int k = 0; k < a[2]; k++) {
                    fillCoordinates(dir, x, y, z, i, j, k);
                    for (int l : xyz) {
                        if (l < 0 || l >= len) {
                            return false;
                        }
                    }
                    if (solution[xyz[0]][xyz[1]][xyz[2]] != empty) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    void insert1(final int c, final int x, final int y, final int z, final int dir) {
        int[] a = candidates[c];
        for (int i = 0; i < a[0]; i++) {
            for (int j = 0; j < a[1]; j++) {
                for (int k = 0; k < a[2]; k++) {
                    fillCoordinates(dir, x, y, z, i, j, k);
                    solution[xyz[0]][xyz[1]][xyz[2]] = c;
                    freeSpace--;
                }
            }
        }
        available[c]--;
    }

    boolean insert(final int c, final int x, final int y, final int z, final int dir) {
        if (isInsertable(c, x, y, z, dir)) {
            insert1(c, x, y, z, dir);
            return true;
        }
        return false;
    }

    void remove(final int c, final int x, final int y, final int z, final int dir) {
        int[] a = candidates[c];
        for (int i = 0; i < a[0]; i++) {
            for (int j = 0; j < a[1]; j++) {
                for (int k = 0; k < a[2]; k++) {
                    fillCoordinates(dir, x, y, z, i, j, k);
                    solution[xyz[0]][xyz[1]][xyz[2]] = empty;
                    freeSpace++;
                }
            }
        }
        available[c]++;
    }

    boolean isSolved() {
        return freeSpace == 0;
    }

    boolean isProbableSolvable(final int level) {
        if (freeSpace <= 0) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < len; k++) {
                    if (solution[i][j][k] == empty) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    void startSolving(final boolean nextRandom) {
        solve(0, nextRandom);
    }

    boolean solve(final int index, final boolean nextRandom) {
        if (index > len * len * len) {
            return isSolved();
        }
        final int i = index / len / len;
        final int j = index / len % len;
        final int k = index % len;
        if (!isProbableSolvable(i)) {
            return false;
        }

        if (withMagicCuboid && i == 2 && j == 2 && k == 2) {
            // skip this step
            return solve(index + 1, nextRandom);
        }

        if (nextRandom) {
            int r = (int) (Math.random() * randomCandidates.length);
            for (int ri = 0; ri < candidates.length; ri++) {
                int current = randomCandidates[r][ri];
                if (current == 2) {
                    // take an abbreviation
                    if (insert(current, i, j, k, 0)) {
                        if (isSolved()) {
                            return true;
                        }
                        if (isProbableSolvable(i)) {
                            if (solve(index + 1, true)) {
                                return true;
                            }
                        }
                        remove(current, i, j, k, 0);
                    }
                } else {
                    // take all directions
                    for (int d = 0; d < 6; d++) {
                        if (insert(current, i, j, k, d)) {
                            if (isSolved()) {
                                return true;
                            }
                            if (isProbableSolvable(i)) {
                                if (solve(index + 1, true)) {
                                    return true;
                                }
                            }
                            remove(current, i, j, k, d);
                        }
                    }
                }
            }
        } else {
            for (int current = 0; current < candidates.length; current++) {
                if (current == 2) {
                    // take an abbreviation
                    if (insert(current, i, j, k, 0)) {
                        if (isSolved()) {
                            return true;
                        }
                        if (isProbableSolvable(i)) {
                            if (solve(index + 1, false)) {
                                return true;
                            }
                        }
                        remove(current, i, j, k, 0);
                    }
                } else {
                    // take all directions
                    for (int d = 0; d < 6; d++) {
                        if (insert(current, i, j, k, d)) {
                            if (isSolved()) {
                                return true;
                            }
                            if (isProbableSolvable(i)) {
                                if (solve(index + 1, false)) {
                                    return true;
                                }
                            }
                            remove(current, i, j, k, d);
                        }
                    }
                }
            }
        }

        // May we find a solution by leaving this index empty?
        return solve(index + 1, nextRandom);
    }

    public static void solveAndPrint(final int maxCandidates, final boolean withMagicCuboid, final boolean nextRandom) {
        System.out.println("Start solving with: maxCandidates = " + maxCandidates + ", withMagicCuboid = " + withMagicCuboid + ", nextRandom = " + nextRandom);
        Box box = new Box(maxCandidates, withMagicCuboid);
        box.startSolving(nextRandom);
        System.out.println(box.isSolved());
        System.out.println(Arrays.toString(box.available));
        for (int i = 0; i < box.solution.length; i++) {
            System.out.println(Arrays.deepToString(box.solution[i]));
        }
    }

    public static void main(final String[] args) {
        solveAndPrint(23, true, true);
        solveAndPrint(6, true, true);
    }
}

Ausblick:

Vielleicht wäre ein Port in C++ sinnvoll, um es noch schneller lösen zu können.

Noch eine Anmerkung:

In Zeile 166 kann man den Spaß auch schon bei index >= len * len * len abbrechen... Dadurch spart man ggf. noch einmal etwas Zeit ein.

*john 0

@wob sagte in Wie oft passt ein Quader in einen größeren Quader?:

@john-0 In Spezialfällen mit Rechtfertigung: ok. Ansonsten nicht.

Diesen Ungetüm an Schleifen ist nicht gut, allerdings sollte man aus den korrekten Gründen ihn kritisieren. Die innere Schleife ist unsinnig, da sie postwendend durch das switch case Konstrukt ausgehebelt wird. Wenn man performanten Code schreiben will, und somit auf die Auslagerung von Schleifen verzichtet, so dass der Compiler besser optimieren kann, dann sollte man auch ein Loop Unrolling in der innersten Schleife machen. Ob die Schleifen hier der sinnvolle Weg ist, ist ja durchaus berechtigt angesprochen worden.

Allgemein ist der Nutzer „NoIDE“, das Verhalten lässt auf eine neue Inkarnation von Fragender vermuten, wenig einsichtig, und ich habe vollstes Verständnis, wenn Du ihm nicht antworten willst.

*john 0

@NoIDE sagte in Wie oft passt ein Quader in einen größeren Quader?:

Nicht so frech, bitte.

Irgend wie hast Du ein Problem damit, wenn man vollkommen normale Fragen aufwirft, die in diesem Kontext naheliegend sind. „Frech“ ist hier nur Deine Antwort. Wenn Du mit Rückfragen nicht umgehen kannst, dann reiß Dich entweder zusammen, oder verschone das Forum doch in Zukunft mit Deinen Beiträgen.