. . .
The Elves managed to locate the chimney-squeeze prototype fabric for Santa's suit (thanks to someone who helpfully wrote its box IDs on the wall of the warehouse in the middle of the night). Unfortunately, anomalies are still affecting them - nobody can even agree on how to cutthe fabric.
The whole piece of fabric they're working on is a very large square - at least 1000 inches on each side.
Each Elf has made a claim about which area of fabric would be ideal for Santa's suit. All claims have an ID and consist of a single rectangle with edges parallel to the edges of the fabric. Each claim's rectangle is defined as follows:
A claim like #123 @ 3,2: 5x4 means that claim ID 123 specifies a rectangle 3 inches from the left edge, 2 inches from the top edge, 5inches wide, and 4 inches tall. Visually, it claims the square inches of fabric represented by # (and ignores the square inches of fabric represented by .) in the diagram below:
#123 @ 3,2: 5x4
The problem is that many of the claims overlap, causing two or more claims to cover part of the same areas. For example, consider the following claims:
#1 @ 1,3: 4x4#2 @ 3,1: 4x4#3 @ 5,5: 2x2
Visually, these claim the following areas:
The four square inches marked with X are claimed by both 1 and 2. (Claim 3, while adjacent to the others, does not overlap either of them.)
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?
Tricky business today!
Now, what is the best way to represent a 2D-plane and a bunch of rectangles? ...
Hold tight everybody and good luck!
In these, I used repeating variable "namespaces" again. Each square of fabric is an x,y coordinate. I looped through each line of input and created a variable for all the x,y coordinates that a line encompassed. I named the variable based on a representation of the coordinate. 1xxxx01yyyy So 421,9 became 10421010009 (which can be converted back to an x,y format).
For #1, before creating a variable, I checked to see if it already had a value of 1, and if so, added it to a cumulative list. The number of values in that list was the answer.
For #2, I used nearly the same script, but first I created a list of all the claim numbers. Then when I checked a coordinate, if it had a single value, I removed that value and the current one from the list. If it had more than one value, I removed the current one from the list (no need to remove existing ones again). That would whittle the list down to a single claim #.
Each script takes 60-80 seconds.
I think I did roughly the same thing as David Jondreau. I notated the coordinate vars like $~x[y]. I would have loved to use nested JSON arrays if Filemaker's JSON processing weren't so dang slow.
P1: I set each square inch coordinate variable with one of two values: 0 = single claim, 1 = overlapping claims. For a new overlap (i.e. I set the variable from 0 to 1) I'd iterate the overlap counter. If I found an overlap that was already overlapping (i.e. it was already set to 1) then I would not iterate because we already counted that coordinate. The overlap counter is the answer.
P2: Set each square inch coordinate variable with the id of the first claim to cover it. If no overlaps occur then I add the ID to a JSON object with the ids as keys. If an overlap does occur, then I delete the ids for the current claim and the claim that occupies that square inch coordinate. At the end the JSON will contain only one claim ID.
I think there is good optimization potential for this problem. First of all my times were no good at 4 and 6 minutes (on a 2012 MBP so adjust for that). While the algorithm is fine, I know I could speed up the script in some ways by reducing redundant variable writing etc... But the algorithm is still brute force and scans every square inch of every claim. I'd be really stoked to see if someone writes a solution that stored values in range notation (a la how snapshot links list ids like "1-7"). Another optimization could be to store a boolean value for each row and column to indicate whether any values were added in that line. Then when drawing a new claim, we'd only check for overlaps in rows/columns that contain values. Anyway, all this is to say that I'm not incredibly thrilled with my implementation but "When in doubt, use brute force." - KT
I solved it in a different language with a memory database, think a simple filemaker table with the fabrik x;y space should work nice, need to test it
I've cracked both parts using data in a table and a create-relation from a global field, which increments a counter field, ... :-)
... but I'm currently just enjoying another technique (for part 1) of simply storing the counter in a large 1000x1000 string (or rather x1001, coz. there is a ¶ at the end of each row), in which each character is initialized to the character "0" and is incremented to "1", "2", …, "9", ":", ";", etc. when claims overlap.
I'm then keeping the result in a $$-variable at the end and displaying this in a merge variable <<$$fabric>> on a layout with a very small font + line space (2px, I think). You then get a real good visualisation of the situation:
..aha ... and I was thinking that the method hadn't worked, because it returned a result which was exactly 1000 wrong ... but writing this has made me realise that I mustn't count the ¶ characters.
That is epic!
So my solution(s) ... slow! ... but you can also learn from that!
I have half the solution done. Didn't get much time to even look at it today. Just need to actually calculate the actual space that overlaps. Not sure I will be able to finish it up tonight. It may have to wait until tomorrow. What I have so far is almost instant.
Did you know that a relationship from a global field in a table with NO records …
Now ... is that useful, expected, logical, or an FM-BUG? or the beginning of a change request?
Basically used same principle as David Jondreau
Represented x,y as x * 10000 + y
(First tried using Evaluate to create an indexed variable for each row but above method was about twice as fast)
Generated all the rectangles in the space increasing the counter for each cell each time it is a rectangle
Keeping track of the max and min values of x and y so we know the size of the space
Scanned the space counting all the cells covered by more than one rectangle
Same as P1, generated all the rectangles in the space
Using the same loops, scan the space occupied by each rectangle to find the one that has all its cell counters set to one.
Depending on how dense the rectangle overlap is it might have been more efficient to just scan the whole space again looking for cells with a count of one.
Great visualisation of the space by MrWatson.
Retrieving data ...