Splitting a given rectangle into n subrectangles

Question

Preliminary remarks

I am learning Haskell.

A question that I answered some days ago gave me the inspiration for this exercise in Haskell, which gave the opportunity for experimenting with the few things that I've learned up to now, and also left me with questions :)

Problem statement

Given a rectangle A of width w and height h find the best rectangle B that fits n times within A, where best means having the smallest perimeter.

My attempt

I've started with the basic idea of generating the set of sub-rectangles of A having an area equal to div (w * h) n, and then picking the one having the smallest perimeter.

Here are the three implementations of this idea that I came up with; they're in chronological order: I got the inspiration for the third after having done the second, which I got after having done the first (OK, there's a version 0, in which I didn't use data Rectangle but just a tuple (x, y)):

Implementation 1

data Rectangle = Rectangle { width :: Integer,
                             height :: Integer
                           } deriving (Show)

subRectangles :: Rectangle -> Integer -> [ Rectangle ]
subRectangles r n = [ Rectangle x y | x <- [1..w ], y <- [1..h], x * y == (w * h) `div` n ]
                  where w = width r
                        h = height r

bestSubRectangle :: [ Rectangle ] -> Rectangle
bestSubRectangle [ r ] = r
bestSubRectangle (r:rs)
  | perimeter r < perimeter bestOfRest = r
  | otherwise = bestOfRest
  where bestOfRest = bestSubRectangle rs

perimeter :: Rectangle -> Integer
perimeter r = (width r) + (height r)

Implementation 2

data Rectangle = Rectangle { width :: Integer,
                             height :: Integer
                           } deriving (Show)

subRectangles :: Rectangle -> Integer -> [ Rectangle ]
subRectangles r n = [ Rectangle x y | x <- [1..w ], y <- [1..h], x * y == (w * h) `div` n ]
                  where w = width r
                        h = height r

bestSubRectangle :: [ Rectangle ] -> Rectangle
bestSubRectangle xs = foldr smaller (last xs) xs

smaller :: Rectangle -> Rectangle -> Rectangle
smaller r1 r2 
  | perimeter r1 < perimeter r2 = r1
  | otherwise = r2

perimeter :: Rectangle -> Integer
perimeter r = (width r) + (height r)

Implementation 3

import Data.List

data Rectangle = Rectangle { width :: Integer,
                             height :: Integer
                           } deriving (Show, Eq)

instance Ord Rectangle where
  (Rectangle w1 h1) `compare` (Rectangle w2 h2) = (w1 + h1) `compare` (w2 + h2)

subRectangles :: Rectangle -> Integer -> [ Rectangle ]
subRectangles r n = [ Rectangle x y | x <- [1..w ], y <- [1..h], x * y == (w * h) `div` n ]
                  where w = width r
                        h = height r

bestSubRectangle :: [ Rectangle ] -> Rectangle
bestSubRectangle = head . sort

Questions

1. Which approach is more idiomatic?

2. Which approach is better in terms of performance? bestSubRectangle in Implementation 3 depends on sort, which is at best O(n lg n), while in Implementation 1, 2 bestSubRectangle requires only scanning the array returned by subRectangles, thus making it O(n). However I'm not sure if/how Haskell laziness works on bestSubRectangle = head . sort: will sort produce only the first element of the sorted array, because of head requiring only the first element (head (x:_) = x)?

3. In implementation 3, when making Rectangle an instance of Ord should I also define the other methods of the Ord class? Is this the right way to make Rectangle an instance of Ord?

Any further suggestion/recommendation to improve is highly welcome.

Answer 1

To answer your questions about Haskell (and not about the algorithm you've choosen):

1. I'd say your second implementation is most idiomatic.
2. You are right that the problem needs only a linear scan, so that sort is likely to be more expensive than needed. You are also asking the right question when asking if, due to laziness, head . sort will compute only the first element of the result of the sort. It will, but depending on how sort is implemented, that may very well rely on sorting the whole list before it can return the first element. You should assume that it does.
3. You can tell from the documentation for Ord that compare is sufficient. The key phrase is Minimal complete definition: either compare or <=. Many type classes have similar use patterns. You should feel free to write a minimal implementation where they do.

Some other observations about your code (again, not the algorithm):

• Function calls bind tighter than operators, as in most languages - just in Haskell there are no parenthesis around the arguments. Hence you would write perimeter r = width r + height r
• If you are folding over a list that must have at least one element, you can use foldr1 as in bestSubRectangle xs = foldr1 smaller xs
• Your instance of Ord for Rectangle doesn't agree with the derived instance of Eq. That is, there are values which will compare as EQ but would return False for ==. In this case, I wouldn't try to bend Rectangle's general purpose instance of Ord for purposes of perimeter comparison, and instead go with the smaller predicate you wrote in the second implementation.

Answer 2

Seems like you are calculating too much, inductively going through posibilities of n (number of rectangles we wish to fill up our given rectangle) we should get:

• n = 1 => always returns the given rectangle
• n = 2 => always returns the 2 rectangles given by bisecting the given rectangle on the longest side, i.e. gives the 2 most square rectangles
• n = 3 => same as 2 using 3, divide equally along longest side.
• n = 4 More complicated, essentially the question comes up is it better to put the same rectangle 4 times in a row OR is is better to bisect both length and width into a 2x2 group of rectangle. For larger numbers of n it is also a question of these configuration of factors > 1

--Essentially this is a question of factoring n, dividing the length and width by the each of the factors THEN choosing the configuration where the divided length & width (i.e. the length and width of the resulting filler rectangles) are MOST SIMILAR, (most square-like). Also note it is not necessary to try all factors against all sides. The most square rectangle will be taking the larger factor against the longer side.

• n = number of filler rectangles
• l = longest of width or height of container rectangle
• s = shortest of width or height container rectangle
• h1 = height of candidate rectangle 1
• w1 = width of candidate rectangle 1
• d = difference of candidate dimensions
• t = smallest difference in candidate height and width (initialize t to l)
• b = best fit

Therefore the steps become:

    1: Factor n
    2: for each factor pair of n:
       (l/largest factor) - (s/smaller factor) = d
       if d < t:
          t = d
          store current best candidate rectangle 
    3: Return best fit remaining after all factors have been tried