13
\$\begingroup\$

Significantly harder version of Spanning tree of a rectangular grid.

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 a randomly generated spanning tree of the grid graph which has w vertices horizontally and h vertices vertically. Your program/function should be able to generate every possible spanning tree with nonzero probability.

One possible algorithm to solve this task is random minimum spanning tree, which calculates the minimum spanning tree of the given graph with randomized edge weights.

Input and output

The input is two positive integers w and h.

The output is a representation of a spanning tree. You can choose any representation that can describe such a graph without ambiguity, which includes (but is not limited to):

  • ASCII-formatted grid
  • A standard graph structure, e.g. adjacency matrix, adjacency list, incidence matrix...
  • A list of pairs of numbered vertices

Please specify the output format in your submission.

Scoring & winning criterion

The standard rules apply. The shortest valid submission in bytes wins.

Example I/O

w=3, h=2

  • ASCII grid
+-+-+
| |
+ +-+
  • Adjacency matrix
0 1 0 1 0 0
1 0 1 0 1 0
0 1 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0
  • List-of-vertex-pairs representation
[(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.

\$\endgroup\$
  • \$\begingroup\$ See my answer; are complex number coordinates to distinguish vertices allowed? \$\endgroup\$ – Value Ink Dec 30 '19 at 8:00
  • \$\begingroup\$ @ValueInk Yes, it's allowed. \$\endgroup\$ – Bubbler Dec 30 '19 at 8:12
  • 1
    \$\begingroup\$ As the challenge stands now, I could generate graphs randomly, check if the current graph is a spanning tree, else repeat. The program will have random running time (usually very large), but will finish with probability 1. You may want to rule that out (not sure how). Or is that acceptable? \$\endgroup\$ – Luis Mendo Dec 30 '19 at 13:21
  • 1
    \$\begingroup\$ @LuisMendo I was about to go write an algorithm doing exactly like that to make a point... BogoSpanningTree \$\endgroup\$ – FlipTack Dec 30 '19 at 17:38
  • 1
    \$\begingroup\$ @LuisMendo I have no problem with such a solution (though the challenge was indeed inspired from the "minimum random spanning tree" Wikipedia article). \$\endgroup\$ – Bubbler Dec 31 '19 at 5:25

10 Answers 10

5
\$\begingroup\$

Wolfram Language (Mathematica), 146 bytes

Block[{c,g=GridGraph@{##}},Graph[Range[1##],Join@@Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g,c@#=#]}]&@1][[2]],Options@g]]&

Try it online!

Based on my answer to the question Maze Generation.

Returns a Graph object.

For example, w = 20, h = 20 gives:

enter image description here

| improve this answer | |
\$\endgroup\$
5
+100
\$\begingroup\$

Python 2, 134 bytes

from random import*
w,h=input();w+=1
t={1}
while 1:z=choice([{a,b}for a in t for b in{a-1,a+1,a-w,a+w}-t if b%w>0<b<w*h]);print z;t|=z

Try it online!

A small improvement over xnor's answer by using row size w+1 instead of w and not using the zeroth column. For example, the following coordinates are used for the input 3,2:

1-2-3
| | |
5-6-7
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Bountied! I'll keep it up for the 7 days to give you more views. \$\endgroup\$ – xnor Mar 25 at 4:12
3
\$\begingroup\$

Ruby, 159 bytes

->w,h{c=(v=[*1..w].product [*1..h]).product;((f,(a,b)),(g,(d,e))=c.shuffle.map{|z|[z,z.sample]};(c=c-[f,g]+[f+g];p(a,b,d,e))if(a-d).abs+(b-e).abs<2)while c[1]}

Try it online!

Uses simple Kruskal's algorithm with a few pessimizations (no union-find, inefficient - and non-uniform! - sampling of the purely virtual edge list, returns via stdout), at a byte cost relatively close to Value Ink's Prim implementation.

Prints each edge as a set of four lines; if you want something slightly more sensible, replace p(a,b,d,e) with p [a,b,d,e] at the cost of one byte.

Unsqueezed version:

->w, h{
 v=[*1..w].product [*1..h]
 c=v.product
 while c.size > 1
  (f, (a, b)), (g, (d, e)) = c.shuffle.map{|z| [z, z.sample]}
  if (a-d).abs + (b-e).abs < 2
   c = c - [f, g] + [f + g]
   p [a,b,d,e]
  end
 end
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The algorithm I used has a name?? Also you should add a TIO link \$\endgroup\$ – Value Ink Dec 30 '19 at 22:59
  • 3
    \$\begingroup\$ +1 for the word "pessimization". \$\endgroup\$ – Bubbler Dec 30 '19 at 23:01
  • \$\begingroup\$ @ValueInk there are two different ways [Prim's algorithm}(en.wikipedia.org/wiki/Prim%27s_algorithm) can be turned into a maze generator algorithm. If you randomize edges once at the beginning, it returns the same distribution as Kruskal's algorithm. If you pick a random edge at each step, you get a markedly different type of maze, that prefers paths towards the origin \$\endgroup\$ – John Dvorak Dec 30 '19 at 23:13
2
\$\begingroup\$

Jelly, 28 bytes

,þ;Z$ṡ€2ẎẊḣ1;ẎḟL’ɗÐḟ@ḣ1ʋ¥ƬƊṪ

Try it online!

A dyadic link taking the width and height as its arguments and returning a list of pairs of vertices indicating the edges of the random minimum spanning tree. Based on Prim’s algorithm with the edge costs randomised.

Explanation

,þ                           | Outer table using pair function
    $                        | Following as a monad:
  ;                          | - Concatenate to:
   Z                         | - Transposed table
     ṡ€2                     | Split each into overlapping lists of length 2
        Ẏ                    | Join outer lists
         Ẋ                   | Randomise order
                          Ɗ  | Following as a monad:
          ḣ1                 | - First list item (still in a list)
                        ¥Ƭ   | - Repeat following as a dyad, collecting up results, until no new result seen (will have the randomised list of vertex pairs as its right argument)
            ;          ʋ     | - Concatenate to the following as a dyad:
             Ẏ               |   - Join outer lists (making list of vertices seen so far)
                 ɗÐḟ@        |   - Keep only items from the randomised list of edges where the following is false:
              ḟ              |     - Filter out the vertices already used
               L             |     - Length
                ’            |     - Decrement by 1
                     ḣ1      |   - First list item (still in a list)
                           Ṫ | Final iteration of the above
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 2, 136 bytes

from random import*
w,h=input()
t={0}
while 1:z=choice([{a,b}for a in t for b in{a-~a%w/~w,a+a%w/~w,a-w,a+w}-t if-1<b<w*h]);print z;t|=z

Try it online!

Prints edges as two-element set of vertices given by single-number index, terminating with error. The strategy is to to build up the set of vertices t in the tree until it contains the whole rectangle rectangle. At each step, we add an edge to the spanning tree consisting of a vertex in t and one of its neighbors that's not in t, and we add the new vertex to t. We search for neighbors by adding one of {1,-1,w,-w} to the 1D index with some trickery to avoid unwanted wraparounds, and checking that the result lies within the bounds of the rectangle.


Python 2, 142 bytes

from random import*
w,h=input()
t={0}
while 1:z=choice([{a,b}for a in{k/w+k%w*1jfor k in range(w*h)}-t for b in t if(a-b)**4==1]);print z;t|=z

Try it online!

Prints edges as two-element sets of complex numbers, terminating with error.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Ruby, 185 164 bytes

A huge mess. Outputs a vertex-pair list, where vertex coordinates are complex numbers in the form x+yi.

Long story short, it takes all vertices that have already been chosen, randomly picks a neighbor that has not been picked before, and attaches it to the graph, then repeats the process until all vertices have been chosen.

  • -4 bytes by optimizing r>=0&&i>=0 to r|i>=0 -- If either number is negative, the bit-or will ensure that the combined result is negative.
  • -17 bytes by realizing my filter function in the second neighbor check could be switched to a simple set intersection...
->w,h,*e{*v=q=0i;d=1,-1,1i,-1i
(q=v.flat_map{|x|d.map{|c|x+c}.select{|e|r,i=e.rect;r|i>=0&&r<w&&i<h}-v}.sample
(v<<q;e<<[(d.map{|c|q+c}&v).sample,q])if q)while q;e}

Try it online!

Explanation

->w,h,*e{                                       # Proc taking 2 arguments, e=[]
         *v=q=0i;                               # Add first vertex 0+0i to list
                 d=1,-1,1i,-1i                  # Save 4 cardinal directions
(                                     )while q  # While there is a valid neighbor:
 q=                                             # Set next vertex to:
   v.flat_map{|x|d.map{|c|x+c}                  # Get all neighbors to used vertices
      .select{|e|                               # Filter neighbors by:
                 r,i=e.rect                     # Get real/imaginary components
                 r|i>=0&&r<w&&i<h               # Vertex coordinates are in-bounds
             }
      -v                                        # Filter already-used vertices
    }.sample                                    # Pick a random valid neighbor
 (                                   )if q      # If a neighbor was found:
  v<<q                                          # Add it to the vertex list
  e<<[                                          # Add an edge to the edge list.
      (                                         # First vertex of edge is:
       d.map{|c|q+c}                            # Get vertex neighbors
       &v                                       # Intersect w/ used vertices
      ).sample                                  # Pick one by random
      ,q]                                       # Second vertex of edge is neighbor
                                                # (end while)
e                                               # Return the edge list
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 62 bytes

{e@&~~':i{@[x;&|/x=/:y;:;&/x y]}\e:0N?,/(2''m),+'2'm:x#i:!*/x}

Try it online!

arg: w,h pair. result: list of vertex pairs.

i:!*/x create the list 0 .. (w*h)-1 and assign to i

m:x# reshape to a w-by-h matrix m

2' pairs of neighbouring rows

+' transpose each (make them rows of pairs)

( ), prepend

2''m pairs of neighbouring cells in each row

,/ concat into a single list

e:0N? shuffle and assign to e for "edges"

i{ }\ scan the edges with the function in { } and a starting value i. the left arg will map vertices to their "tree ids" in the forest. initially the vertex ids and tree ids coincide.

@[x;&|/x=/:y;:;&/x y] amend the current forest by merging the tree(s) corresponding to the ends of the new edge

~': which forests match the previous ones? boolean list

e@&~ select from e where not

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 77 63 bytes

NθNηJ⊗‽θ⊗‽ηP+  ¦+W‹№KA+×θη«J⊗‽θ⊗‽η¿¬℅KK«≔⌕AKV ι¿ι«P+  P✳⁻χ⊗‽ι²+

Try it online! Link is to verbose version of code. Outputs a whitespace-bordered ASCII grid. Explanation:

NθNη

Input the width and height.

J⊗‽θ⊗‽ηP+  ¦+

Jump to a random position and mark it with a + surrounded with spaces. (Unfortunately Charcoal's Multiprint operator special-cases a leading + so I have to output the + separately.)

W‹№KA+×θη«

Repeat until w*h +s have been output.

J⊗‽θ⊗‽η

Jump to a random position.

¿¬℅KK«

If the position is vacant,

≔⌕AKV ι

find any neighbouring spaces,

¿ι«

and if there is at least one, then

P+  P✳⁻χ⊗‽ι²+

surround the current position with spaces, draw a - or | in a random matching direction, and finally draw a + in the current position.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6),  151 147 145  143 bytes

Takes input as (width)(height). Returns a list of pairs of numbered vertices.

w=>g=h=>(m=1,n=a=[],F=v=>[++v%w&&v,--v%w&&v-1,v+w,v-w].map(V=>V<0|V/w/h|m>>V&1|Math.random()<.5||F(V,m|=1<<V,n=a.push([v,V]))))``|~n+w*h?g(h):a

Try it online!

Commented

w =>                        // w = width
g = h => (                  // h = height
  m = 1,                    // m = bitmask of visited vertices
  n =                       // n = number of visited vertices - 1
  a = [],                   // a[] = pairs of connected vertices
  F = v =>                  // F is a recursive function, taking the current vertex v
    [ ++v % w && v,         //   try v + 1 if (v + 1) mod w is not equal to 0
                            //   we temporarily increment v to coerce it to a number
      --v % w && v - 1,     //   decrement v; try v - 1 if v mod w is not equal to 0
      v + w,                //   unconditionally try v + w
      v - w                 //   unconditionally try v - w 
    ].map(V =>              //   for each new vertex V:
      V < 0 |               //     abort if V is negative
      V / w / h |           //     abort if V is greater than or equal to w * h
      m >> V & 1 |          //     abort if V was already visited
      Math.random() < .5 || //     abort with 50% probability
      F(                    //     otherwise, do a recursive call:
        V,                  //       using the new vertex
        m |= 1 << V,        //       update the bitmask of visited vertices
        n = a.push([v, V])  //       append [v, V] to a[] and update n
      )                     //     end of recursive call
    )                       //   end of map()
)`` |                       // initial call to F with v = [''] (zero'ish)
~n + w * h ?                // if n is not equal to w * h - 1:
  g(h)                      //   try again
:                           // else:
  a                         //   success: return a[]
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

R, 156 bytes

function(w,h){b=rbind(x<-1:(s=w*h),c(x+1,1:(s-h)+h))[,1:w*-h][,sample(s+s-h-w)]
y=b[,1]
while(!all(z<-matrix(b%in%y,2)))y=rbind(y,b[,colSums(z)==1][1:2])
y}

Try it online!

A function taking the width and height and returning a two-matrix of 1-indexed pairs of points (numbered from top left, moving down and then right). The footer also prints an ASCII representation. Implements Prim’s algorithm.

| improve this answer | |
\$\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.