Wooden Box

Task Description Link to heading

This was my very first coding project :)

Essentially, I was presented with a wooden box containing 14 smaller wooden boxes of varying sizes and shapes - some of them were cubes, while others were not. My objective was to fit all the smaller wooden boxes neatly inside a larger wooden box, ensuring that there was no wasted space.

While one could certainly attempt to solve this problem manually by trying out different combinations, I opted to develop a program to tackle it instead. By doing so, I was able to simplify the process and more efficiently arrive it a viable solution.

A special thanks goes to NoRelect who gave me this task and helped me to achieve my first result. Also thank you to J.L who even got a faster working solution in Python and removed all the Object instantiations.

Code Link to heading

import java.util.HashSet;
import java.util.Set;

public class Solver {
    private final boolean[][][] boxContainer;
    private final int[][] boxes;
    private final boolean[] used;

    public Solver(int[][] boxes, boolean[][][] boxContainer, boolean[] used) {
        this.boxContainer = boxContainer;
        this.boxes = boxes;
        this.used = used;
    }

    //check if the box is placeable --> is it inside the box? does any other box collide with the current one?
    private boolean placeable(int x, int y, int z, int[] box) {
        for (int i = x; i < x + box[0]; i++) {
            for (int j = y; j < y + box[1]; j++) {
                for (int k = z; k < z + box[2]; k++) {
                    if (i >= boxContainer.length || j >= boxContainer[0].length ||
                            k >= boxContainer[0][0].length || boxContainer[i][j][k]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private void removeBox(int x, int y, int z, int[] box) {
        for (int i = x; i < x + box[0]; i++) {
            for (int j = y; j < y + box[1]; j++) {
                for (int k = z; k < z + box[2]; k++) {
                    boxContainer[i][j][k] = false;
                }
            }
        }
    }

    private void placeBox(int x, int y, int z, int[] box) {
        for (int i = x; i < x + box[0]; i++) {
            for (int j = y; j < y + box[1]; j++) {
                for (int k = z; k < z + box[2]; k++) {
                    boxContainer[i][j][k] = true;
                }
            }
        }
    }

    //first occurrence of a false
    private int[] findPos() {
        for (int i = 0; i < boxContainer.length; i++) {
            for (int j = 0; j < boxContainer[0].length; j++) {
                for (int k = 0; k < boxContainer[0][0].length; k++) {
                    if (!boxContainer[i][j][k]) {
                        return new int[] {i, j, k};
                    }
                }
            }
        }
        return null;
        //no position found
    }

    //put all rotation in a hashset TODO: check if I need an override equal method for the hashset --> array as an object
    private Set<int[]> getAllRotations(int box) {
        Set<int[]> hashSet = new HashSet<>();
        hashSet.add(new int[]{boxes[box][0], boxes[box][1], boxes[box][2]});
        hashSet.add(new int[]{boxes[box][0], boxes[box][2], boxes[box][1]});
        hashSet.add(new int[]{boxes[box][1], boxes[box][2], boxes[box][0]});
        hashSet.add(new int[]{boxes[box][1], boxes[box][0], boxes[box][2]});
        hashSet.add(new int[]{boxes[box][2], boxes[box][1], boxes[box][0]});
        hashSet.add(new int[]{boxes[box][2], boxes[box][0], boxes[box][1]});
        return hashSet;
    }

    public void solve() {
        solve(0);
    }

    private boolean solve(int numBox) {
        //numBox = number of boxes --> if it is full, recursion stops
        if (numBox == boxes.length) {
            System.out.println("There is a solution");
            return true;
        }

        int[] pos = findPos();
        for (int i = 0; i < boxes.length; i++) {
            //the box is already used or there does no position exist
            if (used[i] || pos == null) {
                continue;
            }
            Set<int[]> comb = getAllRotations(i);
            //TODO: check if it is better to use x, y, z or if I should stick with pos[0]...
            int x = pos[0];
            int y = pos[1];
            int z = pos[2];
            for (int[] box : comb) {
                if (placeable(x, y, z, box)) {
                    used[i] = true;
                    placeBox(x, y, z, box);
                    if (solve(numBox + 1)) {
                        System.out.println("Box{" + "length=" + box[0] + ", width=" + box[1] + ", height=" + box[2] + "}"
                                + " Coordinates: x: " + x + " y: " + y + " z: " + z);
                        return true;
                    }
                    //if recursion doesn't work with this order, remove the box again
                    removeBox(x, y, z, box);
                    used[i] = false;
                }
            }
        }
        return false;
    }
}