BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

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.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re: Challenge: 2D random layout of variable-sized rectangular units.
by zentara (Cardinal) on Sep 03, 2006 at 17:56 UTC
    UPDATE Sep04,2006 Fixed an error in the second point of the patio rectangle, where I didn't account for the y offset. The patio rectangle will then be bigger.

    Well, I figure this is more of an "artistic" endeavor, than 1 of pure mathematical fitting. So of course, I made a Tk visualizer, which allows you do drag pavers from stacks of 99, and rotate them 90 degrees with a right click. Postscript saving included. In order to get a convenient scaling of cm-to-pixel, I've scaled it to cm.

    Read more... (8 kB)
    I'm not really a human, but I play one on earth. Cogito ergo sum a bum
[reply]
[d/l]
      heh... nice job++ :)

      It really needs a "snap-to-edge" feature though. Especially for somebody as clumsy with a mouse as me ;)

[reply]
        Thanks, I made it as simple as I could. I'm thinking about an improved version, with "snap-to" edges, and 45 degree rotations, so you can get more artistic with the layout.
        I'm not really a human, but I play one on earth. Cogito ergo sum a bum
[reply]
Re: Challenge: 2D random layout of variable-sized rectangular units.
by punch_card_don (Curate) on Sep 03, 2006 at 14:18 UTC
    Not a very Perlish answer, but perhaps helpful to a fellow Perl user in real life:

    If this an actual real-life project in your backyard, I would just make a point of buying from a store that takes returns. Choose 5 or 6 sizes and buy approximately equal surface areas of each size to equal patio size + ~20%. Lay them out randomly following the rules. You'll spend less time, and get more exercise, working it out on your hands and knees in real time than you'll spend writing a progrma that produces a set of coordinates that almost noone can actually follow. Then, use the time you've saved to enjoy your new patio with your kids.

    Like I said, not Perlish, but Perl-coders' real lives are more important than Perl itself. Call me crazy.




    Forget that fear of gravity,
    Get a little savagery in your life.
[reply]

      I already laid my patio this summer using 300x300 slate pavers. The problem came up whilst researching what to use, and I thought it interesting enough to consider it a perlish (going on) winter project.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
        Ah - good man.

        Of course, once it's developed, you could always sell this program to the paver company for them to use as a marketing tool....




        Forget that fear of gravity,
        Get a little savagery in your life.
[reply]
Re: Challenge: 2D random layout of variable-sized rectangular units.
by bart (Canon) on Sep 03, 2006 at 18:30 UTC
    In your proposed format for the output, you forgot one thing: rectangular paves can be oriented either horizontally or vertically — thus, rotated over 90°.

    Unless you prefer all rectangles to be oriented in the same direction?

[reply]

      The orientation (where it matters Ie. for non-square units), can be derived from the information I listed. If you substract the next unit's X-offset from this unit's X-offset, you have the dimension in the X orientation. Combined with the type letter, this is sufficient.

      But you are right. An indication of orientation would be a useful addition.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
Re: Challenge: 2D random layout of variable-sized rectangular units.
by pengvado (Acolyte) on Sep 05, 2006 at 20:54 UTC
    Interesting problem. Here's my attempt at a random layout generator, using a simple exponential-time backtracking algorithm.

    It enforces "no 4-corner joints", but does not enforce "no long straight runs".

    The areas covered by each tile type are not necessarily equal: The randomization code looks like they might be equal by number instead of by area, but small tiles fit in more places and so have a higher representation in the final layout.

    Read more... (5 kB)
    And a sample output: 
    +----+-+----+--+-+----+-+--+---+---+---+--+-+---+--+-+---+--+ 
|    | |    |  | |    | |  |   |   |   |  | |   |  | |   |  | 
|    | |    +-++-+    +-+  |   |   +---+-++-+-+-+  +-+   |  |
|    +-+    | |  |    | +--+   |   |     |    | |  | |   +--+
+-+--+ +---++++--+    | |  +---+   |     |    | +-++-+   |  |
| |  | |   | |   +---++-+  |   |   |     |    +-+ |  |   |  | 
+-+--+++-+-+ |   |   |  +--+   +-+-+-+---++---+ +-+-++---++-+ 
|     |  | | +--++--++--+  |   | |   |    |   | |   |     | |
|     |  | +-+  |   |   |  |   +-+   |    |   +-+   |     +-+ 
|     |  +-+ |  +-+-+   |  +-+-+ |   |    |   | |   |     | |
+---+-+--+ | |  | | |   +--+ | +-+   +---++--++-+   +--+-++-+ 
|   |    +-+ +--+++-++--+  | | | |   |   |   |  |   |  | |  | 
|   |    | +-+   |   |  +--+-+++-++--+   |   |  +---+  | +--+
+---+    | | |   |   |  |     |   |  |   |   +--+   +--+-+  | 
|   +-+--+++-+   |   |  |     |   +--+   |   |  +-+-+    +--+ 
|   | |   |  |   |   +--+     |   |  +---+   |  | | |    |  |
+---+++---++-+---+   |  +---+-+   |  |   +--+++-+ +-+    +--+ 
|    |     |     +---+  |   | +-+-+  |   |  | | | | |    |  | 
|    |     |     |   +--++-++-+ | +-++-+-++-+ | +-+ +---+++-+
|    |     |     |   |   | |  | | | |  |  | | | | | |   | | |  
+----+-----+-----+---+---+-+--+-+-+-+--+--+-+-+-+-+-+---+-+-+

    [download]
