Wie oft passt ein Quader in einen größeren Quader?
-
Bin verwirrt und etwas stimmt mit meinem Code nicht.
Ein Quader (1x2x4) soll in einen größeren Quader (4x4x4) platziert werden. Wie oft unterschiedlich ist das möglich?
Mögliche Operationen sind:
- Verschiebung um 1 nach oben, unten, links, rechts, vor, zurück
- Drehen um 90° um eine der Achsen
- Kippen um 90° (das ist eigentlich zweimal drehen)
#include <iostream> int main(int argc, char const *argv[]) { const int dim[] = {1, 2, 4}; const int len = 4; for (size_t x = 0; x < len; x++) { for (size_t y = 0; y < len; y++) { for (size_t z = 0; z < len; z++) { for (size_t i = 0; i < dim[0]; i++) { for (size_t j = 0; j < dim[1]; j++) { for (size_t k = 0; k < dim[2]; k++) { for (size_t l = 0; l < 6; l++) { int x2 = x, y2 = y, z2 = z; switch (l) { case 0: x2 += i; y2 += j; z2 += k; break; case 1: x2 += i; y2 += k; z2 += j; break; case 2: x2 += j; y2 += i; z2 += k; break; case 3: x2 += j; y2 += k; z2 += i; break; case 4: x2 += k; y2 += i; z2 += j; break; case 5: x2 += k; y2 += j; z2 += i; break; } if (x2 >= 0 && x2 < dim[0] && y2 >= 0 && y2 < dim[1] && z2 >= 0 && z2 < dim[2]) std::cout << x << " " << y << " " << z << " " << l << " " << x2 << " " << y2 << " " << z2 << std::endl; } } } } } } } return 0; }
-
Der Code ist nicht lesbar. 7 verschachtelte Schleifen! Ernsthaft?
-
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.
-
@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.
-
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.
-
@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*
-
@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
-
@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.
-
@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.
-
@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 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?
-
@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:
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 = 1x1x1Anbei 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 * lenabbrechen... Dadurch spart man ggf. noch einmal etwas Zeit ein.
