Skip to main content
Edit post to show link
Source Link
leo848
  • 637
  • 3
  • 4

Traverse a rectangle's antidiagonalsTraverse a rectangle's antidiagonals

There exists a bijection between the natural and rational numbers that works (approximately) like this:

  1. You create a 1-indexed 2-dimensional grid.
  2. In every field of this grid with position (x, y), put the number x / y.
  3. You start at (1,1) and iterate over the field in the following way:

Bijection

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):

  1. Start at (0,0).
  2. Go one field down, if in bounds, else right.
  3. Go one field to the right and one up (in one step), if in bounds, else go to step 5.
  4. Repeat step 3.
  5. Go one field to the right, if in bounds, else down.
  6. Go one field to the left and one down (in one step), if in bounds, else go to step 8.
  7. Repeat step 6 until you reach an edge.
  8. 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 and h 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

Visual depiction of the algorithm

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

isu

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)

InputOutput
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 , so the shortest output (measured in bytes) wins.

Traverse a rectangle's antidiagonals

There exists a bijection between the natural and rational numbers that works (approximately) like this:

  1. You create a 1-indexed 2-dimensional grid.
  2. In every field of this grid with position (x, y), put the number x / y.
  3. You start at (1,1) and iterate over the field in the following way:

Bijection

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):

  1. Start at (0,0).
  2. Go one field down, if in bounds, else right.
  3. Go one field to the right and one up (in one step), if in bounds, else go to step 5.
  4. Repeat step 3.
  5. Go one field to the right, if in bounds, else down.
  6. Go one field to the left and one down (in one step), if in bounds, else go to step 8.
  7. Repeat step 6 until you reach an edge.
  8. 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 and h 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

Visual depiction of the algorithm

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

isu

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)

InputOutput
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 , so the shortest output (measured in bytes) wins.

`code blocks`
Source Link
leo848
  • 637
  • 3
  • 4

There exists a bijection between the natural and rational numbers that works (approximately) like this:

  1. You create a 1-indexed 2-dimensional grid.
  2. In every field of this grid with position (x, y), put the number x / y.
  3. You start at (1,1)(1,1) and iterate over the field in the following way:
  1. Start at (0,0)(0,0).
  2. Go one field down, if in bounds, else right.
  3. Go one field to the right and one up (in one step), if in bounds, else go to step 5.
  4. Repeat step 3.
  5. Go one field to the right, if in bounds, else down.
  6. Go one field to the left and one down (in one step), if in bounds, else go to step 8.
  7. Repeat step 6 until you reach an edge.
  8. Go to step 2.

ExamplesExample 1

Example 2

There exists a bijection between the natural and rational numbers that works like this:

  1. You create a 1-indexed 2-dimensional grid.
  2. In every field of this grid with position (x, y), put the number x / y.
  3. You start at (1,1) and iterate over the field in the following way:
  1. Start at (0,0).
  2. Go one field down, if in bounds, else right.
  3. Go one field to the right and one up (in one step), if in bounds, else go to step 5.
  4. Repeat step 3.
  5. Go one field to the right, if in bounds, else down.
  6. Go one field to the left and one down (in one step), if in bounds, else go to step 8.
  7. Repeat step 6 until you reach an edge.
  8. Go to step 2.

Examples

There exists a bijection between the natural and rational numbers that works (approximately) like this:

  1. You create a 1-indexed 2-dimensional grid.
  2. In every field of this grid with position (x, y), put the number x / y.
  3. You start at (1,1) and iterate over the field in the following way:
  1. Start at (0,0).
  2. Go one field down, if in bounds, else right.
  3. Go one field to the right and one up (in one step), if in bounds, else go to step 5.
  4. Repeat step 3.
  5. Go one field to the right, if in bounds, else down.
  6. Go one field to the left and one down (in one step), if in bounds, else go to step 8.
  7. Repeat step 6 until you reach an edge.
  8. Go to step 2.

Example 1

Example 2

array formatting
Source Link
leo848
  • 637
  • 3
  • 4
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)]
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)]
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)]
Fixed formatting and added correct tag
Source Link
leo848
  • 637
  • 3
  • 4
Loading
Fixed issues in description and made initial problem description more clear
Source Link
leo848
  • 637
  • 3
  • 4
Loading
edited body
Source Link
leo848
  • 637
  • 3
  • 4
Loading
Source Link
leo848
  • 637
  • 3
  • 4
Loading