can I avoid the nested loops

| 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

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

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

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

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.