Unique Panel Combinations with Blocks -- Code in Java

Question

I have a project in which i have to create a panel from blocks that are 3x1 and 4.5x1. For structural integrity, the spaces between the blocks must not line up in adjacent rows. I have to calculate all possible combinations. Some examples are a 7.5x1 panel has 2 possible solutions, a 7.5x2 panel has 2 possible solutions, a 12x3 panel has 4 possible ways, and a 27x5 has 7958 possible ways. My problem is when I get up into the higher widths I am getting more solutions then I should. I think this has to do with that there is a possibility that I am getting duplicate tables, but I cannot see where it is happening or how to fix it. Any help would be greatly appreciated. Code follows below.

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

import puzzle.Row;

public class panel {
/**
 * This program will return the number of unique tables that for structural      integrity don't have blocks that line up
 * in adjacent rows.  The width is to be between 3 and 48 and the height between 1 and 10.  The width
 * should also be a multiple of 0.5.
 * 
 * @param width, height
 * @return totalTables
 */
public static void main(String[] args) {
    int width = 0;
    int height = 0;

    // Check to make sure that two arguments were passed.
    if (args.length != 2) {
        System.out.println("Please enter both a height and a width.");
        System.exit(1);
    } else {
        // Check that a data type of double was entered.
        if ( ( args[0].matches("^[0-9]+(\\.[0-9]+)?$") ) && 
                ( Double.valueOf(args[0].trim()).doubleValue() >= 3.0 ) && 
                ( Double.valueOf(args[0].trim()).doubleValue() <= 48.0 ) && 
                ( Double.valueOf(args[0].trim()).doubleValue()) % 0.5 == 0 ) {
            width = (int) (Double.valueOf(args[0].trim()).doubleValue() * 2); // Double the width so that we are working with an integer.
        } else {
            System.out.println("Please enter a number for your width that is between 3 and 48 and divisable by 0.5.");
            System.exit(1);
        }
        // Check that a data type of integer was entered.
        if ( ( args[1].matches("^[0-9]+$") ) && ( Integer.valueOf(args[1]) >= 1 ) && ( Integer.valueOf(args[1]) <= 10 )) {
            height = Integer.valueOf(args[1].trim()).intValue();
        } else {
            System.out.println("Please enter an integer for your height that is between 1 and 10.");
            System.exit(1);
        }

        List<Row> allRows = new ArrayList<Row>(); // Holds all the possible rows and needed information
        findAllRows(width, 0, 0, allRows);
        findMatches(allRows);
        long totalTables = findUniqueTables(allRows, height);
        System.out.println(totalTables);
    }
}

/**
 * Recursively calculates all possible row combinations for supplied width.
 * Row configuration is stored in binary format with 1 indicating gaps.  Each bit is
 * represented by 3 inches.  The bits 1, 2, nth are dropped as they are not needed.
 * 
 * i.e. width of 12 would produce
 * width = 12 * 2 = 24
 * 
 * Bricks               Binary              Stored Binary   Decimal Value
 * 6 x 6 x 6 x 6        0 1 0 1 0 1 0 1     1 0 1 0 1       21
 * 9 x 9 x 6            0 0 1 0 0 1 0 1     0 1 0 0 1       9
 * 9 x 6 x 9            0 0 1 0 1 0 0 1     0 1 0 1 0       10
 * 6 x 9 x 9            0 1 0 0 1 0 0 1     1 0 0 1 0       18
 */

public static void findAllRows(int width, int currLen, int rowConfig, List<Row> root) {
    if (currLen + 6 == width) {
        root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
        return;
    } else if (currLen + 9 == width) {
        rowConfig = rowConfig << 1;
        root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
        return;
    } else if (currLen + 6 > width) {
        return; // Current configuration is longer than the width is allowed.  Do not add.
    } else {
        int nextConfig = (rowConfig << 2) + 1;  //
        findAllRows(width, currLen + 6, nextConfig, root);

        nextConfig = (rowConfig << 3) + 1;
        findAllRows(width, currLen + 9, nextConfig, root);
    }
    return;
}

/**
 * Finds all possible row matches for the given row that do not have gaps that line up.
 */
public static void findMatches(List<Row> rows) {
    for (Row row : rows) {
        for (Row rowC : rows) {
            if (matchesBelow(row.getGaps(), rowC.getGaps())) {
                row.addChilcRows(rowC.getGaps());
            }
        }
    }
}

/**
 * Does a bitwise AND to see if there are any gaps that line up.  If there are no gaps then
 * the resulting AND should equal to 0.
 */
public static boolean matchesBelow(int row, int rows) {
    if ((row & rows) == 0) {
        return true;
    } else {
        return false;
    }
}

/**
 * Finds all the unique tables and returns the count.
 */
public static long findUniqueTables(List<Row> allRows, int height) {
    long tableCount = 0;
    for (Row row : allRows) {
        tableCount += findTables(row, height);
    }
    return tableCount;
}


/**
 * This makes all possible tables.
 */
public static long findTables(Row row, int tableHeight) {
    long count;
    if (tableHeight == 1) {
        return 1;
    } else {
        count = 0;
        for (int i = 0; i < row.getChildRowsSize(row); i++) {
            count += findTables(row, tableHeight -1);
        }   
    }
    return count;
}
}

