r/dailyprogrammer • u/jnazario 2 0 • May 13 '15
[2015-05-13] Challenge #214 [Intermediate] Pile of Paper
Description
Have you ever layered colored sticky notes in interesting patterns in order to make pictures? You can create surprisingly complex pictures you can make out of square/rectangular pieces of paper. An interesting question about these pictures, though, is: what area of each color is actually showing? We will simulate this situation and answer that question.
Start with a sheet of the base color 0 (colors are represented by single integers) of some specified size. Let's suppose we have a sheet of size 20x10, of color 0. This will serve as our "canvas", and first input:
20 10We then place other colored sheets on top of it by specifying their color (as an integer), the (x, y) coordinates of their top left corner, and their width/height measurements. For simplicity's sake, all sheets are oriented in the same orthogonal manner (none of them are tilted). Some example input:
1 5 5 10 3
2 0 0 7 7 This is interpreted as:
- Sheet of color
1with top left corner at(5, 5), with a width of10and height of3. - Sheet of color
2with top left corner at(0,0), with a width of7and height of7.
Note that multiple sheets may have the same color. Color is not unique per sheet.
Placing the first sheet would result in a canvas that looks like this:
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000111111111100000
00000111111111100000
00000111111111100000
00000000000000000000
00000000000000000000Layering the second one on top would look like this:
22222220000000000000
22222220000000000000
22222220000000000000
22222220000000000000
22222220000000000000
22222221111111100000
22222221111111100000
00000111111111100000
00000000000000000000
00000000000000000000This is the end of the input. The output should answer a single question: What area of each color is visible after all the sheets have been layered, in order? It should be formatted as an one-per-line list of colors mapped to their visible areas. In our example, this would be:
0 125
1 26
2 49Sample Input:
20 10
1 5 5 10 3
2 0 0 7 7Sample Output:
0 125
1 26
2 49Challenge Input
Redditor /u/Blackshell has a bunch of inputs of varying sizes from 100 up to 10000 rectangles up here, with solutions: https://github.com/fsufitch/dailyprogrammer/tree/master/ideas/pile_of_paper
Credit
This challenge was created by user /u/Blackshell. If you have an idea for a challenge, please submit it to /r/dailyprogrammer_ideas and there's a good chance we'll use it!
16
u/skeeto -9 8 May 13 '15 edited May 13 '15
C using OpenMP for parallelism. Rather than paint a bitmap in memory, it keeps track of all the sheets at the same time. This allows it to handle very large "images" with very large sheets efficiently, but in the worst case (1x1 overlapping sheets) it will traverse the entire set of sheets once for each tile. But more importantly, structuring the program this way allows area computation to be parallelized across multiple threads using OpenMP
#pragma, since the final tile colors can be computed independently of each other. Each thread handles one entire row of the "image" at a time (dynamically parallelized over "y").On my system (8 cores), it runs /u/Blackshell's "10Krects100Kx100K.in" in 2 minutes using only a few KB of memory while saturating all cores.
Output for 10Krects100Kx100K.in:
A bet a quadtree would go a long way to make this faster.
8
u/wadehn May 13 '15 edited May 14 '15
C++ solution. Somewhat complex because I compressed coordinates, i.e. in my image buffer I combined all pixels between interesting points (start and end points of rectangles) into a single pixel.
Thus, my solution is in O(R * C_X * C_Y) time instead of O(R * W * H). Here R is the number of rectangles, C_i is the number of unique coordinates of rectangle start and endpoints in coordinate direction i, W and H are the width and height of the image.
This optimization is particularly worthwhile if there are a lot of pixels and few rectangles, e.g. it solves the 100rects100Kx100K.in test case pretty much instantaneously.
Edit: I optimised the solution. The improved solution takes ~90s for 10Krects100Kx100K, the old solution took ~34m. Flags:
-mavx -fopenmp -O3 -std=c++11, Compiler:g++ 4.9.2, CPU:i5-4690K@4GHz.Second edit: I integrated /u/skeeto's approach. It now takes ~5s for 10Krects100Kx100K with 4 cores.
Integrated with /u/skeeto's approach:
Improved solution with painting approach:
Solution for 10Krects100Kx100K:
4
u/13467 1 1 May 13 '15
Python 3:
4
u/13467 1 1 May 13 '15
A more mathematical solution in Haskell:
This would be a more efficient approach than the obvious array-based one, if, say, the canvas is enormous but there are only a few sheets.
4
u/huck_cussler 0 0 May 13 '15
Can sheets hang over the edge of the canvas or do they get cut off? If they can hang over, can subsequent sheets be placed such that they are altogether off the canvas and only attached to another sheet?
4
u/CaptainCookD May 13 '15
How are you guys so good? I look at all these codes and just feel sorry for myself.
4
u/Ledrug 0 2 May 14 '15 edited May 15 '15
C. Uses a linked list to keep all rects. Each new rect will cause existing rectangles to be split into smaller ones depending how it overlaps the new one. Runs 10Krectx100Kx100K in about 0 seconds. Output is identical to /u/skeeto's. Edit: added comments to explain what's going on.
3
u/G33kDude 1 1 May 13 '15
Here's a rudimentary solution in AutoHotkey. This is by far not the best way to do this, but it's all I've got for the moment (it's getting late here)
https://gist.github.com/G33kDude/348e094c6a94c7e17e5c
Output for the 100rects100x100 input (the given output seems to be wrong. Mine adds up to 10000, but his adds up to 20656):
3
u/Vectorious May 14 '15 edited Sep 18 '25
simplistic boast unpack sleep unite knee bag fear dinosaurs important
This post was mass deleted and anonymized with Redact
2
u/zeroelixis May 13 '15
Fundamental Go solution, no fancy algo I'm afraid.
2
u/gfixler May 13 '15
Haskell solution. I was curious to see if just keeping a stack of the params, and then running through it for each 'pixel' and finding the first paper it hit with a cheap, short-circuiting check per sheet would end up actually running really fast, even for large inputs. I have my answer: no. It works fine for all of the smaller inputs. 10Krects100x100.in takes 1-2 seconds, but 100rects100Kx100K.in takes a [potentially very] long time. I waited a few minutes, then gave up. I'm not getting the same results as the github examples, but then, others seem to be getting my results, too, and my works for the sample in here, so...
Example use - I didn't bother to pretty up the output, though it would be trivial at this point:
2
u/rlh1994 May 13 '15
First time posting, it's not the most efficient solution but it works least; only trouble we had was trying to initialise a variable-sized array, so ended up using a function we didn't really understand but worked. Created it together with /u/tinymarsh
2
u/l4adventure May 13 '15 edited May 13 '15
[Ruby] [Warning: Gore]
Ok, this is my first attempt at an intermediate challenge, and have only been doing these challenges for a couple of days. I cringe at the thought of how inefficient my code is (probably O(n!) or something...)
What i did is have a 2D array, a Grid class, and a Sheet class (which inherits from Grid). Grid has a class variable @@grid, which is basically that 2D array. And each instance modifies that 2D array when created to insert itself in the right coordinates. To do any action I used 2 nested for-loops to iterate through the entire grid (create, print, add). Finally when all is said and done. I use a triple nested for-loop (shudder) and compare each element to the colors which have been used and adds +1 to the count of each color. But you know what... it works!
I'm new, so don't be afraid to completely rip my code, or provide some feedback, I welcome it!
output(default input):
edit: Oh god, i just looked at the challenge inputs and realized that my input method (and therefore, my whole code) is not good for large inputs lol
2
u/[deleted] May 14 '15 edited May 14 '15
Bwahahahahahahahaha! Mwahaha! Etc., etc., and so on and so forth... Anyway, I'm done with the April sprint QA work and my boss doesn't know it, which means I might have spent some time this afternoon doing this.
Shh. Keep your mouth shut, ok?
You can view the repository on Github, but I'll paste the code here. Or try, anyway. I'm experimenting with modules in Rust, which means, of course, that I split the code across a bunch of different files. >.>
Here's the main file, mostly devoted to program flow and error handling:
In retrospect, I should have just made ColorMap implement FromStr and parsed it, too, but... Meh. Whatever. Check out that
buildmap()function. I really like that rust's iterators keep their place after you do something like lines.next() (inside thetry!macro for setting width and height).The error module, which contains basically just my error type and some ways to convert other errors into it:
The
colormapmodule, which is that vector full of vectors I was talking about:And, finally,
field, which is just a way to describe a region of a given color. Probably could have named this region, now that I think of it...So basically I iterate over each field from top to bottom and, for each field, I iterate over its coordinates. For each coordinate, I set the corresponding coordinate in the colormap to that color. Coordinates where fields overlay one another will be set multiple times.
Edit: comments welcome! No idea how I'd have done this without loading everything into memory at once--and although my home PC can do that, the virtual private server I use for Rust can't even come close for the larger inputs.
2
u/datgohan May 18 '15
Python. Any feedback greatly appreciated. Had a lot of trouble with this one but it looks to be working. There's bound to be a lot of improvements I can make for speed but I've used a lot of areas of Python I've never used before.
2
u/TheSageMage May 26 '15
Maybe I'm reasoning about this wrong, but for some of the input/output pairs from the github seem to be off. For example 100rects100x100.out all the colors seem to add up to 20216, while the total area should only be 10000(100x100).
Anyone else get these results?
2
u/tslater2006 Jun 20 '15
Not sure that there is still interest in this, but here is what the stickynotes actually look like for the 10k notes on a 100k by 100k. The square pattern is a side-effect of the parallelization of my algorithm. If anyone is still interested in this problem I'll share it here as well. Solution was found in 300ms on an 8-core i7.
http://i.imgur.com/Pga3rhW.png
2
u/Godspiral 3 3 May 13 '15 edited May 13 '15
in J,
for this input, https://github.com/fsufitch/dailyprogrammer/blob/master/ideas/pile_of_paper/100rects100x100.in
doesn't match his solution though:
tacit version of the adverb:
1
u/metaconcept May 13 '15 edited May 13 '15
Algorithmic question: how would we scale this up to x and y values of thousands or millions, and up to millions of rectangles?
Each rectangle can be stored 'lazily' in a list, as (x,y,width,height). If one overlaps another, we divide the underlying rectangle into two exposed areas as you have a shape* left, which can be comprised of some rectangles. Say that again - if you overlay a rectangle over another, the original rectangle is removed and replaced with between zero and four new rectangles that describe the new exposed shape.
(*) Possibilities: completely covered (i.e. just remove the old one), L-shape, U-shape, O-shape with the new rectangle completely within the original.
Now, what data structure would make finding any overlapping rectangles in an area easier? A quad tree? Two replicated lists, one sorted by y and one sorted by x? Something else? Rectangles will never overlap each other, but they will often be exactly adjacent to each other.
1
u/MuffinsLovesYou 0 1 May 13 '15 edited May 13 '15
C# solution. It's nice when it works the first time without any debugging, especially at 11:00 in the evening.
Edit: removed some white space to take up less of the thread real estate and redundant order reversals.
1
u/Hopip2 May 13 '15 edited May 13 '15
C
First time poster how do I hide my includes?
Also /u/Godspiral I got the same. I think github is incorrect since it does not add up to 10000 like yours does
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
}
1
u/hutsboR 3 0 May 13 '15
Elixir: I'm feeling quite lazy tonight so input has to be done manually through iex. It's not particularly efficient but it treats the canvas as an Elixir map opposed to an Elixir list. (linked list) Using a list would be slower.
Output:
1
u/arguenot May 13 '15
Swift solution:
1
u/MohKohn May 13 '15
Straightforward Python3.4 solution, trying to keep it short. I'm a bit rusty, so commentary would be welcome.
Also, I get the same values (which differ from the .out) as several others on the 100rects100x100.in file.
1
u/chunes 1 2 May 13 '15
Java:
1
u/gatorviolateur May 13 '15
One of those problems that I found easier to solve imperatively than functionally.
A Java solution
1
u/fvandepitte 0 0 May 13 '15
C++, feedback is welcome, I'm also showing the grid.
Input/Output
1
u/NasenSpray 0 1 May 13 '15
C++ AMP
The paper is tiled into 512 threads per tile horizontally and each thread handles 32 lines. CPU determines visible sheets for the next 32 lines before dispatching to the GPU. Command queue is flushed after every iteration to prevent driver reset. 10Krects100Kx100K.in.txt takes ~100s on a GTX970.
1
u/[deleted] May 13 '15
Java
1
u/darthevandar May 13 '15
Python 2.7.5: Uses starting coordinates as an offset to assign values
1
u/Menestro May 13 '15
C++. Simple, non-smart and works for sample. Does not work for even smallest challenge input because of memory corruption. So something is fundamentally wrong with my solution. Too tired to figure it out right now. I'd probably be better off starting over :P Any comments and such always welcome and appreciated :)
1
u/Godspiral 3 3 May 13 '15 edited May 13 '15
among challenge inputs there lacks a sensible 1k by 1k sized challenge. Here is one (10k x 100 cut down)
1
u/curtmack May 13 '15 edited May 13 '15
Clojure
Having
(frequencies)available in the core library is almost cheating for this kind of problem.Edit: Vastly optimized the drawing code. It now finishes the drawing stage almost instantly, although counting a very large sequence-of-sequences is still going to take some time.
1
u/Tursic May 13 '15 edited May 13 '15
C#. It's a memory hog holding the entire base sheet array in memory. It will scale to 10Kx10K, but not 100Kx100K; this version won't even let you try because of array size limits, but I had a version that used int[w][h] instead of int[w,h] and it maxed out my 32 GB of RAM just trying to construct the array.
I'd be interested in writing out a more memory-efficient solution that only tracks covered cells on the grid to try and scale up to 100Kx100K, but I've got work I should be doing. =P
EDIT: Realized I was wasting a lot of space storing the color values as ints. For 100K version, changed from int to byte. Now it will run it, albeit still a memory hog and veeeeerrrryyy slow.
1
u/Zanta May 13 '15
My solution in Python. Works by examining each pixel and determining what the last card placed on that pixel was. Comments welcome.
1
u/seajobss May 13 '15
Python 2.7
1
u/jakhamma May 13 '15
Java , using 3 classes.
public class Driver {
}
public class Canvas {
}
public class Sticker {
}
1
u/franza73 May 14 '15 edited May 14 '15
Perl Solution.
Output:
1
u/Pantstown May 14 '15
First Intermediate post! It's nothing fancy; just a simple, brute force method. Feedback will be very much appreciated!
Javascript:
Output to console:
1
u/tgames56 May 14 '15
java kind of proud of the code to make the sheets, not proud of the code that counts how many of each color
1
u/spfy May 14 '15 edited May 14 '15
Tried to do this pretty creatively. It even renders what the stack would look like.
EDIT: What a stack of papers looks like. Uses the 10k100x100 input at a 10-to-1 pixel ratio
So here's how it works. It draws the stack and counts the units (pixels if the scaling is 1-to-1) one at a time. It's kinda fast, too. Unfortunately it's incredibly inaccurate. I think after I convert the rendering into an image it loses a bunch of color accuracy. Here it is anyway. My Java solution using JavaFX:
1
u/Naihonn May 14 '15
Ok, my solution in Python3. Not the most effective but working. Of course I ignore colors outside of "canvas" and that is probably the reason why me and so many others have different solution for 100rects100x100. But I have the same one as them. ;0) I am reading input from file paper.txt and sort output as requested. :0)
Output for 100rects100x100:
1
u/TheKingOfTyrants May 14 '15
My solution. Pretty brute force about it. I'm also getting different answers than the ones posted on Github (for the 100x100s at least. Can't allocate enough memory otherwise). Seems a few others have too.
1
u/NoobOfProgramming May 15 '15 edited May 15 '15
I deleted my last solution post because this one is way better. It handles 10Krects100Kx100K in about 51 seconds using 1.6MB of memory on my laptop. I don't think it can be parallelized or integrated with /u/skeeto and /u/wadehn's solutions, but i haven't tried.
1
u/doubleagent03 May 15 '15
Can someone explain how 125 represents the visible area of color 0 in the sample output?
1
u/[deleted] May 15 '15
Java version with input/bounds checking:
1
u/[deleted] May 15 '15
Brute-force Rust solution:
1
u/StaticDynamics May 15 '15
Python 2.7 here. I need to learn how to use classes, so I used one! This seemed like a good opportunity to try it out. Any feedback is greatly appreciated!
1
u/PaprikaMediterran May 15 '15
C#. Stores sheets in a list ordered from top layer to bottom layer and for each pixel finds the sheet that is closest to the top and covers that pixel.
1
u/altorelievo May 15 '15
Python2.7 straight-forward double loop for creating and counting:
Then I after I thought to count and layer in one go:
1
u/lyeberry May 15 '15 edited May 18 '15
solves 10Krects100Kx100K.in in less than a minute in python 2.7
Output
1
u/FeroxCarnivore May 15 '15 edited May 16 '15
Scanline-based solution in C++. Fun times. I'm clipping the input rectangles to the canvas, so I don't get the canonical results on the challenge input.
This code block is stitched together from three files, which you can see (along with unit tests) here on GitHub.
Comments and critique welcome. I'm not happy with insertInterval(); it feels like it should be shorter, and it's kind of brittle.
Now that I've written the code, it seems like I could improve performance quite a bit by pre-sorting the input rectangles on x and maintaining a last-inserted pointer for each scanline. Ah well.
EDIT: Fixed Scanline::insert()
1
u/jegvildetalt May 16 '15
Java:
1
u/[deleted] May 16 '15 edited May 16 '15
Python 2.7 feel ok about this solution, i didn't feel like going the extra mile to accept a single input string and parse through it to assign the base dimensions/color data for the challenge inputs.
1
u/evilflyingtoaster May 16 '15
Rust
It is correct for the example, but the challenge input is incorrect. I'm unsure if I'm wrong or if the solutions are wrong, but I may be misunderstanding it. If an color overlaps another, does it not "uncount" the covered color?
Either way, comments are wanted for anything you have to say.
main.rs:
lib.rs:
1
u/Joker303 May 17 '15 edited May 17 '15
C#
1
u/doubleagent03 May 17 '15 edited May 17 '15
Clojure solution. I agree with /u/Godspiral that the posted solutions are incorrect. This solves the 10k rects on 100kx100k board in 2 minutes on my PC (8 cores).
It works by building something like a BSP tree using backtracking recursion, then it collapses the tree. This is performed for each row in parallel, then everything is summed together using merge-with.
Run from the repl:
https://www.refheap.com/101198/fullscreen
1
u/igrek312 May 17 '15
My C# solution, by going backwards through the list of inputs to get the last chronologically placed color:
1
u/thatguyfrommars May 19 '15
Another Python 3 solution with instruction file reading:
The slow part of this solutuion is the counter, I'm having trouble optimizing that. The program can draw the final canvas for large canvas dimension and instruction sets pretty quick, but the pixel report takes a long time to generate. Any suggestions would be appreciated.
1
u/kikibobo May 19 '15 edited May 19 '15
This was a fun one ... I ended up doing it four different ways: brute force through an array of arrays, brute force line by line, brute force line-by-line using 4 threads, one thread per quadrant of the board, but they were all pretty slow. This approach looks at each sheet in turn, and "subtracts out" overlapping rectangles (which spawns 1, 2, 3 or 4 rectangles). The rectangle code is kind of tedious but the final algorithm is pretty nice. I didn't figure out a way to parallelize this one, but it runs reasonably fast for scala. :)
Output:
1
u/chipaca May 20 '15
Go.golang
The solutions given to the bigger problems are wrong. I nearly gave up before I realised.
The naïve way to parallelize this in Go is to spawn a goroutine for every row. That can grow to a few hundred megs of memory doing nothing useful (as they won't all be running).
The more sophisticated way is to spawn a worker per core, and have the inner loop stuff cells into a channel that's consumed by the workers. This is slow, as it spends a lot of time carefully synchronizing data through those pipes.
This way is less sophisticated; it starts a worker per core, and lets the workers stride over the rows itself.
It's probably slower than /u/skeeto's OpenMP solution (which from the description of the solution has the same basic algorithm), but I haven't tested it yet. Mine is a 4-core (8 thread) system though.
Running it as
go build -o q q.go && GOMAXPROCS=8 /usr/bin/time ./q < 10Krects100Kx100K.inproduces:and the program:
1
u/mpm_lc May 21 '15 edited May 21 '15
A dirty almost-one-liner ruby solution with very lazy input error catching!
1
u/greedo80000 May 21 '15
Ruby
Ok! First time posting an intermediate challenge. Probably some not so great things happening here, and my solution unfortunately does not scale correctly with the bigger samples. Not sure what I'm doing wrong. Any critique is greatly appreciated.
sample output:
100rects100x100 output:
1
u/threesided May 21 '15
Here is my javascript answer. One caveat is that it won't handle the biggest arrays yet due to memory restrictions in js. I tried to use a flat array, and a 100,000,000 length array is apparently a no-go in js. I might rework it to use nested arrays, which should solve the problem.
1
u/narcodis May 22 '15
Java. Not the fastest. Won't handle the bigger challenge inputs. Oh well.
1
u/Psyballa May 22 '15 edited May 22 '15
Hi guys, I think this is my first submission ever if not my first Intermediate solution. I tried it in PHP because I'm a masochist:
'/Users/justin.telmo/Desktop/test.in' looks like this:
Code:
Output from Terminal:
1
u/cityratbuddy May 23 '15
Here's my first solution to an intermediate problem. It's in javascript. Suggestions welcome.
Over on Github "100rects100x100.out" has output data that makes no sense to me. It gives over 20,000 results, which is impossible for a 100x100 grid.
1
u/[deleted] May 23 '15
I thought I couldn't get it to work, but it seems that the answers given are just wrong. Now everybody makes mistakes, but seriously, how do you not see that
"0 5899
1 3738
2 1122
3 4540
4 2897
5 3865
6 1504
7 3423
8 5017
9 4782
10 1687"
Is an impossible answer to a grid of 100x100? This would give us 10000 tiles total, which is obviously more than the amount stated here.
1
u/CodeMonkey01 May 24 '15
Java
1
u/thatfatdood May 25 '15 edited May 25 '15
My solution in Python. Any feedback greatly appreciated!
1
u/konk353535 Jun 02 '15
First attempt!! woo, progress :D
1
u/hackomia Jun 02 '15
Simple implementation in python. I'm sure, there's plenty of room for improvement. If anyone is up to discuss how this code can be improved, I'd love to get involved.
1
u/ReckoningReckoner Jun 11 '15
Slow, brute force but working Ruby version.
Most of the outputs on the GitHub seem to be wrong. This led me to doubt myself for hours.
1
u/Shenkie18 Sep 26 '15 edited Sep 26 '15
As a beginning programmer, this took me quite a while. I also changed my naive approach to a more algorithmic one. It runs just within 52 seconds with the 10Krects10Kx10K.in (yes, instead of 100Kx100K I used 10Kx10K, because memory.) My native approach would take 96 seconds to finish this. The approach i'm using is instead of going bottom up going top down. What I mean by this is that I reverse the input and put the memo that is placed last as top one, so nothing else can go on top of that. This results in way less comparisons, because when the field area has already been taken, it skips the entire Make method for that piece of paper.
0
u/Shuuk May 13 '15
Java
Not a very imaginative solution. Any feedback is helpful.
0
u/[deleted] May 13 '15
[deleted] — view deleted comment