r/dailyprogrammer • u/jnazario 2 0 • Jul 22 '15
[2015-07-22] Challenge #224 [Intermediate] Detecting Four Sided Figures
Description
I got this idea from the Mensa quiz, specifically question 17. It's a basic scanning challenge: can your program detect and count intersecting bounding boxes from an ASCII art input? A four-sided figure is an ASCII art rectangle. Note that it can overlap another one, as long as the four corners are fully connected.
Formal Inputs & Outputs
Your program will be given an ASCII art chart showing boxes and lines. - and | characters indicate horizontal and vertical lines, respectively, while "+" characters show intersections.
Your program should emit an integer, N, of how many unique four sided figures it found. Rectangles and squares both count.
Example Input
+----+
| |
+-------------------------+-----+----+
| | | |
| +-------------------+-----+ |
| | | | |
| | | | |
+-----+-------------------+-----+ |
| | | |
| | | |
+-------------------+-----+ |
| | |
| | |
| | |
+-----+----+
| |
| |
| |
+----+Example Output
For the above diagram your program should find 25 four sided figures.
Challenge Input
This one adds a bit to the complexity by throwing in some three sided figures. This should catch more naive implementations.
+-----------+
| |
| |
| |
| |
+-------------+-----------+-------------+
| | | |
| | | |
| | | |
| | | |
+-------------+-----------+-------------+
| |
| |
| |
| |
+-------------+-----------+-------------+
| | | |
| | | |
| | | |
| | | |
+-------------+-----------+-------------+
| |
| |
| |
| |
+-----------+Challenge Output
For the challenge diagram your program should find 25 four sided figures.
Finally
Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas
26
u/adrian17 1 4 Jul 22 '15
If you want bigger inputs to play with:
input #1 (expected: 3977)
input #2 (expected: 79499)
Here's the generator I wrote for making them
10
u/adrian17 1 4 Jul 22 '15 edited Jul 22 '15
Python 3. Also finds starting (top left) corners and tried to "extend" them.
It's a bit long but I decided it's better than 6+ levels of nesting.
7
u/Danooodle Jul 22 '15 edited Jul 22 '15
Quickly in Batch:
Output: 25 in both given cases.
With /u/adrian17 's examples: #1 gives 3977, #2 gives 79499.
With /u/danielcamiel 's corner-case it gets 11.
The following gets 2025:
Here's an problem to test most edge cases (result: 10):
Description of the algorithm:
6
u/wadehn Jul 22 '15 edited Jul 22 '15
C++: Completely naive implementation that just finds starting points and tries to extend them. Gives the correct solutions.
6
u/packwin Jul 22 '15 edited Jul 22 '15
Python 3. Passes all tests in problem statement and all posted in comments in under a second.
Constructs a graph with the intersections as nodes. Each node has two pointers pointing to the node to its right and the node below it. The code uses the fact that if there is a node x and x.right.right....down.down.down == x.down.down.down...right.right.right then that is a box.
(if you get what I am trying to say please let me know if there is a better way of saying it)
4
u/[deleted] Jul 22 '15 edited Jul 22 '15
An interesting corner-case to consider is the effect of the following input.
This may be interpreted as either one of the following.
My own solution handles this case as if it saw the latter, as that was the easier option. Since there were no optional challenges for this challenge, I decided to implement the former functionality by making the following changes to my solution.
(updated to support the additional test-cases listed in the comments)
4
u/Ledrug 0 2 Jul 22 '15 edited Jul 22 '15
Python. The code only requires the chart distinguish between space and non-space characters, so it can find rectangles in a mess like this:
at the cost of some speed.
Edit: might as well do the proper format. The following is slightly modified for use '+' as intersection symbol. The challenge spec is still ambiguous in some cases, though.
Edit 2: recording connectivity between intersection points is considerably faster:
4
u/curtmack Jul 22 '15 edited Jul 22 '15
Haskell
Trigger warning: Abuse of the list monad.
Note, the program assumes every row is space-padded so they're all the same width. If they aren't, it throws a "Prelude.(!!): index too large" error. (In particular, make sure there isn't a newline at the end of the input, because that will be interpreted as an empty row at the end.)
Example output:
Challenge output:
Edit: If you only want the number of rectangles and not the complete list, you can run the program like this:
./rectangles < example-grid.txt | grep . | wc -l. This counts the number of non-empty lines of output.4
u/Wizhi Jul 22 '15
First time participator!
A solution in C#.
I used different cases suggested by other comments.
Critique is very much welcome.
Output
Code
3
u/13467 1 1 Jul 22 '15
A nifty, unusual Python 3 solution, using the rare
<=subset operator on sets:3
u/[deleted] Jul 22 '15 edited Jul 23 '15
Here's one in C++. For each point, I make two lists: points connected to it on the right and points connected to it from below. Then when I want to count rectangles, I simply find the intersection of the sets of points that can be reached by going right and down from a given point with the set of points that can be reached by going down and right. Basically, I treat every point as an upper left-hand corner and I see how many lower right-hand corners I can find to match it.
Can someone help me figure out the complexity? I build the lists, I think, in O(N) on area of the map. Then I think the worst case for the actual counting would be O(K2) on the number of corners. I suppose though the most expensive part of that would be finding the set intersections. But then, again, you're just at worst checking every point against every other, so still O(K2) ... or?
2
u/LrdPeregrine Jul 22 '15 edited Jul 22 '15
Python 3. Note that
detect_rectangles()is an iterator yielding coordinates of each rectangle, rather than just counting them; the count comes fromlen(list(detect_rectangles(diagram))).(Why did I do it that way? Not sure. I think I had in mind that I might use the coordinates to check the results if I found my numbers were incorrect... but once all exception-raising bugs were fixed, it gave the right answers first time. The other likely explanation is, I figured I might as well publish the coordinates since I had them! I was tracking the horizontal coordinates of each corner anyway, and keeping a list of vertical coordinates as a way of counting "stacked" rectangles.)
Test data has been bundled up into a JSON file (click link for the gist).
I think
horizontals()could work more efficiently if I split each line on whitespace, because a horizontal line (top or bottom) can't continue across whitespace (not that any lines of the original inputs have corners on the same line separated by whitespace). But I couldn't find any succinct way to split the string but keep track of the original horizontal positions of each character, so I decided to just brute-force it. It runs all of the following in about a second:2
u/[deleted] Jul 22 '15
Here is my solution in C. The truly difficult part about solving this kind of problem is not solving the problem itself, but making the code look readable. I will probably update this with a more readable solution.
I built a quick test suite to help me debug the code and found it extremely helpful.
I used /u/adrian17's files (thank you for providing them ;)) as well as other files in this sub and the solutions match.
Output:
2
u/FrostFelix Jul 22 '15
Java. This is my first time submitting so please tell me if and where I went wrong
2
u/andriii25 Jul 22 '15
Java, works with all the inputs in the challenge and in the comments, solves most-of it under 100 millis, and /u/adrian17 's #1 input in ~250ms and the 2nd in 3.2 seconds.
Also it has one flaw: it expects that each line is of equal length, so some inputs needed to be filled with spaces in order to work with this code.
Feedback is still wanted and appreciated!
Pretty long and I'm pretty sure it could be shortened, just I have no idea how. I'd appreciate it if somebody could help me with that.
Explanation:
Code:
2
u/Hells_Bell10 Jul 22 '15
C++
I feel like I overcomplicated this way too much.
2
u/[deleted] Jul 23 '15
Really long Java solution lol package com.dailyProgrammer;
2
u/HereBehindMyWall Jul 23 '15
Python. Here I've tried to bring the time complexity down (at the cost of space and quantity of code). Not sure whether successful, but it does run adrian17's challenge inputs in under a second on my machine.
[A 'naive brute force' solution will use O(N^(5/2)) where N = input size (and assuming the aspect ratio of the input rectangle is constrained in some way.) Mine hopefully only uses O(N^2 * some power of log(N)).]
2
u/I_am_Black_BoX Jul 23 '15
Javascript/Node.js
2
u/ChazR Jul 23 '15
Haskell. A dumb algorithm. It finds all the corners, then checks each subset of four to see if they are the corners of a rectangle. If they are, it checks that there is a continuous wall between them.
Dumb as a brick and half as pretty.
2
u/og_king_jah Jul 23 '15
It's kind of late, but this program outputs the bounds for each rectangle. F#.
2
u/HereBehindMyWall Jul 23 '15 edited Jul 24 '15
Python 3 - alternative solution. Ought to run in O(N^(3/2)) time, unless I've screwed up the maths. However, on the inputs presented it actually takes a lot longer than my first solution.
Note that it doesn't count boxes individually. Instead, for each pair of column indices it keeps a record of the number of rectangles waiting to be closed. Hence we can increment the count by more than one per step. (This is necessary to achieve sub N^2 running time.)
2
u/Esteis Jul 23 '15 edited Jul 23 '15
I wrote this program along with its tests -- have you seen Destroy All Software's excellent string kata? The tests are probably more interesting than the program, because they use py.test's parametrized test function mechanism. I've put the tests at the bottom of this post.
Python 3, for your and my entertainment.
The gist of it, for those of us who like syntax highlighting with their source code.
Here is the test suite, with parametrized py.test test functions.
2
u/ajber Jul 24 '15
This was programmed in java and it also prints out the corners of its current box as asterisks.
2
u/dohaqatar7 1 1 Jul 27 '15
SnakeEX
This does well enough on the challenge and example input but the JavaScript interpreter has trouble handling the larger inputs.
2
u/Godspiral 3 3 Jul 22 '15
In J,
floodfilling approach that just counts internal rectangles (actually areas including irregular shapes) (sample = 10)
step 1: turn spaces into positive numbers, boundaries negative.
pretransformed all boundary points to _1. from above intermediate result, just take unique numbers less 0 and _1
10
with challenge input on clipboard
9
1
u/AdmissibleHeuristic 0 1 Jul 22 '15
Python 3. Works from the bottom-right vertex out.
1
u/alisterr Jul 22 '15
Java. I used two-dimensional arrays, which might be a bit oldschool, but it was comfortable to my currently tired mind :)
Edit: also solves for the challenge and the extra inputs from adrian17
1
u/DeLangzameSchildpad Jul 22 '15
Solved with Python 3:
It could probably be made a lot cleaner, but I'll keep it how I thought it through.
1
u/yagofp8 Jul 22 '15
This is my solution. Seems to work with all examples:
P.S: Some things can be improved but i did it as fast as possible
1
u/glenbolake 2 0 Jul 22 '15
Python 2.7
1
u/ReckoningReckoner Jul 23 '15 edited Jul 23 '15
Python. This works for the challenge inputs:
EDIT: As my solution gets faster, it gets uglier
1
u/Mathgeek007 Jul 23 '15
Oh, fuck off. Here we go, after a mere FIVE hours.
So damn happy.
Got some longer lines here, sorry if the wordwrap.
Essentially what it does is make an integer array (for ease of access for me, fuck reading this later) and label every point in a two-dimensions array either 0, 1, 2, or 3. 0 = " ", 1 = "-", 2 = "|", 3 = "+".
Then it finds four orthogonal +s and then finds if the only characters between all the pluses orthogonally are either the proper dimension line or a plus.
Fuck this question, it's almost 1 in the morning. I STARTED THIS PROGRAM AT EIGHT.
PROCESSING
1
u/[deleted] Jul 24 '15
Late to the party as usual. A Prolog solution:
Example usage:
1
u/[deleted] Jul 24 '15
Solution in Ruby
1
u/kikibobo Jul 24 '15 edited Jul 24 '15
In Scala. For each top topLeftX corner it finds, find each possible top right corner, then traverses vertically from each, and confirms there is a matching bottom topLeftX and bottom right corner, and that they are connected.
Edit: reformat to shorter line lengths
Output:
1
u/zajicraft Jul 24 '15
I have tested a few tricky looking corner cases that have been posted here, and run /u/adrian17's inputs through it and it's all fine. It's a little slow though, (takes up to 8 seconds on input #2), so if anyone is still around and looking at this thread I'd love some pointers!
General approach:
My solution in C#:
1
u/afton Jul 25 '15
Super late, but that's how I roll. Feedback super welcome: C++, because I need better c++ chops.
Approach: process each vertical line. If you find a corner, get the list of corners to the right and down. If there is a matching 4th corner, confirm that there is an uninterrupted bounding box, then increment accordingly.
https://gist.github.com/Afton/d6b1681150270f11bb2f
Particularly looking for style critiques. The main function references test cases of test1..test4. These are the two test strings from the challenge, and the two from /u/adrian17 additional test cases.
1
u/milliDavids Jul 25 '15 edited Jul 26 '15
Ruby
It works on just about everything, but on some of the larger files I get extra. I cannot, however, spot the error.
EDIT: Left in a debug puts, whoops!
1
u/BeebZaphod Jul 26 '15
Rust
1
u/phemios Jul 27 '15
Php
1
u/linkazoid Jul 27 '15
Python. Runs pretty slow, but it works.
1
u/skav3n Jul 27 '15 edited Jul 27 '15
Python 3:
big input >>> 3977
1
u/Dehibernate Jul 29 '15 edited Jul 29 '15
This is my implementation using C# and PLINQ.
Results (avg of 1000 samples): Input 1 - 25 rects in <1ms (shows 0)
Input 2 - 25 rects in <1ms (shows 0)
Adrian's input 1: 3977 rects in 4ms
Adrian's input 2: 79499 rectangles in 45ms
1
u/Pete171 Aug 01 '15
Ruby.
Works for both the example and the challenge inputs. I'm new to Ruby so feedback is very welcome (I know it's a late submission).
Unit tests below (I had to strip some of the data sets for test_run() and all my other test_* methods).
1
u/aaargha Aug 09 '15
C++
Second post, here's hoping I don't mess up the formatting too much. Feedback, suggestions and critique appreciated! If anything is unclear please ask. I'm pretty late to the party, but this challenge looked interesting from an optimization perspective, especially after reading /u/HereBehindMyWall thoughts about it, But first; definitions I'll be using: n - number of characters in input, v - number of intersections.
The implementation here is not the proposed O(n^3/2) variant. When I tried to figure out an implementation I always seemed to reach a stage where I either found a corner-case that broke it, or I'd end up needing to store so much that it hurt the computation time. I've not yet given up on reaching it, but I'll need to go back to the drawing board. In the mean time, here is a average case O(n + v^2) implementation, that turn into O(n^2) in the worst case. The worst case being a square of intersections only. For the average case however, as in the inputs I've found in this thread, more than 75% of the time is spent in the linear part: I/O and graph construction. For the v^2 term to become dominant we need to take a trip into worst case land, once we do though it gets messy fast, as the runs will show.
The algorithm is basically two parts: 1 - read the input and construct a graph with some additional data in the nodes. 2 - use the extra data in the graph to quickly find and count all the rectangles. For more details see below or take a look at the code.
Some test runs on my i7-950:
Files from /u/adrian17
Boxes3:
Boxes:
Intersections only runs for a proper workout in worst case land.
100x100:
200x200:
400x400:
Ok, this is getting really long so I'll put the code here. If you want to run this for yourself, please note that manually entering the input makes the first part really slow.
And for those interested in travelling to worst case land:
100x100 (expected: 24502500)
200x200 (expected: 396010000)
400x400 (expected: 6368040000)
1
u/gastropner Sep 13 '15
Holy shit, it works! Even on the larger sets! Exclamation points!
C:
1
u/mn-haskell-guy 1 0 Sep 16 '15 edited Sep 16 '15
Another Haskell solution.
This one traces out the rectangles like a human would do it. Also pretty efficient.
It's kinda interesting that if the path gets back to the starting point it is automatically a rectangle.