can I avoid the nested loops

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

can I avoid the nested loops

Roelof
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof

Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

philippeback
Use Rectangle class and intersect: method?




On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <[hidden email]> wrote:
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof

Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

Roelof
so like this ?

so first the intersect between rectangle1 and rectangle2
store it
and then the intersection between the stored one and rectangle3
and so on
then its time to look how I must define a rectangle when I know the starting point and the length and width

then it time to figure out how I can define a Rectangle with the starting point the length and the width

Roelof



Op 4-12-2018 om 17:27 schreef [hidden email]:
Use Rectangle class and intersect: method?




On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <[hidden email]> wrote:
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof


Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

Ben Coman


On Wed, 5 Dec 2018 at 00:45, Roelof Wobben <[hidden email]> wrote:
so like this ?

so first the intersect between rectangle1 and rectangle2
store it
and then the intersection between the stored one and rectangle3
and so on
then its time to look how I must define a rectangle when I know the starting point and the length and width

then it time to figure out how I can define a Rectangle with the starting point the length and the width

Use Spotter to bring up the System Browser on the Rectangle class.
Then right-click >> Class-refs
to look at how the class is used directly to create new instances.

cheers -ben

 

Roelof



Op 4-12-2018 om 17:27 schreef [hidden email]:
Use Rectangle class and intersect: method?




On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <[hidden email]> wrote:
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof


Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

Roelof
Thanks I found that out already.

Now trying to understand what they mean with this exactly

If the Elves all proceed with their own plans, none of them will have enough fabric. How many square inches of fabric are within two or more claims?


They give some 13000 plans 


Roelof




Op 4-12-2018 om 22:55 schreef Ben Coman:


On Wed, 5 Dec 2018 at 00:45, Roelof Wobben <[hidden email]> wrote:
so like this ?

so first the intersect between rectangle1 and rectangle2
store it
and then the intersection between the stored one and rectangle3
and so on
then its time to look how I must define a rectangle when I know the starting point and the length and width

then it time to figure out how I can define a Rectangle with the starting point the length and the width

Use Spotter to bring up the System Browser on the Rectangle class.
Then right-click >> Class-refs
to look at how the class is used directly to create new instances.

cheers -ben

 

Roelof



Op 4-12-2018 om 17:27 schreef [hidden email]:
Use Rectangle class and intersect: method?




On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <[hidden email]> wrote:
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof



Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

philippeback
A claim is a claim ID + a rectangle.

"If the Elves all proceed with their own plans, none of them will have enough fabric. 
How many square inches of fabric are within two or more claims?" <--- actual question.
units are inches.
So, question translates to:
"What is the total area of rectangle intersections?"
Now you can see it as rectangles or as all measurements are integers, are cells in a matrix (rasterizing the geometry).
That's the approach I took and it worked well enough.

HTH
Phil





On Tue, Dec 4, 2018 at 11:05 PM Roelof Wobben <[hidden email]> wrote:
Thanks I found that out already.

Now trying to understand what they mean with this exactly

If the Elves all proceed with their own plans, none of them will have enough fabric. How many square inches of fabric are within two or more claims?


They give some 13000 plans 


Roelof




Op 4-12-2018 om 22:55 schreef Ben Coman:


On Wed, 5 Dec 2018 at 00:45, Roelof Wobben <[hidden email]> wrote:
so like this ?

so first the intersect between rectangle1 and rectangle2
store it
and then the intersection between the stored one and rectangle3
and so on
then its time to look how I must define a rectangle when I know the starting point and the length and width

then it time to figure out how I can define a Rectangle with the starting point the length and the width

Use Spotter to bring up the System Browser on the Rectangle class.
Then right-click >> Class-refs
to look at how the class is used directly to create new instances.

cheers -ben

 

Roelof



Op 4-12-2018 om 17:27 schreef [hidden email]:
Use Rectangle class and intersect: method?




On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <[hidden email]> wrote:
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof



Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

Richard O'Keefe
In reply to this post by Roelof
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.
Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

Richard O'Keefe
In reply to this post by Roelof
The data set AoC gave me for problem 3 has 1353 claims.
The brute force way is to make your x->(y->count) map
and then walk over it counting the number of counts > 1,
   n := 0.
   map do: [:row |
      row do: [:count |
         count > 1 ifTrue: [n := n+1]]].


On Wed, 5 Dec 2018 at 11:06, Roelof Wobben <[hidden email]> wrote:
Thanks I found that out already.

Now trying to understand what they mean with this exactly

If the Elves all proceed with their own plans, none of them will have enough fabric. How many square inches of fabric are within two or more claims?


They give some 13000 plans 


Roelof




Op 4-12-2018 om 22:55 schreef Ben Coman:


On Wed, 5 Dec 2018 at 00:45, Roelof Wobben <[hidden email]> wrote:
so like this ?

so first the intersect between rectangle1 and rectangle2
store it
and then the intersection between the stored one and rectangle3
and so on
then its time to look how I must define a rectangle when I know the starting point and the length and width

then it time to figure out how I can define a Rectangle with the starting point the length and the width

Use Spotter to bring up the System Browser on the Rectangle class.
Then right-click >> Class-refs
to look at how the class is used directly to create new instances.

cheers -ben

 

Roelof



Op 4-12-2018 om 17:27 schreef [hidden email]:
Use Rectangle class and intersect: method?




On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <[hidden email]> wrote:
Hello,

For adventofCode I had to write some code that calculates the overlap that multiple rectangles have.

Fo far I have it working for 1 rectangle but I do not like the code because of the nested loops.

Can I make this more the pharo way

Code so far :

| item coordinates area overlap regexp line beginX endX beginY endY|
area := OrderedCollection new.
overlap := OrderedCollection new.
regexp := '\#(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)' asRegex.
line := '#1 @ 1,3: 4x4'.
(regexp matches: line)
        ifTrue: [
             beginX := (regexp subexpression: 2) asInteger + 1.
             endX := (regexp subexpression: 5) asInteger + beginX  .
             beginY := (regexp subexpression: 4) asInteger + 1.
             endY := (regexp subexpression: 6) asInteger + beginY.    
             beginX  to: (endX - 1) do: [:a |
                  beginY to: (endY -1)  do: [:b |
                      item := a asString , '*' , b  asString .
                   (area includes: item)
                      ifTrue: [ overlap add: item ]
                      ifFalse: [ area add: item ]]]] .
 ^ area. 

Thanks, 

Roelof



Reply | Threaded
Open this post in threaded view
|

Re: can I avoid the nested loops

Roelof
In reply to this post by Richard O'Keefe
Thanks,

I think that is because im a beginner which has to learn a lot.

May I have a hint how to read the data as as Dictonary. Right now I use a OrderedCollection for that.

I read in the data like this :

lines := 'inputDay3.txt' asFileReference contents lines.

but then lines is a OrderedCollection

Roelof



Op 5-12-2018 om 06:37 schreef Richard O'Keefe:
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.