New answers tagged

0

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


2

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


5

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:


3

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


1

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


1

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


1

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


2

K (ngn/k), 60 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 ...


2

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


Top 50 recent answers are included