Problem description:

Your going to lay a patio using brand of precast concrete "stone effect" pavers that come in a range of sizes:

a)300x300, b)450x300, c)450x450, d)600x450, e)600x600, f)600x300, g)750x600, h)750x750, i)900x600.

To achieve the most natural effect, the advice is to lay a combination of sizes of paver in 'random layout'. The industry rules of thumb for achieving a good effect are:

1. The more sizes used the better.
2. There should be roughly equal numbers areas* of each size used.
3. There should be no 4-corner joints.
4. Contiguous straight runs of joint should be minimised, and under no circumstances should any single straight run stretch for more than half the width of the area in the direction it runs.

One final, if obvious, golden rule is that you should work out the pattern of choice before ordering the pavers.

The challenge

Write a program that takes the width x length of the patio in question, ( and optionally the list of sizes of paver, though these can be hard coded as above), and generates random patterns that comply with the rules of thumb above.

The program should produce one random layout per run.

The output should be in some form that can be used as input to another program to display the layout graphically. I'm not going to specify the format, but it might be something like:

   X,    Y  TYPE
   0,    0,  c
 450,    0,  g
1050,    0,  a
1350,    0,  i
...
[download]

Many other formats are possible, including a Data::Dumper dump of the internal data structure used.

The size of the patio as input can be 'rounded up' in either or both dimensions to the next of the greatest common divisor (GCD) of the list of sizes. (This puts all cuts to be made in the actual patio at one of the four edges). For example. The GCD of the 9 sizes above is 150mm. This forms a minimum grid for the layout. If the patio size entered was 8.65 x 4.1, then this would be round up to

0.15 * ( 1 + int( 8.65 / 0.15 ) ) x 0.15 * ( 1 + int( 4.1 / 0.15 ) )
8.7 x 4.2
[download]

Other rules

None. I have ideas about how I will approach the problem, but I don't want to influence the creativity.

There is no rush. I will not be looking at other peoples solutions till I've had a go myself, and not until at least next Sunday. If you have questions, please mark the post with (Qs) in the title so I'll know to look and answer.

There is no 'best layout'; or 'right answer'; nor prize. It's just a real world problem that I encountered recently that I thought deserved a programic solution, but found quite hard to tackle when I sat down to try it. I hope that others will find it interesting also.

I will attempt to produce the graphic display program (probably using GD). I will also attempt to make it verify layouts against the rules above.