Crackless Wall, #10 from overclock.net

Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal×vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".

There are eight ways of forming a crack-free 9x3 wall, written W(9,3) = 8.

Calculate W(32,10).

Warning: Large values (16+) have a probably will cause your browser to display a "Script Execution Time" error. ... for those of you still brave enough... type in values to calculate the number of unique tables: W(,)

In an attempt to organize my own thoughts, I am making a high level outline with some pseudocode.

Class Row Row->cracks = integer (used as a bit array of crack positions, see source code comments for more details) Row->width = integer width Row->findTables(allRows, tableHeight, count) = returns an int for the number of possible tables that can be created from an array of possible Row objects allRows, and a size tableHeight, starting from int count. It's fully recursive. Row->matchesBelow(row) does binary operation on cracks property to determine if they are a match or not. main() 1. Generate All Possible Row Objects 2. Foreach Row Object, find all its possible matches (Optional. See Below) 3. Foreach Row Object, call findTables method to find every unique path / table 4. Return totalCount

You can reach me on AIM, s/n = dizdique or gchat = dizdique@gmail.com

Link back to home Walrus walrus page