Traverse a rectangle's antidiagonals

Question

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 2.
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 (for width and height), 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)

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.

• Jonah: Related: Zigzagify a matrix

Answer 1

J, ¹⁸ 15 bytes

#:&;<@|.`</.@i.

Try it online!

Very similar to Gareth's answer in Zigzagify a matrix. This is the standard J approach for these types of problems, and all I do here is combine it with self-indexing.

Consider 3 3:

• i. Create the matrix:

  0 1 2
  3 4 5
  6 7 8
  

• <@|.`</. For each diagonal, alternate reverse-and-box and box. This is the heart of the logic:

  ┌─┬───┬─────┬───┬─┐
  │0│1 3│6 4 2│5 7│8│
  └─┴───┴─────┴───┴─┘
  

• #:&; Unbox and convert each number to mixed-base 3 3 -- this gives each number's self-index within the original matrix:

  0 0
  0 1
  1 0
  2 0
  1 1
  0 2
  1 2
  2 1
  2 2
  

Answer 2

Jelly, 7 bytes

pS;ị\$Þ

A dyadic Link that accepts \$w\$ on the left and \$h\$ on the right and yields the path as a list of 1-indexed coordinates.

Try it online! Or see the test-suite (converts the output to 0-indexing).

How?

Each anti-diagonal consists of the maximal subset of coordinates that have the same sum. The path traverses these anti-diagonals in this coordinate-sum order. Those with odd sums are traversed in row order, while those with even sums are traversed in column order. (This is all true regardless of whether 0 or 1 indexing is employed.)

pS;ị\$Þ - Link: integer, w; integer h
p - ([1..w]) Cartesian product ([1..h]) -> coordinates
 Þ - sort by:
 $ - last two links as a monad - f([r, c]):
 S - sum ([r, c]) -> r+c = #diagonal
 \ - last two links as a dyad -f (#diagonal, [r, c]):
 ị - (#diagonal) index into ([r, c]) - 1-based and modular
 -> r if #diagonal is odd; c otherwise
 ; - (#diagonal) concatenate (that)

Answer 3

Haskell, 65 bytes

w#h=[[n-m,m]|n<-[0..w+h],m<-cycle[id,(n-)]!!n<$>[0..n],n-m<w,m<h]

Attempt This Online!

Answer 4

Ruby, (削除) 66 64 (削除ここまで) 61 bytes

->w,h{[*1..w].product([*1..h]).sort_by{|a|[q=a.sum,a[~q%2]]}}

Try it online!

How it works:

First, create the set of coordinates from the cartesian product of X and Y, then sort by sum and then by ascending or descending X alternatively.

Answer 5

JavaScript (V8), 73 bytes

Expects (w)(h). Prints the coordinates.

w=>h=>{for(i=j=0;~j||(j=++i)<w+h;j--)i-(x=i&1?i-j:j)<h&x<w&&print(x,i-x)}

Try it online!

How?

We walk through the upper-left diagonals of a square of width \$w+h\$, going alternately from top-right to bottom-left and the other way around. We print only the coordinates that are within the target rectangle.

Below is an example for \$w=3\$ and \$h=2\$:

example

NB: Processing the longest diagonal never brings any new cell. It's just golfier to include it.

Answer 6

sclin, 46 bytes

O>a Q*"_`"map"+/"group""sort"rev2% \_` &#"mapf

Try it here! Takes input as list [ h w ].

For testing purposes:

[3 5] ; \>A map f>o
O>a Q*"_`"map"+/"group""sort"rev2% \_` &#"mapf

Explanation

Prettified code:

O>a Q* \_` map \+/ group () sort ( rev 2% \_` &# ) mapf

Assuming input [ h w ].

• O>a vectorized range over [ h w ]
• Q* \_` map Cartesian product and reverse each generated pair to get properly ordered matrix coordinates
• \+/ group () sort group pairs by sum and sort by sum
  • this creates a nicely ordered set of diagonals
• ( rev 2% \_` &# ) mapf reverse every odd (0-indexed) diagonal and flatten into a list of pairs

Answer 7

Alchemist, 145 bytes

_->In_r+In_d+s
s+r+d->z
z+0m->z+m+Out_l+Out_","+Out_u+Out_"\n"
0b+m+l+d->r+u
0b+m+0l+d->b+u
0b+m+r+0d->b+l
b+m+r+u->b+l+d
b+m+r+0u->l
b+m+0r+d->u

Try it online!

After the first two iterations, the atoms are a direct representation of the current state of the traversal.

_: starting atom

s: needed to initialize r and d properly

z: initialization complete

u, d, l, r: number of tiles away from top/bottom/left/right boundary

m: should move next iteration (otherwise output coordinates)

b: current direction is up+right. There was a complementary a atom, but removing it saved 5 bytes.

Answer 8

Charcoal, 41 bytes

NθFNFθ⊞υ⟦+ικ§⟦ικ⟧+ικκι⟧≔⟦⟧ηW−υη⊞η⌊ιIEη✂ι2

Try it online! Link is to verbose version of code. Port of @JonathanAllen's Jelly answer. Explanation:

NθFNFθ⊞υ⟦+ικ§⟦ικ⟧+ικκι⟧

Generate a list of coordinates and their sort order.

≔⟦⟧ηW−υη⊞η⌊ι

Sort them.

IEη✂ι2

Output just the coordinates.

38 bytes using the newer version of Charcoal on ATO:

Nθ≔ΣENEθ⟦+ιλ§⟦ιλ⟧+ιλλι⟧ηW−ηυ⊞υ⌊ιIEυ✂ι2

Attempt This Online! Link is to verbose version of code.

I also tried a canvas-walking approach but that weighed in at a massive 69 bytes:

UONN*≔5θ⊞υ⟦i×ばつ3⊖θ2θ⟧c/o⌊KD2✳κι✳ιψ⊞υ⟦ij⟧¿−ιθ≦−6θ»⎚Iυ

Try it online! Link is to verbose version of code.

Answer 9

05AB1E, 13 bytes

Ý€ ̈`âΣODyRsè‚

Input as a pair [w,h]. Uses 0-based output.

Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well!
Unfortunately, this approach doesn't port too well to 05AB1E, since it's almost double the byte-count of his answer.. :/

Try it online or verify all test cases.

Explanation:

Ý # Convert the values in the (implicit) input-pair to a list in the range [0,v]
 € ̈ # Remove the last value from each to make the ranges [0,v)
 # (note: we can't use `L` instead of `Ý€ ̈` for a [1,v]-ranged list, since it
 # would result in [1,0] for input 0)
 ` # Pop and push both lists separated to the stack
 â # Take the cartesian product of the two list, creating pairs
Σ # Sort these pairs by:
 O # Take the sum of the pair
 D # Duplicate this sum
 y # Push the pair again
 R # Reverse it (necessary, since 05AB1E uses 0-based indexing instead of 1-based)
 s # Swap so one of the sums is at the top of the stack
 è # Modular 0-based index it into the pair
 ‚ # Pair it together with the other sum
 # (after which the sorted list of pairs is output implicitly)

The ODyRsè‚ can be a lot of other alternatives (some examples below), but I've been unable to find anything shorter:

OyRyOè‚
RDODŠè‚
O©y®<è‚
ÐO<è‚€O
ÂsOè}ΣO
...

• Emigna: Apparently I'm blind :)
• Kevin Cruijssen: @Emigna It happens. ;) Also, welcome back! Didn't knew you were active again. I see you're posting in ><> since being November.
• Emigna: Yeah, I've started doing some challenges when time allow. And ><> is very fun to golf in :)

Answer 10

R, 63 bytes

\(w,h,x=matrix(1:w,w,h),y=col(x))(x+y*1i)[order(s<-x+y,x*s%%2)]

Attempt This Online!

Since R is not very good at working with matrices of pairs, this returns the coordinates as the components of a complex number (1-indexed, converted to 0-indexed in the footer for convenience).

Thanks to pajonk for spotting an unnecessary byte.

• pajonk: Why the - in x*-s%%2? Looks like it can be omitted?
• Kirill L.: @pajonk, it was there because it's not a good idea to do golfing half-asleep :D.