And my puzzle.Row class.

package puzzle;

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

public class Row {
int gaps;
int width;
List<Long> potChildRows = new ArrayList<Long>();

public Row(int width, int gaps) {
    this.gaps = gaps;
    this.width = width;
}

public int getGaps() {
    return this.gaps;
}

public int getWidth() {
    return this.width;
}

public long getChildRowsSize(Row row) {
    return row.potChildRows.size();
}

public void addChilcRows(long row) {
    this.potChildRows.add(row);
}
}

Answer 1

I think I just solved the assignment. Even though it's been two months since the question was asked, I thought it looked like a fun problem to solve, so I gave it a shot. I don't want to post my code due to "Homework" tag (even after 2 months), so I will just describe my approach. I used Python, but I will try to translate any terminology into Java.

First, I feel like you're keeping track of way more data than you need. I just kept an ArrayList of doubles such that for any double i, i refered to a ix1 block. The list was ordered such that row[0] was the leftmost block and row[row.length-1] was the rightmost block. For example, [3, 3, 4.5] refers to a row of length 10.5 using, from left to right, a 3x1 block, another 3x1 block, and a 4.5x1 block. Using this simple structure I can easily visualize my configuration. My row length is as easy as adding all the elements together (i.e. 3 + 3 + 4.5 = 10.5). My gaps are as easy as keeping a running total while iterating through my list (i.e. my gaps are 3 and 3 + 3 = 6). Using this simpler datatype you can greatly simply your code.

Also, I found it helpful to think of the problem as a modified Depth-First Search. Using DFS and given a binary tree, starting from the root you first try to go all left. Then you try to go all left but one the last node. And so on. Instead of "left" and "right", think "3" and "4.5", where the value of the node is the width and you stop traversing the tree once the width becomes greater than the desired width, width. If you find a node with a value of exactly width, that path is now a possible row, remember it. In other words, you build your rows left to right first trying N 3x1 blocks (such that width + 2.5 >= N*3 >= width). Then you try (N-1) 3x1 blocks and 1 4x1 block (the 4x1 being the right most). Then (N-2) 3x1s, one 4x1, and one more 3x1. And so on. No bitshifts, no rowConfig variable, just an ArrayList of block widths. Also, since you systematic traveled each path (i.e. tried each combination) once and only once, you know you've tried every combination and you know there are no duplicates.

Now, building your wall. This can also be treated as a modified DFS. Imagine an n-ary tree where n is equal to the number of potential rows of width width. Using the same, systematic approach, try every path until you have a wall of height height (since each row is of height 1). But remember, you only want to traverse a path if none of the gaps are adjancent. Try building the wall one row at a time, from the bottom up. By adding a new row to the top of the wall if and only if none of it's gaps are adjancent to the gaps in the top row, you can trust that your partial wall is always valid. There, once you hit height, you know you have a valid wall. Record the path and continue until there are no more valid paths left to explore.

I apologize for not answering while you were still doing your assignment. I'd be interested to know how your final solution differed from mine.