CareerCup

can you give an example of how an crack-free wall may lay out?

First, for one layer, use recursion to computer the number of possible combinations. f(m) = f(m-3)+f(m-2), f(3)=1, f(2)=1, f(1)=0, f(0)=0. Second, obtain a conflict matrix, where an item is 1 is patten i is conflict with pattern j (by looking at their cumulative sum (a sorted array), then finding the identical value in two sorted arrays (similar to merge operation)). Next, considering the other dimension, we have to record the maximum ways to lay bricks in n-1 layer for each possible patten on layer n-1 (or g(n-1, i), i \in [f(m)]). Finally, use dynamic programming to compute $g(n,i) = \sum_{k:k,i \textrm{ is compatible }} g(n-1, k), g(n) = \sum_i g(n,i)$.

hi canger
will be elaboratng your above explanation. Actually I did not get or post some link where We could get detail explanation about it.
The first for finding the number of ways in which one layer brick can be formed is undersatnble ..but for remaining part ..please elaborate it

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Bricks {

	public static int getPatterns(int rowNumber, int rowSize)
	{
		return generateCount(1, rowNumber, rowSize, null);
	}
	
	private static int generateCount(int rowNumber, int rowMax, int rowSize, Pattern previousRow)
	{
		if(rowNumber == rowMax)
		{
			List<Pattern> rowPatterns = generateRow(0, previousRow, rowSize);
			return rowPatterns.size();
		}else
		{
			int result = 0;
			List<Pattern> rowPatterns = generateRow(0, previousRow, rowSize);
			for(Pattern pattern:rowPatterns)
			{
				result += generateCount(rowNumber + 1, rowMax, rowSize, pattern);
			}
			return result;
		}
	}
	private static List<Pattern> generateRow(int startingBrickLocation, Pattern previousPattern, int rowSize)
	{
		if(startingBrickLocation + 2 > rowSize)
		{
			return null;
		}else
		{
			List<Pattern> returnList = new ArrayList<Pattern>();
			if((startingBrickLocation + 2) == rowSize || (startingBrickLocation + 3) == rowSize)
			{
				Set<Integer> brickSet = new HashSet<Integer>();
				brickSet.add(rowSize);
				returnList.add(new Pattern(brickSet));
				return returnList; 
			}else
			{
				if(previousPattern == null || !previousPattern.getBrickLocations().contains(startingBrickLocation + 2))
				{
					List<Pattern> restPatterns1 = generateRow(startingBrickLocation + 2, previousPattern , rowSize);
					if(restPatterns1 != null)
					{
						for(Pattern pattern:restPatterns1)
						{
							returnList.add(Pattern.prepend(pattern, startingBrickLocation + 2));
						}
					}
				}
				if(previousPattern == null ||!previousPattern.getBrickLocations().contains(startingBrickLocation + 3))
				{
					List<Pattern> restPatterns2 = generateRow(startingBrickLocation + 3, previousPattern , rowSize);
					if(restPatterns2 != null)
					{
						for(Pattern pattern:restPatterns2)
						{
							returnList.add(Pattern.prepend(pattern, startingBrickLocation + 3));
						}
					}
				}
				
				
				return returnList;
			}
		}
		
	}
}

class Pattern
{
	// this data structure records the end location of each brick in this pattern.
	Set<Integer> brickLocations;
	

	
	public Pattern(Set<Integer> brickLocations)
	{
		this.brickLocations = brickLocations;
	}
	

	public Set<Integer> getBrickLocations() {
		return brickLocations;
	}

	public void setBrickLocations(Set<Integer> brickLocations) {
		this.brickLocations = brickLocations;
	}
	
	
	public static Pattern prepend(Pattern pattern, int brickLocation)
	{
		Set<Integer>brickLocations = pattern.getBrickLocations();
		brickLocations.add(brickLocation);
		return new Pattern(brickLocations);
	}
	

}

The strategy used here is same as what Canger outlined. Python code follows:

def brickwall(w,h):
    # generate single brick layer of width w (by recursion)
    def gen_layers(w):
        if w in (0,1,2,3):
            return {0:[], 1:[], 2:[[2]], 3:[[3]]}[w]
        return [(layer + [2]) for layer in gen_layers(w-2)] + \
               [(layer + [3]) for layer in gen_layers(w-3)]
    # precompute info about whether pairs of layers are compatible
    def gen_conflict_mat(layers, nlayers, w):
        # precompute internal brick positions for easy comparison
        def get_internal_positions(layer, w):
            acc = 0; intpos = set()
            for brick in layer:
                acc += brick; intpos.add(acc)
            intpos.remove(w)
            return intpos
        intpos = [get_internal_positions(layer, w) for layer in layers]        
        mat = []
        for i in range(nlayers):
            mat.append([j for j in range(nlayers) \
                              if intpos[i].isdisjoint(intpos[j])])
        return mat
    layers = gen_layers(w)
    nlayers = len(layers)
    mat = gen_conflict_mat(layers, nlayers, w)
    # dynamic programming to recursively compute wall counts
    nwalls = nlayers*[1]
    for i in range(1,h):
        nwalls = [sum(nwalls[k] for k in mat[j]) for j in range(nlayers)]
    return sum(nwalls)

print(brickwall(9,3))   #8
print(brickwall(18,5))  #7958
print(brickwall(32,10)) #806844323190414

Hi,

Can you please elaborate on the logic.. i'm using perl to find a solution.. This is what i've done so far..

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)

Adding all these n's should give the count of all possible combinations . But i have no idea on how to find the real combinations for one row and how to proceed further.. Please help..

Can I get the code for this in C / C++ asap? Thanks much in advance for your help.

Can I get the code in C / C++ for this ? I need it urgently. Please help me. Thanks.
Vivek