2
$\begingroup$

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).

  • 0
    See my answer at stackoverflow.com: http://stackoverflow.com/questions/7788462/project-euler-215-in-java/7788862#77888622011-10-21

1 Answers 1

2

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.

  • 0
    Great, thanks for the explanation!2011-10-21