Problem Statement
On a piece of graph paper, you want to draw a long line that wraps around at the edges of the graph paper. Every time you reach an edge, you start drawing at the opposite edge in the same exact spot. To aid yourself in drawing accurately, you come up with an x and y offset, which you use to draw each piece of the line. If you reach a corner, depending on your offsets, you may pass through 1 or 2 edges. This may take you to the opposite corner, or a corner along the same edge. If you continue drawing the line, eventually, it will reach the same spot that you started from. You are to count how many line segments there are on the graph paper after you are done drawing. A line segment extends from one edge or corner of the graph paper, to another edge or corner.
When referring to a coordinate (x, y) in this problem, x is how many squares from the left edge of the paper, and y is how many squares from the top edge of the paper. Thus, on a graph paper of size 4x4, the coordinate (3,2) would be where the X is in the following diagram:
+--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--X--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+
Create a class LongLine that contains the method count, which takes a single
params[0] - width: how many cells wide the graph paper is.
params[1] - height: how many cells high the graph paper is.
params[2] - startx: The line begins at X coordinate startx.
params[3] - starty: The line begins at Y coordinate starty.
params[4] - distx: how much to add to or subtract from the x coordinate each time you draw a piece.
params[5] - disty: how much to add to or subtract from the y coordinate each time you draw a piece.
The method should return how many line segments are drawn on the page.
Definition
- Class:
- LongLine
- Method:
- count
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int count(int[] params)
- (be sure your method is public)
Notes
- A line may reach its exact original coordinates before finishing a particular piece (see third example).
- If dx is 0, then x will never change. If dy is 0, then y will never change. This is true even for lines drawn into corners. See example 6.
Constraints
- params will have exactly 6 elements.
- Element 0 of params (width) is between 1 and 1000, inclusive
- Element 1 of params (height) is between 1 and 1000, inclusive
- Element 2 of params (startx) is between 0 and width - 1, inclusive
- Element 3 of params (starty) is between 0 and height - 1, inclusive
- Element 4 of params (distx) is between -10000 and 10000, inclusive
- Element 5 of params (disty) is between -10000 and 10000, inclusive
- Elements 4 and 5 of params (distx and disty) cannot both be 0
Examples
{997, 991, 976, 31, 9949, 9941}
Returns: 19770635
This is the worst test case I could think of. All the arguments are the largest prime numbers they can be, so the maximum number of line segments is reached (this example won't be in the final problem statement)
{1000, 999, 999, 10, 9999, 10000}
Returns: 19989000
OK, I thought of a worser case :) Each pair is relatively prime. (this example won't be in the final problem statement)
{10, 10, 0, 0, 2, 10}
Returns: 5
Each line segment goes from the top to the bottom of the paper, and travels two cells to the right. Here are all the line segments: (0,0) - (2,10) (2,0) - (4,10) (4,0) - (6,10) (6,0) - (8,10) (8,0) - (10,10) Since the last segment goes into the lower right corner, it wraps back to the upper left corner which is where we started.
{10, 10, 1, 0, 2, 10}
Returns: 6
This is the same as the last example, except it starts at (1,0). There are 4 line segments that extend from the top to the bottom of the graph paper: (1,0) - (3,10) (3,0) - (5,10) (5,0) - (7,10) (7,0) - (9,10) The final full height segment is split in half by the right edge of the paper: (9,0) - (10,5) (0,5) - (1,10)
{3, 2, 1, 1, 2, 4}
Returns: 4
Here is an example where the last increment can only be drawn half-way because it's midpoint is at the original starting coordinate. The resulting line segments are: (0,1) - (0.5,2) (0.5,0) - (1.5,2) (1.5,0) - (2.5,2) (2.5,0) - (3,1) Note that the starting point is contained in the full line segment (0.5,0) - (1.5,2).
{1000, 1000, 0, 0, 4000, 4000}
Returns: 1
{1000, 1000, 0, 1, -555, 1000}
Returns: 311
Here is an example with a negative distance
{1, 1, 0, 0, 1000, -999}
Returns: 1998
{97, 101, 25, 32, 11, 19}
Returns: 2953
{1, 1000, 0, 1, -9999, 1}
Returns: 9999000
{50, 50, 49, 49, -1, -1}
Returns: 1
{1, 1, 0, 0, 9876, -9876}
Returns: 1
{1, 1, 0, 0, -9875, 9876}
Returns: 19750
{123, 456, 78, 91, -1112, 1314}
Returns: 111449
{5, 50, 2, 3, 50, 5}
Returns: 101
{3, 3, 1, 1, 0, 5}
Returns: 1
{122, 344, 0, 0, -1, 0}
Returns: 1
{10,10,0,0,1,0}
Returns: 1
There is only one segment from 0,0 to 10,0.
{ 1000, 999, 43, 27, -4437, 8358 }
Returns: 4263520
{ 1, 1, 0, 0, 1, 0 }
Returns: 1
{ 97, 101, 25, 32, 11, 19 }
Returns: 2953
{ 1000, 1000, 0, 0, 1, 1 }
Returns: 1
{ 3, 3, 1, 2, 1, -1 }
Returns: 1
{ 13, 15, 1, 3, 479, 978 }
Returns: 6632
{ 1000, 1000, 0, 0, -10000, 1 }
Returns: 10000
{ 10, 10, 1, 2, -35, -47 }
Returns: 82
{ 10, 10, 0, 0, 2, 10 }
Returns: 5
{ 100, 100, 0, 0, 100, 200 }
Returns: 2
{ 1000, 1000, 500, 0, 1, 1 }
Returns: 2
{ 1, 1, 0, 0, 0, 1 }
Returns: 1
{ 10, 10, 1, 0, 2, 10 }
Returns: 6
{ 5, 5, 0, 0, -1, 1 }
Returns: 1
{ 1000, 1000, 0, 0, 10000, 9999 }
Returns: 19998
{ 10, 10, 0, 0, 100, 10 }
Returns: 10
{ 4, 4, 1, 1, 1, -1 }
Returns: 2
{ 10, 10, 1, 1, -1, -1 }
Returns: 1
{ 1, 1000, 0, 200, 10000, 1 }
Returns: 10000000
{ 1000, 1000, 2, 3, 9973, 9967 }
Returns: 19940
{ 1, 1, 0, 0, -1, -1 }
Returns: 1
{ 3, 3, 2, 1, 1, -1 }
Returns: 1
{ 3, 3, 2, 1, -1, 1 }
Returns: 1
{ 997, 991, 0, 0, 9949, 9941 }
Returns: 19770635