Spanning tree of a rectangular grid

Question

Background

A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of the original graph. The following is an example of a spanning tree of a 4-by-4 grid graph.

Task

Given two positive integers w and h, output any valid spanning tree of the grid graph which has w vertices horizontally and h vertices vertically. There are lots of valid answers; just output one of them. Your code is even allowed to give different outputs across runs, as long as all of them are valid.

Input and output

The input is two positive integers w and h.

The output is a representation of a spanning tree. The output format is restricted to "a list of pairs of numbered vertices", in order to prevent various boring answers (as discussed in the sandbox). Also, the vertex numbering should be in row-major order, e.g.

0 - 1 - 2 - 3
|   |   |   |
4 - 5 - 6 - 7
|   |   |   |
8 - 9 - 10- 11

or

(0,0) - (0,1) - (0,2) - (0,3)
  |       |       |       |
(1,0) - (1,1) - (1,2) - (1,3)
  |       |       |       |
(2,0) - (2,1) - (2,2) - (2,3)

You can choose to use 0-based or 1-based indexing for vertices. Also, you may output nested or flattened arrays.

Scoring & winning criterion

The standard code-golf rules apply. The shortest valid submission in bytes wins.

Example I/O

w=3, h=2

If you want to output the following graph

+-+-+
| |
+ +-+

The list-of-vertex-pairs representation will be (using 0-based indexing for example):

[(0, 1), (0, 3), (1, 2), (1, 4), (4, 5)]

or

[((0, 0), (0, 1)),
 ((0, 0), (1, 0)),
 ((0, 1), (0, 2)),
 ((0, 1), (1, 1)),
 ((1, 1), (1, 2))]

w=1, h=1

The graph is a single vertex with no edges, and its only spanning tree is the graph itself. Your code should output an empty list (which means no edges).

Answer 1

K (ngn/k), 8 bytes

|\'2'+!:

Try it online!

this is a composition equivalent to the lambda {|\'2'+!x}. the trailing : forces ! (and therefore the whole composition) to be monadic.

 !2 3         /odometer
(0 0 0 1 1 1
 0 1 2 0 1 2)
 +!2 3        /flip
(0 0
 0 1
 0 2
 1 0
 1 1
 1 2)
 2'+!2 3      /pairs (sliding window size 2)
((0 0;0 1)
 (0 1;0 2)
 (0 2;1 0)
 (1 0;1 1)
 (1 1;1 2))
 |\'2'+!2 3   /cumulative(\) max(|) each(')
((0 0;0 1)
 (0 1;0 2)
 (0 2;1 2)
 (1 0;1 1)
 (1 1;1 2))

Answer 2

Python 2, 46 bytes

lambda w,h:zip(R(w-1)+R(w*h),R(1,w*h))
R=range

Try it online!

49 bytes

lambda w,h:[(i-w**(i>=w),i)for i in range(1,w*h)]

Try it online!

Both of these produce a list corresponding to a spanning tree like this (for w=4, h=3):

0--1--2--3
|  |  |  |
4  5  6  7
|  |  |  |
8  9  10 11

Answer 3

APL (Dyalog Extended), 12 bytes^SBCS

Full program. Prompts for [h,w] from stdin. Prints pairs of [y,x] coordinates.

2⍮/,↑⊢∘⌽\↓⍳⎕

Try it online!

⎕ prompt for numeric input from the console

⍳ an array of those dimensions containing the ɩndices of an array of those dimensions

↓ split into list of rows

⊢∘⌽\ boustrophedonise

↑ combine rows into matrix

, ravel matrix into list

2⍮/ adjacent pairs (lit. for every overlapping run of 2 elements, juxtapose the 2 elements)

Answer 4

05AB1E, 12 10 bytes

*L©¹<L쮦ø

-2 bytes by porting @xnor's Python 2 answer, but is 1-based instead. So it will output the graph in this format (i.e. w=5, h=3):

1--2--3--4--5
|  |  |  |  |
6  7  8  9  10
|  |  |  |  |
11 12 13 14 15

Try it online.

Explanation:

*           # Multiply the (implicit) width and height inputs with each other
 L          # Create a list in the range [1,w*h]
  ©         # Store this list in variable `®` (without popping)
   ¹<       # Push the width-input again, and decrease it by 1
     L      # Create a list in the range [1,w-1]
      ì     # Prepend it in front of the earlier list
       ®    # Push the list [1,w*h] from variable `®` again,
        ¦   # and remove the 1 to make it the range [2,w*h]
         ø  # Zip/transpose to create pairs of the two lists
            # (after which this list of pairs is output implicitly as result)

---

Original 12 bytes answer:

*LIä2Å€R}˜ü‚

