2

I'm working on a problem right now and am having a bit of trouble.

Here's the question:

enter image description here

I've gotten to a point in the program where I can generate all possible rows for a given length and can calculate the number of other rows that align with each other. I can calculate base cases fairly quick, but my program is very naive and calculates walls recursively, with each of the possible rows as bases of a wall and which builds walls recursively on each possible leaf combination. As you can imaging, this isn't very efficient, and for anything above height 6 my program takes a very, very long time.

I've seen this problem on the forum from an earlier, but my question wasn't really answered and I couldn't reply to it. Help/ideas is/are greatly appreciated.

Oh, and I'm writing the program in c++.

EDIT: I'm having a lot of trouble, could someone look at my code and suggest improvements?

EDIT2: Ok, I have an answer now, I get 806844323190414 possible walls for a 48x10 inch wall. If anyone wants, I can post post my methodology/code, or just general advice.

riqitang
  • 3,241
  • 4
  • 37
  • 47

5 Answers5

4

Sounds like Dynamic Programming

http://en.wikipedia.org/wiki/Dynamic_programming

http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

lorean
  • 2,150
  • 19
  • 25
  • Yes, I was well aware of this (I've taken algorithms). It was breaking it down into subproblems where I was having issues. Thank you though. – riqitang Dec 29 '11 at 22:33
1

I'd look at this as a divide and conquer problem, you're given some examples for other panel sizes, why not see how many ways you could build a 48x10 panel using smaller panels, then look for the combinations that won't work along the edges of your smaller panels.

ridecar2
  • 1,968
  • 16
  • 34
  • This was what I was originally thinking. I was thinking of trying to build walls half the height, then recursively build walls half of the height, though I don't know if this method would miss walls. – riqitang Dec 29 '11 at 22:28
1

have you thought of reusing calculations?

eg: the first row will allow only some constellations of the second row. but if there is a third row that looks like one of the first one it has all the variants the second row had in relation to the first one.

Baarn
  • 673
  • 11
  • 23
  • I thought of this as well, maybe making a map of the base walls and combinations, but wasn't sure if this would miss walls. – riqitang Dec 29 '11 at 22:32
1

Observe that when you have built k rows, it's only the topmost (k th) row that restricts what the next row may look like. Consider the question "when I have built k rows and the topmost row looks like x, in how many ways can I build the remaining wall?" This can be solved by asking the same question for all compatible ways of making the k+1 th row and summing the results. The answer to the entire problem is the sum of the answers to the questions "When I have built 1 row and the topmost row looks like x", for all possible ways of building the first row. This problem can be solved using memoization or dynamic programming.

Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
1

If there are n ways of laying down a single row, then let 1 be the n x 1 vector of ones. Form an n by n adjacency matrix A, with each cell A_ij holding a zero if patterns i and j share a vertical edge (cannot appear next to each other), and a one otherwise. Clearly the major diagonal of A is filled with zeros.

Now, the solution is the norm

x' pow(A, height-1) x

where x' is the transpose, and pow(A, height-1) is the matrix exponential.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • Very informative. I saw this solution but had trouble making a matrix library, do you know of any online (for c/c++)? – riqitang Dec 30 '11 at 22:41
  • Maybe this question would help: http://stackoverflow.com/questions/3858652/c-library-for-calculating-the-matrix-exponential or http://stackoverflow.com/questions/3359608/looking-for-an-elegant-and-efficient-c-matrix-library – Ben Voigt Dec 30 '11 at 22:57
  • I'm still a little confused. Is the matrix exponential equal to the matrix (of ones and zeros) times e^(height-1)? – riqitang Jan 01 '12 at 18:47
  • @Sean: No, just like a normal exponent means a number multiplied by itself a certain number of times, a square matrix raised to an exponent means that matrix multiplied by itself (in the matrix sense) that many times. – Ben Voigt Jan 01 '12 at 18:52
  • BTW, there are more efficient ways of calculating the matrix power for very large exponents than repeated multiply, for example the characteristic equation relates eigenvalues to the matrix power. However, for your problem the rank is likely to be much much larger than the height, so just use repeated multiply. – Ben Voigt Jan 01 '12 at 19:14
  • I'm a little confused on the matrix exponential. If the matrix is just 0s and 1s, then wouldn't the exponential do nothing since multiplication by 1 is idempotent? – riqitang Jan 02 '12 at 18:00
  • Sean, it's a [matrix multiply](http://en.wikipedia.org/wiki/Matrix_multiplication). Not element-wise. That's why I said "multipled by itself (in the matrix sense)". – Ben Voigt Jan 02 '12 at 18:32