can I avoid the nested loops
Use Rectangle class and intersect: method? On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <r.wobben@home.nl> 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
On Wed, 5 Dec 2018 at 00:45, Roelof Wobben <r.wobben@home.nl> 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 phil@highoctane.be:
Use Rectangle class and intersect: method?
On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <r.wobben@home.nl> 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
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 <r.wobben@home.nl> 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 <r.wobben@home.nl> 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 phil@highoctane.be:
Use Rectangle class and intersect: method?
On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <r.wobben@home.nl> 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
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 <r.wobben@home.nl> 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 <r.wobben@home.nl> 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 phil@highoctane.be:
Use Rectangle class and intersect: method?
On Tue, Dec 4, 2018 at 5:07 PM Roelof Wobben <r.wobben@home.nl> 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.
participants (4)
-
Ben Coman -
phil＠highoctane.be -
Richard O'Keefe -
Roelof Wobben