1-based. Will output the graph in this format (i.e. w=5, h=3):

1--2--3--4--5
|
6--7--8--9--10
            |
11-12-13-14-15

Try it online.

Explanation:

*             # Multiply the (implicit) width and height inputs with each other
 L            # Create a list in the range [1,w*h]
  Iä          # Split it into the height-input amount of equal-length parts
    2Å€ }     # Apply to every 2nd (index % 2 == 0) item:
       R      #  Reverse the inner list
         ˜    # Then flatten it to a single list of integers again
          ü   # Apply to each overlapping pair of values:
           ‚  #  Pair them together
              # (after which this list of pairs is output implicitly as result)

Answer 5

R, 42 bytes

function(w,h)cbind(a<-1:(h*w-1),a+w^!a%%w)

Try it online!

Creates the spanning graph

1-2-3
    |
4-5-6
    |
7-8-9

Node i is connected to node i+1 in general, or to node i+w if i is a multiple of w. This corresponds to a connecting node i to node i+w^d where d=1 if i is a multiple of w, and d=0 otherwise.

Answer 6

APL (Dyalog Extended), 9 bytes

⌈\¨2⍮/,⍤⍳

Try it online!

Adám's golfing of my algorithm

Answer 7

Ruby, 44 41 bytes

^{crossed out 44 is still 44}

->w,h{(1...w*h).map{|x|[x,x+=x%w<1?w:1]}}

Try it online!

1-based solution

Answer 8

JavaScript (V8), 68 bytes

Takes input as (w)(h). Prints pairs of 0-based numbered vertices.

w=>g=(h,n=0,p=n)=>((n/w&1?n--:++n)%w?n:n=p+w)<w*h&&g(h,n,print(p,n))

Try it online!

Recursively creates the following pattern (here with \$w=4\$):

 0→ 1→ 2→ 3
          ↓
 4← 5← 6← 7
 ↓
 8→ 9→10→11
          ↓
   … ←14←15

Answer 9

Jelly, 9 bytes

×ḶsUÐeFṡ2

Explanation:

×ḶsUÐeFṡ2 the main and only link, takes the dimensions as input
×         multiply the dimensions
 Ḷ        create the range of 0..h*w-1
  s       split into chunks of length w, I have no idea how does this part refer to w
    Ðe    at even indices
   U      reverse the chunks
      F   flatten
       ṡ2 split in overlapping slices of length 2 (path -> edge list)

The tree is actually a snake-like path:

01234
98765
ABCDE

Try it online!

Answer 10

Charcoal, 22 bytes

ＮθＮηＦ×θη¿ιＩ⟦⎇﹪ιθ⊖ι⁻ιθι

Try it online! Link is to verbose version of code. Outputs using the following format:

0-1
|
2-3
|
4-5

Alternative solution, also 22 bytes:

ＮθＮηＦ×θη¿ιＩ⟦⎇‹ιθ⊖ι⁻ιθι

Try it online! Link is to verbose version of code. Outputs using the following format:

0-1
| |
2 3
| |
4 5

Bonus version:

ＮθＦＮＦθ«Ｊ⊗κ⊗ι¿∧κ∨¬ι‽←+-↑✂+|⁰⊕ι

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

Answer 11

Rockstar, 215 bytes

g takes w,h
let j be 0
while j is less than h
let i be 0
while i is less than w
let c be j*w+i
let p be c-1
if i is 0
let p be c-w

if p is as high as 0    
say "("+p+"-"+c+")"

build i up

build j up

It can be invoked like

g taking 3,2

with the output as

(0-1)
(1-2)
(0-3)
(3-4)
(4-5)

you can also try it online!