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.
