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

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.

@john-0

@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?

Das war nun mal, rein objektiv betrachtet, vom Umgangston her eher daneben... Und das sollte man auch sagen können dürfen.

Zurück zum Thema. Das Problem ist doch schon gelöst, und die innere Schleife habe ich in Zeile 185 bis 213 und in Zeile 217 bis 245 doch schon partiell ausgerollt.

Eine Darstellung einer möglichen Lösung wäre zum Beispiel:

https://postimg.cc/p9484mqm

wobei ein Objekt immer aus gleichen Zahlen besteht und die gleiche Farbe hat.

Nach meiner Vermutung lässt sich die Anzahl der inneren Schleifen beim Backtracking nicht weiter reduzieren.

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

Allgemein ist der Nutzer „NoIDE“, das Verhalten lässt auf eine neue Inkarnation von Fragender vermuten

Das ist richtig.

*john 0

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

Das war nun mal, rein objektiv betrachtet, vom Umgangston her eher daneben... Und das sollte man auch sagen können dürfen.

Objektiv? Du meintest wohl subjektiv. Du eckst hier im Forum immer wieder an, weil Du Nachfragen komplett fehlinterpretierst und als persönlichen Angriff wertest, und anschließend Dich daneben benimmst. Das führt dann zu den wiederholten Accountsperren. Daher kannst Du auch nicht ernsthaft erwarten, dass man Dich im Forum mit einer besonderen Höflichkeit behandelt, wenn man davon ausgehen muss, dass es wieder dieselbe Person ist, die sich nicht zu benehmen weiß.

@john-0
Ja, ich hatte mich mal danebenbenommen, und unliebsame Themen angesprochen, aber in der jüngeren Vergangenheit ist doch nichts derartiges mehr vorgekommen?
Deshalb wünsche ich mir einfach nur einen normalen Umgangston.

*john 0

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

@john-0
Ja, ich hatte mich mal danebenbenommen, und unliebsame Themen angesprochen, aber in der jüngeren Vergangenheit ist doch nichts derartiges mehr vorgekommen?

Auf eine berechtigte Frage im Thread reagierst Du mit unpassenden Verhalten, wenn das nicht in der jüngeren Vergangenheit war, was ist dann die jüngere Vergangenheit? Die letzten fünf Minuten?

@john-0
Bitte belege deine Aussage.

*john 0

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

@john-0
Bitte belege deine Aussage.

Muss man Dich ernsthaft daran erinnern?

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

@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.

Ja, dazu stehe ich doch auch, der Ton war daneben. Man kann sachliche Kritik auch sachlich kommunizieren.