Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wrote a program to solve Project Euler Problem #215 (see below for description) using memoization, and when I got access to the PE forums, I saw everyone else wrote programs that also used dynamic programming/memoization techniques.

However, from this stackoverflow answer, Dietrich Epp solved it in Haskell using a sparse matrix of NxN dimensions (an adjacency matrix) and then multiplied the matrix by a 1xN vector to arrive at the solution.

Quote from the poster Dietrich Epp:

You compute each possible way to tile a row. Let's say there are N ways to tile a row. Make an NxN matrix. Element i,j is 1 if row i can appear next to row j, 0 otherwise. Start with a vector containing N 1s. Multiply the matrix by the vector a number of times equal to the height of the wall minus 1, then sum the resulting vector.

How come the matrix x vector solution is viable for this problem, as in what property is it exploiting to solve the question?

Thanks in advance!

Problem Description

Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal and 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".

For example, the following 9x3 wall is not acceptable due to the running crack shown in red:

PE 215 Crack-free wall

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

Calculate W(32,10).

share|improve this question
    
See my answer at stackoverflow.com: stackoverflow.com/questions/7788462/project-euler-215-in-java/… –  Thomas Andrews Oct 21 '11 at 3:14
add comment

1 Answer

up vote 2 down vote accepted

This is a nice way of keeping track of the linked recurrence relations. The vector initially starts out with all $1$'s indicating there is one way to make a height $1$ wall with each type of layer on the bottom. After one multiplication by the matrix position $j$ in the vector is the number of ways to have a wall of height $2$ with the bottom layer of type $j$. Each successive multiply adds one layer because position $j$ will have the sum of all the other types of layer that can come above it. So after $n-1$ multiplies you have walls of height $n$. Then at the end you sum over all the types of bottom layer.

share|improve this answer
    
Great, thanks for the explanation! –  birryree Oct 21 '11 at 0:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.