14
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Does rule anything prevent us from always zig-zagging through the array? E.g. 0 → 1 → 2 → 3 ↓ 7 ← 6 ← 5 ← 4 ↓ 8 → 9 → 10 → 11 \$\endgroup\$ – Adám Nov 7 at 2:33
  • \$\begingroup\$ @Adam It doesn't, as far as I see. You can also simply use, for example, a vertical line combined with many horizontal ones. \$\endgroup\$ – my pronoun is monicareinstate Nov 7 at 2:54
  • \$\begingroup\$ Can we input h and w in unary? Can we input them as a grid made of a specific character? \$\endgroup\$ – my pronoun is monicareinstate Nov 7 at 4:30
  • \$\begingroup\$ @someone Unary: yes, but only if it's the most natural representation of a positive integer in your language of choice. Grid input: no. \$\endgroup\$ – Bubbler Nov 7 at 4:34

11 Answers 11

6
\$\begingroup\$

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))
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Extended), 12 bytesSBCS

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)

\$\endgroup\$
  • \$\begingroup\$ ⌈\¨2,/⊂¨,⍳⎕ is 11. i believe you can shorten it even more with your extensions. \$\endgroup\$ – ngn Nov 8 at 6:55
  • \$\begingroup\$ @ngn Another clever ngn-scan! But it has no connection to my solution, and even makes a different tree. Go ahead and post ⌈\¨2⍮/,⍤⍳ in Extended. \$\endgroup\$ – Adám Nov 8 at 7:09
  • \$\begingroup\$ codegolf.stackexchange.com/questions/195408/… \$\endgroup\$ – ngn Nov 8 at 7:42
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice that this method's solution for a 3x3 traces out a 3. \$\endgroup\$ – CriminallyVulgar Nov 7 at 15:07
2
\$\begingroup\$

APL (Dyalog Extended), 9 bytes

⌈\¨2⍮/,⍤⍳

Try it online!

Adám's golfing of my algorithm

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 22 bytes

NθNηF×θη¿ιI⟦⎇﹪ιθ⊖ι⁻ιθι

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:

NθNηF×θη¿ιI⟦⎇‹ιθ⊖ι⁻ιθι

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

0-1
| |
2 3
| |
4 5

Bonus version:

NθFNFθ«J⊗κ⊗ι¿∧κ∨¬ι‽←+-↑✂+|⁰⊕ι

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.