Coding Dojo - Four Boxes by Ruby (Improved)

Four Boxes (I translated this quest from http://xper.org/wiki/seminar/FourBoxes)

Quest

There are four rectangles in plan and all their base of four rectangles are in parallel with the horizontal axis. You should make a program that calculate total area that the four boxes occupied.

There can be separated from others or overlaid with others. One box can cover others and some sides or apexes of a rectangle can overlap other's.

Input

Input has 4 lines. Each line represents one rectangle and consists of 4 positive integer. First and second integer mean x, y coordinate of leftmost lowest apex. Third and fourth integer mean x, y coordinate of rightmost highest apex. ( 1<= x, y <= 1000 )

ex)
  1 2 4 4
  2 3 5 7
  3 1 6 5
  7 3 8 6

output

The program should print total area that the four boxes occupied.

ex)
  26

My program:


addtion : After today coding dojo, I could take another idea from my pair who is not programmer(he is so brave man :-) during pair programming with TDD. Total lines of test_shape_group.rb is reduced from 90 to 65. And shape_group.rb is also compacted. :-)

test_shape_group.rb

 1 require 'test/unit'
 2 require 'shape_group'
 4
 5 class TestShapeGroup < Test::Unit::TestCase
 6   def setup
 7     @group = ShapeGroup.new
 8   end
 9  
10   def test_leftmost_lowest_point
11     @group.add(make_rectangle(5,1,7,10))
12     assert_equal([5,1], @group.leftmost_lowest_point)
13    
14     @group.add(make_rectangle(2,3,6,11))
15     assert_equal([2,1], @group.leftmost_lowest_point)
16    
17     @group.add(make_rectangle(4,1,5,99))
18     assert_equal([2,1], @group.leftmost_lowest_point)
19   end
20  
21   def test_rightmost_highest_point
22     @group.add(make_rectangle(5,1,7,10))
23     assert_equal([7,10], @group.rightmost_highest_point)
24    
25     @group.add(make_rectangle(2,3,6,11))
26     assert_equal([7,11], @group.rightmost_highest_point)
27    
28     @group.add(make_rectangle(4,1,5,99))
29     assert_equal([7,99], @group.rightmost_highest_point)
30   end
31  
32   def test_include?
33     small_rec = make_rectangle(1,2,3,4)
34     assert !@group.include?(small_rec)
35    
36     @group.add(make_rectangle(1,2,3,4))
37     assert @group.include?(small_rec)
38    
39     large_rec = make_rectangle(4,3,7,7)
40     assert !@group.include?(large_rec)
41    
42     @group.add(make_rectangle(2,3,8,8))
43     assert @group.include?(large_rec)
44   end
45
46   def test_size
47     assert_equal(0,@group.size)
48    
49     @group.add(make_rectangle(1,2,4,4))
50     @group.add(make_rectangle(2,3,5,7))
51     @group.add(make_rectangle(3,1,6,5))
52     @group.add(make_rectangle(7,3,8,6))
53     assert_equal(26, @group.size)
54    
55     other_group = ShapeGroup.new
56     other_group.add(make_rectangle(5,1,7,10))
57     other_group.add(make_rectangle(2,3,6,11))
58     other_group.add(make_rectangle(4,5,10,8))
59     other_group.add(make_rectangle(8,3,9,14))
60     assert_equal(60, other_group.size)
61   end
62  
63   def make_rectangle(ll_x,ll_y,ru_x,ru_y)
64     Rectangle.new(ll_x,ll_y,ru_x,ru_y)
65   end
66 end

I attached other files, so you can download and check it. four_boxes.zip

Addition: Below code is coded by jiah11 in coding dojo(http://club.filltong.net/codingdojo/6546 - Korean site). Her code is so much simpler than mine and her algorithm is so fresh and nice. :-)

 1 position = [[1, 2, 4, 4],
 2         [2, 3, 5, 7],
 3         [3, 1, 6, 5],
 4         [7, 3, 8, 6]]
 5 
 6 space = Array.new(1000*1000, 0)
 7 area = 0
 8 
 9 def getPos(x, y)
10   return x+(y*1000)
11 end
12 
13 position.each do  | x1, y1, x2, y2 |
14   (y1..(y2-1)).each do | y |
15     (getPos(x1, y)..getPos((x2-1), y)).each do | pos |
16       space[pos] = 1
17     end
18   end
19 end
20 
21 space.each do | tile |
22   if tile == 1
23     area = area + 1
24   end
25 end
26 
27 puts area

If she use my leftmost_lowest_point and rightmost_highest_point routine, her program's performance will be a little bit improved.

And.. Which points of my code are better than her code? I think my code can accept change easy. Suppose, quest is changed that calculate total area of all shape (not only rectangle) like below:









In this case - new shapes consist of rectangles -, I just add new class that represent those shape and implement all method in class Rectangle. (of course I have to change four_boxes.rb :-) That's it. And if I introduce factory calss for shape, the code will be more flexible. This idea was came from Dollar example of TDDBE.

And.... My program use smaller memory than her code. :-)

However, most serious problem is our main quest didn't require this kind of job. :-<