Menu
Topics Index
...
`

Weekend Hack - 06 Jul 2013 - Results

Thanks to Pramod Jain for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Given the experience of the participants, they were really innovative and clean. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 06 Jul 2013 - 1 is Pramod Jain. He will get a recharge or gift voucher worth Rs. 300.

To fit the blocks such that it forms a perfect rectangular box with out any gaps

Write a program to fit the blocks such that it forms a perfect rectangular box with out any gaps. The blocks are further comprised of cells and they are of irregular shape. In the integer array defining the block, 0 indicates there is no cell and 1 indicates cell. The blocks given might be any direction and they might have to be turned to fit into a proper block. Also note that the answers given here are indicative and any other solution will also be accepted as long as it is perfect rectangular box with out any gaps.

Input (List) Output (char[][])
{[A, {{1, 1, 0}, {1, 1, 1}, {1, 1, 1}, {1, 1, 0}, {1, 1, 0}}], [B, {{1, 1, 0, 0}, {0, 1, 1, 1}}], [C, {{1, 1, 1}, {0, 0, 1}}], [D, {{0, 1, 1}, {1, 1, 1}}], [E, {{1, 0}, {1, 1}}], [F, {{0, 1, 1}, {0, 1, 1}, {1, 1, 1}}], [G, {{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 1, 1, 1}}], [H, {{1, 1}, {1, 1}, {1, 1}, {1, 1}}], [I, {{1}, {1}, {1}, {1}}]}
A A B B C C C G G D D
A A A B B B C G D D D
A A A E F F F G G G G
A A E E F F F H H H H
A A I I I I F H H H H
{[A, {{1, 0, 0}, {1, 1, 1}, {0, 0, 1}}], [B, {{1, 1, 1, 1}, {0, 0, 1, 0}, {0, 0, 1, 0}}], [C, {{0, 1, 1}, {1, 1, 1}, {1, 0, 1}}], [D, {{1}}], [E, {{1, 1}}] } A B B B B C C
A A A B C C C
E E A B C D C
{[A, {{1, 1, 1, 1, 1}}], [B, {{1, 1, 1, 1, 1}}], [C, {{1, 1, 1, 1, 1}}]} A A A A A B B B B B C C C C C
{[A, {{1, 1, 1}}], [B, {{1, 1, 1}, {0, 1, 0}}], [C, {{1, 0}, {1, 1}}], [D, {{1, 1}}], [E, {{1, 1}, {1, 1}}]} C C B A A A E E
C B B B D D E E
{[A, {{1, 1}, {0, 1}}], [B, {{0, 0, 1}, {1, 0, 1}, {1, 1, 1}}]} A A B
B A B
B B B

Solution 1 - Submitted on Sat Jul 6 23:30:17 2013

import java.util.ArrayList;
import java.util.List;

public class FitBolcks {

    public static void main(String s[]) {
        int[][] aPositions = {{1, 1, 0}, {1, 1, 1}, {1, 1, 1}, {1, 1, 0}, {1, 1, 0}};
        Block aBlock = new Block('A', aPositions);
        int[][] bPositions = {{1, 1, 0, 0}, {0, 1, 1, 1}};
        Block bBlock = new Block('B', bPositions);
        int[][] cPositions = {{1, 1, 1}, {0, 0, 1}};
        Block cBlock = new Block('C', cPositions);
        int[][] dPositions = {{0, 1, 1}, {1, 1, 1}};
        Block dBlock = new Block('D', dPositions);
        int[][] ePositions = {{1, 0}, {1, 1}};
        Block eBlock = new Block('E', ePositions);
        int[][] fPositions = {{0, 1, 1}, {0, 1, 1}, {1, 1, 1}};
        Block fBlock = new Block('F', fPositions);
        int[][] gPositions = {{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 1, 1, 1}};
        Block gBlock = new Block('G', gPositions);
        int[][] hPositions = {{1, 1}, {1, 1}, {1, 1}, {1, 1}};
        Block hBlock = new Block('H', hPositions);
        int[][] iPositions = {{1}, {1}, {1}, {1}};
        Block iBlock = new Block('I', iPositions);
        List blocks = new ArrayList();
        blocks.add(aBlock);
        blocks.add(bBlock);
        blocks.add(cBlock);
        blocks.add(dBlock);
        blocks.add(eBlock);
        blocks.add(fBlock);
        blocks.add(gBlock);
        blocks.add(hBlock);
        blocks.add(iBlock);
        char[][] result = fitBlocks(blocks);
        System.out.println("The rectangular box after the arrangement is : \n");
        if (result != null) {
            for (char[] row : result) {
                for (char element : row) {
                    System.out.print(element + " ");
                }
                System.out.println(" ");
            }
        }
    }

    public static char[][] fitBlocks(List blocks) {
        int count = 0, max_no_of_rows = 0;
        // count gives total number of 1's in all the arrays of the list.
        // max_no_of_rows gives the maximum number of rows present among the arrays in the list.
        for (int i = 0; i < blocks.size(); i++) {
            int no_of_rows = blocks.get(i).positions.length;
            if (no_of_rows > max_no_of_rows) {
                max_no_of_rows = no_of_rows;
            }
            for (int j = 0; j < no_of_rows; j++) {
                int[][] matrix = blocks.get(i).positions;
                for (int k = 0; k < matrix[j].length; k++) {
                    if (matrix[j][k] == 1) {
                        count++;
                    }
                }
            }
        }
        while (count % max_no_of_rows != 0) {
            max_no_of_rows++;
        }
        int columns = count / max_no_of_rows;
        char[][] result = new char[max_no_of_rows][columns];
        // Initializing all elements to '0'
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                result[i][j] = '0';
            }
        }
        // calling the recursive function..
        return solve(result, blocks, 0);
    }

    public static char[][] solve(char[][] result, List blocks, int number) {
        // If all arrays are inserted then number gets equal to blocks.size so return the answer.
        if (number == blocks.size()) {
            return result;
        }
        for (int j = 0; j < result.length; j++) {
            for (int k = 0; k < result[0].length; k++) {
                // calling isPossible function which returns boolean, telling whether the given block can be inserted at the given position or not
                if (isPossible(blocks.get(number).positions, j, k, result)) {
                    // If true ,fill the elements at respective places with respective character according to the given block
                    fill(blocks.get(number), j, k, result);
                    // Checking whether this leads to a solution or not
                    if (solve(result, blocks, number + 1) != null) {
                        return result;
                    }
                    //If it does not lead to a solution then remove previously added block elements
                    else {
                        unfill(blocks.get(number), j, k, result);
                    }
                }
                // same procedure , but here we are considering the block which is rotated 90D in anti-clock-wise direction
                int[][] rotatedLeft = rotateLeft(blocks.get(number).positions);
                if (isPossible(rotatedLeft, j, k, result)) {
                    Block temporaryBlock = new Block(blocks.get(number).code, rotatedLeft);
                    fill(temporaryBlock, j, k, result);
                    if (solve(result, blocks, number + 1) != null) {
                        return result;
                    } else {
                        unfill(temporaryBlock, j, k, result);
                    }
                }
                // same procedure , but here we are considering the block which is rotated 90D in clock-wise direction
                int[][] rotatedRight = rotateRight(blocks.get(number).positions);
                if (isPossible(rotatedRight, j, k, result)) {
                    Block temporaryBlock = new Block(blocks.get(number).code, rotatedRight);
                    fill(temporaryBlock, j, k, result);
                    if (solve(result, blocks, number + 1) != null) {
                        return result;
                    } else {
                        unfill(temporaryBlock, j, k, result);
                    }
                }
            }
        }
        return null;
    }

    // Function which returns a double dimensional array of given block rotated to 90D to its left
    public static int[][] rotateLeft(int[][] originalBlock) {
        int[][] rotatedBlock = new int[originalBlock[0].length][originalBlock.length];
        for (int i = originalBlock[0].length - 1, x = 0; i >= 0; i--, x++) {
            for (int j = 0, y = 0; j < originalBlock.length; j++, y++) {
                rotatedBlock[x][y] = originalBlock[j][i];
            }
        }
        return rotatedBlock;
    }

    //Function which returns a double dimensional array of given block rotated to 90D to its right
    public static int[][] rotateRight(int[][] originalBlock) {
        int[][] rotatedBlock = new int[originalBlock[0].length][originalBlock.length];
        for (int i = 0, x = 0; i < originalBlock[0].length; i++, x++) {
            for (int j = originalBlock.length - 1, y = 0; j >= 0; j--, y++) {
                rotatedBlock[x][y] = originalBlock[j][i];
            }
        }
        return rotatedBlock;
    }

    // Function to check whether the given block can be inserted at a given position or not
    public static boolean isPossible(int[][] temporaryArray, int row, int column, char[][] result) {
        // conditions for elements of block to be with in the size of result array.
        if (row + temporaryArray.length > result.length || column + temporaryArray[0].length > result[0].length) {
            return false;
        }
        // conditions to check whether an element is already present at the position where a new element is to be inserted.
        for (int countRow = 0; countRow < temporaryArray.length; countRow++) {
            for (int countColumn = 0; countColumn < temporaryArray[countRow].length; countColumn++) {
                if ((countColumn >= temporaryArray[countRow].length || (temporaryArray[countRow][countColumn] != 0 && result[countRow + row][countColumn + column] != '0'))) {
                    return false;
                }
            }
        }
        return true;
    }

    // Function to fill the result array with the block passed.
    public static void fill(Block block, int row, int column, char[][] result) {
        int[][] temporaryArray = block.positions;
        char characterFilled = block.code;
        for (int countRow = 0; countRow < temporaryArray.length; countRow++) {
            for (int countColumn = 0; countColumn < temporaryArray[countRow].length; countColumn++) {
                if (temporaryArray[countRow][countColumn] == 1)
                    result[row + countRow][column + countColumn] = characterFilled;
            }
        }
    }

    // Function to remove the given block of elements from the result array 
    public static void unfill(Block block, int row, int column, char[][] result) {
        int[][] temporaryArray = block.positions;
        char characterRemoved = block.code;
        for (int countRow = 0; countRow < temporaryArray.length; countRow++) {
            for (int countColumn = 0; countColumn < temporaryArray[countRow].length; countColumn++) {
                if (result[row + countRow][column + countColumn] == characterRemoved) {
                    result[row + countRow][column + countColumn] = '0';
                }
            }
        }
    }
}

enum Direction {
    South, East, West, North;
}

class Block {

    char code;
    int[][] positions;

    public Block(char code, int[][] positions) {
        this.code = code;
        this.positions = positions;
    }

    public char getCode() {
        return code;
    }

    public int[][] getPositions() {
        return positions;
    }
}

Comments :

© meritcampus 2019

All Rights Reserved.

Open In App