[reply]
[d/l]
[select]

      Excellent++. The first attempt to tackle the challenge!

      I'm resisting looking at how your code works whilst I complete my attempt. More in a week or so once I've finished my attempt.

      I like your output format, though it does present problems for supplying on to other programs, but then it is a pretty good visualisation as is.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
Re: Challenge: 2D random layout of variable-sized rectangular units.
by traveler (Parson) on Sep 03, 2006 at 18:04 UTC
    You should include any grout line and try to make it uniform. You may not have used grout in your previous project, but for a "stone effect", you may want a fixed (1cm?) grout line around all pavers, but not necessarily along the edges.

    (No, I am not trying to add a mathematical complication, just a nicer appearance.)

[reply]

      For the purposes of this exercise, the "grout lines" can be ignored as the nominal sizes of the pavers are actually slightly larger on each dimension to accomodate the pointing. Ie. Just as bricks are nominally sold as being 225 x 112.5 x 75 but actually measure 215 x 102.5 x 65 to accomodate 10mm of mortar.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
    A reply falls below the community's threshold of quality. You may see it by logging in.
Re: Challenge: 2D random layout of variable-sized rectangular units.
by GrandFather (Saint) on Sep 05, 2006 at 23:01 UTC

    The following code uses a backtracking technique that gets very slow with increasing size. It precludes long edges, but doesn't check for four tile corners. It attempts to achieve an even distribution of tile areas.

    A very stripped down version of Zentra's Tk code is used to display the result and the tile list and placement is also printed.

    Update: various bugs fixed and a constant added to control maximum allowed edge length as a fraction of width or height.

    Update: the code doesn't scale as poorly as I expected with larger areas to be paved. I guess because it doesn't actually have to do much back tracking until fitting the last tiles so the last couple of "rows" may get relaid multiple times, but hardly ever more than that. The kMaxFrac constant I added can be set to much smaller values than the 0.5 criteria provided by BrowserUK for a maximum edge of half the width or height. In fact it could probably be set in terms of the GCD and be independent of the patio size.

    Read more... The code (10 kB)

    Sample output:

    Rounded dimensions are 1500 mm x 1200 mm
X,    Y,    Type
0,    0,    1 (300 x 300)
300,    0,    3 (450 x 450)
750,    0,    2 (300 x 450)
1050,    0,    2 (450 x 300)
0,    300,    1 (300 x 300)
1050,    300,    3 (450 x 450)
300,    450,    2 (300 x 450)
600,    450,    2 (450 x 300)
0,    600,    1 (300 x 300)
600,    750,    2 (300 x 450)
900,    750,    4 (600 x 450)
0,    900,    6 (600 x 300)

    [download]
    DWIM is Perl's answer to Gödel
[reply]
[d/l]
[select]
Re: Challenge: 2D random layout of variable-sized rectangular units.
by Anonymous Monk on Sep 03, 2006 at 09:19 UTC
    What do you mean by 4-corner joints?
[reply]

      I think that these are places where two straight lines intersect:

               |
         |
---------+----------
         |
         |

      [download]

      These are aesthetically inacceptable as too much structure becomes apparent. So only T-intersections are allowed.

               |
         |
---+-----+----------
   |
   |

      [download]
[reply]
[d/l]
[select]
Re: Challenge: 2D random layout of variable-sized rectangular units.
by aquarium (Curate) on Sep 03, 2006 at 12:05 UTC
    if you were describing a real world scenario then....areas of particular pattern/size tiles are already known, as there's design involved. that precludes having to write a computed solution. although go ahead if you find this interesting.
    the hardest line to type correctly is: stty erase ^H
[reply]
A reply falls below the community's threshold of quality. You may see it by logging in.

Back to Seekers of Perl Wisdom