Traverse a rectangle's antidiagonalsTraverse a rectangle's antidiagonals
There exists a bijection between the natural and rational numbers that works (approximately) like this:
- You create a 1-indexed 2-dimensional grid.
- In every field of this grid with position
(x, y)
, put the numberx / y
. - You start at
(1,1)
and iterate over the field in the following way:
However, this task is not about outputting rational numbers, but about following this pattern in a finite rectangle. This algorithm is best described by an image, but can also be described using words (0-indexing is used this time):
- Start at
(0,0)
. - Go one field down, if in bounds, else right.
- Go one field to the right and one up (in one step), if in bounds, else go to step 5.
- Repeat step 3.
- Go one field to the right, if in bounds, else down.
- Go one field to the left and one down (in one step), if in bounds, else go to step 8.
- Repeat step 6 until you reach an edge.
- Go to step 2.
If at any point you encounter the bottom right field, stop.
Task
Given a rectangle defined by two positive integers w
and h
, output all points (x, y)
on the rectangle in the order in which the above algorithm visits them.
- You must handle the possibility of
w
andh
being equal to zero. - The points can be 1- or 0-indexed.
- The first step must be downwards, not right.
- You can use any ordered sequence format as the return value.
- The length of the output sequence must always be
w * h
. - The first and last element will always be
(0,0)
(or(1,1)
one-indexed) and(w-1, h-1)
(or(w,h)
), respectively. - Standard input / output rules apply.
- Standard loopholes are forbidden.
Example 1
w = 5
, h = 3
In this case, you should thus output:
0,0 0,1 1,0 2,0 1,1 0,2 1,2 2,1 3,0 4,0 3,1 2,2 3,2 4,1 4,2
Example 2
w = 4
, h = 7
Following the red line, the expected output is:
0,0 0,1 1,0 2,0 1,1 0,2 0,3 1,2 2,1 3,0 3,1 2,2 1,3 0,4 0,5 1,4 2,3 3,2 3,3 2,4 1,5 0,6 1,6 2,5 3,4 3,5 2,6 3,6
Test cases (zero-indexed)
Input | Output |
---|---|
w=0 , h=0 |
[] |
w=0 , h=123 |
[] |
w=123 , h=0 |
[] |
w=1 , h=1 |
[(0,0)] |
w=2 , h=2 |
[(0,0), (0,1), (1,0), (1,1)] |
w=10 , h=1 |
[(0,0), (1,0), (2,0), (3,0), (4,0), (5,0), (6,0), (7,0), (8,0), (9,0)] |
w=1 , h=10 |
[(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9)] |
w=3 , h=3 |
[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (1,2), (2,1), (2,2)] |
w=4 , h=4 |
[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (0,3), (1,2), (2,1), (3,0), (3,1), (2,2), (1,3), (2,3), (3,2), (3,3)] |
w=4 , h=7 |
[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (0,3), (1,2), (2,1), (3,0), (3,1), (2,2), (1,3), (0,4), (0,5), (1,4), (2,3), (3,2), (3,3), (2,4), (1,5), (0,6), (1,6), (2,5), (3,4), (3,5), (2,6), (3,6)] |
w=5 , h=3 |
[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (1,2), (2,1), (3,0), (4,0), (3,1), (2,2), (3,2), (4,1), (4,2)] |
This is code-golf, so the shortest output (measured in bytes) wins.