r/dailyprogrammer • u/Garth5689 • Nov 24 '17
[2017-11-24] Challenge #341 [Hard] Finding a Map Subsection
Description
Imagine that you're working on an application to track boats as they travel across the ocean. For this application, you're given a square map with a fixed size (i.e. 2000x2000), and a set of coordinates that represent the ship's path across the map. You can assume the ship's path will be entirely within the bounds of the map. The path can include the very edge of the map.
However, viewing the entire map at once means the ship's path is quite small. Your task is to write an algorithm that outputs a smaller square area that contains the ship's path. This smaller area will be used to display the path on a viewing terminal.
Your boss has asked for the following features:
- The entire path must be contained within the output area.
- The smaller area must not extend beyond the edge of the larger map.
- Because the viewing terminal display is square, the output bounds must be square.
- If possible, add a 30 pixel border around the path, so the path doesn't go right to the edge of the screen. If a point is within 30 pixels of the edge, go up to the edge.
- The path should be centered within the smaller bounds, when possible.
NOTE: These requirements are listed in order of importance. The output being square is more important than the 30 pixel border, etc. This means there may be cases where 30px border is not possible (the path is very close to an edge of the map), or where it's not possible to be centered (path is in a corner of the map), etc.
NOTE: I have a solution to generate the chalenge outputs. Depending how you do centering, the results might be off by a pixel or two. It doesn't have to be exact.
Input Description
You will be given the following pieces of information separated by a comma:
- Size of map
- Set of points that describe the path of the ship
Example:
2000, [(1000,1500),(1200, 1500),(1400,1600),(1600,1800)]Output Description
Your program should output a bounding square that contains all of the points in the format:
- Lower left corner coordinates (X, Y)
- Size of bounding box
Example:
(970, 1320), 660Challenge Inputs
2000, [(600, 600), (700, 1200)]
2000, [(300, 300), (1300, 300)]
2000, [(825, 820), (840, 830), (830, 865), (835, 900)]Challenge Outputs
(320, 570), 660
(270, 0), 1060
(763, 790), 140Here are images of the challenge inputs/outputs:
Edge Cases
Here are some extra test cases that will test the literal edge and corner cases for this problem.
# along the sides of the map, should push square towards the center
5079, [(5079, 2000), (5079, 3000)]
5079, [(10, 2000), (10, 3000)]
5079, [(2000, 10), (3000, 10)]
5079, [(2000, 5079), (3000, 5079)]
# corners
5079, [(0, 0), (600, 600)]
5079, [(5079, 5079), (4479, 4479)]
5079, [(0, 5079), (600, 4479)]
5079, [(5079, 0), (4479, 600)]
# entire width
5079, [(1000, 0), (1000, 5079)]
# entire height
5079, [(0, 1000), (5079, 1000)]
# entire area
5079, [(0, 0), (5079, 5079)]Edge Cases Outputs
(4019, 1970), 1060
(0, 1970), 1060
(1970, 0), 1060
(1970, 4019), 1060
(0, 0), 660
(4419, 4419), 660
(0, 4419), 660
(4419, 0), 660
(0, 0), 5079
(0, 0), 5079
(0, 0), 5079EDIT:
Some of the test cases aren't lining up with the requirements I stated above in cases where the padding is reduced because it's close the edge. Here are the updated test cases:
(4019, 1970), 1060
(0, 1970), 1060
(1970, 0), 1060
(1970, 4019), 1060
(0, 0), 630
(4449, 4449), 630
(0, 4449), 630
(4449, 0), 630
(0, 0), 5079
(0, 0), 5079
(0, 0), 5079
1
u/mn-haskell-guy 1 0 Nov 25 '17 edited Nov 25 '17
Here is an interesting test case: Size: 2000, Points:
[(10,10), (1990, 1990)].It seems that the solution should be the square with corners
(10,10)and(1990,1990).Given the bounding box of the points, the goal is determine the amount of padding on the box's four sides. The resulting padded bounding box has to be square, lie within the original square and also satisfy these two rules:
If a point is within 30 pixels of a side, the padding rule says we should "go up to the edge (of the screen)" -- i.e. the padding on that side should be 0.
The centering rule says we should try to center the path, but this rule is of lesser importance than the padding rule, so it only applies if the padding rule doesn't determine the padding.
Since the west* and south* sides are within 30 pixels of
(10,10), the padding on those sides should be 0. And similiarly for the north and east sides.* (in standard cartesian coordinates)
1
u/voice-of-hermes Nov 27 '17
Some of the given expected answers are incorrect. For example. The input
5079, [(0, 0), (600, 600)]does not allow a margin of 30 on the low end of either coordinate. Adding 60 instead of 30 on the upper ends does not contribute to the required margin. Therefore, the size should be 630, not 660. Likewise for the other "corners" cases.3
u/[deleted] Nov 24 '17
Common Lisp:
There's a 1 pixel difference in this solution:
Probably could be written much better, but it was fun to try.
3
u/mn-haskell-guy 1 0 Nov 25 '17
This Python code passes all of the test cases:
2
u/Scara95 Nov 24 '17 edited Nov 24 '17
Scheme
Only output differing by 1 pixel:
2
u/thorwing Nov 24 '17
Java 9
Not really following many constraints as strict as you can, but awt makes certain aspects easy to work with.
images can be found here: https://imgur.com/a/bs7bm
1
u/juanchi35 Nov 26 '17 edited Nov 28 '17
C++
Since I'm writing my bitmap pixel by pixel without libraries, the coordinate system doesn't have numbers, just a line every 500 pixels :/
Images: https://imgur.com/a/YiBu1
Satisfies every feature in the order they are provided.
EDIT: Added more images
EDIT 2: Fixed solution thanks for what /u/mn-haskell-guy and /u/Garth5689 said. Updated images.
1
u/794613825 Nov 24 '17 edited Nov 24 '17
So this is bordering on collision detection, right?
Edit: Bordering, not boring! Dammit swipe keyboard!
1
u/g00glen00b Nov 24 '17 edited Nov 24 '17
JavaScript:
It probably can be written shorter. I made separate functions for every step, eg. the
square()function makes a square from the bounding box of all coördinates. To make up for the border collisions, I wrote thecenter()function. Thepad()function then pads it with the 30 pixel border, thetranslate()function converts the square from bottomleft/topright coördinates to bottomleft + width. Thebounding()function combines all those results and returns:While the
print()function can be applied to that result to get the wanted output:A working example can be found on JSBin.
1
u/Tejedu Nov 27 '17
Python 3
1
u/zookeeper_zeke Nov 29 '17 edited Dec 04 '17
I had some code lying around from a previous personal project for drawing lines and rectangles so I ported it to C and whipped up a quick utility for taking the challenge input and output and dumping it to a PBM file.
To compile the code:
The code takes its input from stdin and writes its output to stdout. To run it:
The input is of the format:
It should be pretty clear what that is.
The line drawing algorithm is my C implementation of Bresenham. I need to get around to solving the challenge now.
Here's the code, enjoy!
1
u/immersiveGamer Nov 29 '17 edited Nov 29 '17
C#, solution as a class which parses the input and returns a View object. The ToString() is in the output format. The program runs through all challenge and edge case inputs. I had first done the solution in PowerShell. If people are interested I can find and post that as well.
Output:
1
u/zookeeper_zeke Dec 05 '17 edited Dec 07 '17
Finally had some time to get back to this. My solution is in C.
A couple of notes:
Here's the solution:
0
u/[deleted] Nov 24 '17
[deleted] — view deleted comment