First, this is a computational geometry problem, as is the second part.
If this were a serious problem or had a huge amount of data, we would
be looking for a good data structure for holding a collection of
rectangles. We might consider quad-trees, k-d-trees, R-trees, ...
With such a data structure, we might hope for O(n.log n) time where
n is the number of claims.
Your approach is O(sum(claim areas)**2).
Since the sum of the claim areas is about half a million square inches,
O(sum(claim areas)) would not be a problem, but squaring that most
definitely is.
The nested loops are not really a problem.
What bothers me a lot is your choice of data structures.
Representing a point by (a asString , '*' , b asString) is, um,
not a good idea. And I don't care if it is C, C++, C#, Java,
Objective C, Eiffel, Ada, Fortran, Javascript, Ruby, Lisp, Smalltalk,
or almost anything but AWK: STRINGS ARE WRONG.
Strings have their uses in input/output. Nietzsche wrote:
‘I teach you the Superman. Man is a thing to be overcome …
What is the ape to man? A jest or a thing of shame. So
shall man be to the Superman – a rope over the abyss.’
STRINGS ARE A THING TO BE OVERCOME. A string where you need
high performance is a jest or a thing of shame.
Alan J. Perlis wrote: 'The string is a stark data structure
and everywhere it is passed there is much duplication of
process. It is a perfect vehicle for hiding information.'
If you need to process information fast, get it *out* of string
form as early as possible, and back into string format for
output as late as possible.
In this case, several programming languages already have a
built-in data structure for points.
In Smalltalk, it is called Point, and (a @ b) will make one.
When you need to represent a point, why not use a Point?
When you need to represent a rectangle, why not use a Rectangle?
Moreover, there is something you do which is *scary*. You do a
LINEAR SEARCH in the OrderedCollection "area". Again, this really
has very little to do with the programming language. You could
use a Vector or an ArrayList in Java and the problem would be the
same. A few linear searches, or a lot of searches in a small
sequence, no worries. A lot of searches in a big sequence, OUCH.
Considering both parts of the problem, you need to be able to
distinguish three different states for any given cell:
- no rectangle covers this cell
- one rectangle covers this cell
- two or more rectangles cover this cell
What you want is some sort of two-dimensional sparse array mapping
x,y coordinates to counts. One good answer is a hash table.
Use map : Dictionary[Integer, Dictionary[Integer, Integer]]
x y count
read the claims as a Dictionary[Integer, Rectangle]
id left@top extent:
(width-1)@(height-1)
create an empty Dictionary, map.
for each rectangle in claims
for each x from rectangle left to rectangle right
row := map at: x ifAbsentPut: [Dictionary new].
for each y from rectangle top to rectangle bottom
increment (row at: y).
let total be the sum over the map of "use #inject:into:"
the number of cells in the row "use #count:"
where the value in the cell is more than one.
