Generate an ascii-art non-intersecting path

Question

Given 2 integer inputs representing the size of the field, x and y, output a path through the field.

Example output for 5, 4:

#    
#    
# ###
### #

The whole field is 5 by 4, and there is a path made of hashmarks crossing the field.

The path should always start in the top left corner, and go to the bottom right. The whole path should be randomized every time the program is run. Every valid path should be a possible output.

The rules for paths are:

• Made of hashmarks

• Every hash is only connected to 2 other hashes (i.e. the path does not intersect or run alongside itself)

The non-hash spaces can be filled it with any other character, but it must be consistent (i.e. all spaces, all periods, etc.)

Examples:

2, 2

##
 #

3, 4

##
 ##
  #
  #

5, 5

#####
    #
    #
    #
    #

6, 5

## ###
 # # #
## # #
# ## #
###  #

7, 9

#######
      #
####  #
#  #  #
#  #  #
#  #  #
#  ####
#
#######

This kind of path is similar to a self-avoiding random walk, however it can't be adjacent to itself unlike a true SAW.

Path continuity and path touching are both defined without diagonals.

Answer 1

MATLAB, 316 305 300 293 bytes

function P=f(a,b);z(a,b)=0;P=z;c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');B=1;while B;P=z;P(1)=1;for K=1:a*b;S=z;S(a,b)=1;for L=2:a*b;S(~S&c(S)&~P)=L;end;[i,j]=find(S&c(P==K));if i;r=randi(nnz(i));else;break;end;P(i(r),j(r))=K+1;if P(a,b);break;end;end;B=any(any(c(P>0)>3));end;P(P>0)=35;P=[P,'']

Thanks @LuisMendo for various suggestions and a bunch of bytes=)

Try it online! (Without warranty: Note that a few adjustments were needed to get it to run on Octave: First of all I needed to remove the function keyword and hardcode the values, secondly: The spaces do not get printed correctly as in Matlab. Also I did not check the convolution commands of Octave, which might act differently.)

Example output for input (7,10) (can already take quite a while):

#         
#         
##        
 ##       
  #   ### 
  #   # ##
  #####  #

Explanation

This generates paths sequentially from the top left to the bottom right with the desired 4-connectivity, and then uses rejection sampling to reject paths that do violate the criterion that you cannot have adjecent parts.

function P=f(a,b);
z(a,b)=0;                                 % a matrix of zeros of the size of th efield
P=z;                                    
c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');  % our convolution function, we always convolute with the same 4-neighbourhood kernel
B=1;
while B;                                  % while we reject, we generate paths:
    P=z;
    P(1)=1;                               % P is our path, we place the first seed
    for K=1:a*b;                          % in this loop we generate the all shortest paths (flood fill) from the bottom right, withot crossing the path to see what fiels are reachable from the bottom left
        S=z;
        S(a,b)=1;                         % seed on the bottom left
        for L=2:a*b;
            S(~S&c(S)&~P)=L;              % update flood front
        end;
        [i,j]=find(S&c(P==K));            % find a neighbour of the current end of the path, that is also reachable from the bottom left
        if i;                             % if we found some choose a random one
            r=randi(nnz(i));
        else;
            break;                        % otherwise restart (might not be necessary, but I'm too tired to think about it properly=)
        end;
        P(i(r),j(r))=K+1;                 % update the end of the current path
        if P(a,b);                        % if we finished, stop continuing this path
            break;
        end;
    end;
    B=any(any(c(P>0)>3));                 % check if we actually have a valid path
end;
P(P>0)=35;                                % format the path nicely
P=[P,''];

Oh and as always:

Convolution is the key to success.

Answer 2

Befunge, 344 bytes

&v>>>#p_:63p:43g`\!+v>/*53g+\01g:2%2*1-\2/!*63g+\0\:v
 40$ v++!\`g14:p35:\<^2\-1*2%2p10::%4+g00:\g36\g35-1_v
#11^$_83p73v >1+:41g`!#v_$,1+:43g`!#v_@>->2>+00p+141^_
<p1^     vp< ^,g+7g36:<<<<1+55p36:<<<< ^1?0^#7g36g35*
8&p|!++!%9#2g+7g10\*!-g38g10!-g37:g00!!*<>3^
443>:!#v_>>1-::3%1-:53g+00p\3/1-:63g+01p^
^>^>>$#<"#"53g63g7+p41g53g-43g63g-+!#^_

Try it online!

As @flawr mentioned in their MATLAB answer, this may take some time if the field size is of any non-trivial size. In fact it's quite easy to get into a situation where it's really not worth trying to wait for it to finish, because you're quite likely to be waiting until the end of time.

To understand why this happens, it helpful to view the program as it's executing in one of Befunge's many "visual debuggers". Since data and code are the same thing in Befunge, you'll get to view the path as it changes over time. For example, here is a short animation showing what a part of a run on a slow path might look like.

Once the algorithm decides to make that fateful turn to the left at the bottom of the field boundary, it has essentially condemned itself to a lifetime of aimless wandering. From that point on it has to follow every single possible path in that fenced off area before it can back out and try the turn to the right. And the number of potential paths in these cases can easily become astronomical.

Bottom line: If it seems to be taking a long time, it's probably a good idea to just abort the execution and start again.

Explanation

This is basically a recursive algorithm, trying every possible path through the field, and then unwinding steps that have already been followed whenever it gets stuck. Since Befunge doesn't have the concept of functions, a recursive function is out of the question, but we can emulate the process by tracking the state on the stack.

This works by populating the stack with potential coordinates that we may want to follow. Then we pull one set from the stack and check whether it is suitable (i.e. in range and not overlapping with an existing path). Once we've got a good spot, we write a # into the playfield at that location, and add those details to the stack in case we need to backtrack later.

We then push an additional four sets of coordinates onto the stack (in random order) indicating the potential paths we can take from this new location, and jump back to the start of the loop. If none of the potential paths are feasible, we'll get to the point on the stack where we saved the location of the # we wrote out, so we'll undo that step and continue trying potential coordinates from one step prior.

This is what the code looks like with the various component parts highlighted:

Read the width and height of the field, and push the start coordinates along with a 0 type marker to indicate a potential path rather than a backtracking location.
Check for backtracking locations (indicated by a 1 type marker) which are reverted with a simple p command, since they're stored in the exact format needed to write a space back into the playfield.
Check if the coordinates are still inside the playfield. If they're out of range, drop them from the stack and loop back to try the next potential coordinates.
If they are in range, get the next two values from the stack, which is the location of the previous step (required in the test that follows this).
Check if the coordinates are going to come into contact with an existing segment of the path. The location of the previous step is obviously ignored from this check.
If all test are successful, write a # into the playfield, and check if we've reached the destination location.
If we have, write out the final path, and exit.
Otherwise save the coordinates onto the stack with a 1 type marker for later backtracking.
This is interrupted with a random number calculation which we're going to need soon.
Push four potential destinations that can be reached from the current location. The random number determines the order in which they're pushed and thus the order that they will be followed.
Wrap back to the start of the main loop and process the next values on the stack.

Answer 3

QBasic, 259 bytes

I sure love GOTOs.

RANDOMIZE TIMER
INPUT w,h
DO
CLS
x=1
y=1
REDIM a(w+3,h+3)
2a(x+1,y+1)=1
LOCATE y,x
?"#"
d=INT(RND*4)
m=1AND d
x=x+m*(d-2)
y=y-d*m+m+d-1
c=a(x,y+1)+a(x+2,y+1)+a(x+1,y)+a(x+1,y+2)=1
IF(x=w)*c*(y=h)GOTO 9
IF(x*y-1)*x*y*c*(x<=w)*(y<=h)GOTO 2
LOOP
9LOCATE y,x
?"#"

Basic strategy: at each step, print a # to the current location and move in a random direction. An array a of 0s and 1s keeps track of where we've been. If the move is legal and takes us to the endpoint, GOTO 9 to exit the loop and print the final #. Else, if the move is legal, take another step. Else, clear the screen and start over (much golfier than coding a backtracking algorithm!).

Tested on my laptop in QB64, this generally produces a result for 9, 9 in five seconds or less. Runs of 10, 10 have taken anywhere between three and 45 seconds. Theoretically, all legal paths have non-zero probability, but the probability of a path with large curves is vanishingly small. I have occasionally seen paths with one or two small curves, though:

Ungolfed version and/or in-depth explanation available on request.

Answer 4

R, 225 bytes

function(x,y){library(igraph);a=matrix(rep(" ",x*y),c(y,x));g=make_lattice(c(y,x));w=runif(ecount(g));for (i in 1:2){v=shortest_paths(g,1,x*y,weights=w)$vpath[[1]];w[]=1;w[E(g)[v%--%v]]=0;};a[v]="#";cat(rbind(a,"\n"),sep="")}

Explanation:

We generate a regular (lattice) [x * y] undirected graph with random weigths on edges then we find the shortest path from the start to the end. However in the generated path there may be cells that have more than two neigbors for example:

#
#
####
  ##
  #
  ###

So we should apply the shortest path algorithm two times. In the second time we set all weights to 1 except those that are in the current found path that set to 0;

result

#
#
### 
  # 
  #
  ###

Ungolfed:

function(x,y){
    library(igraph);#igraph library should be installed
    a=matrix(rep(" ",x*y),c(y,x));#ASCII representation of the graph
    g=make_lattice(c(y,x));# regular graph
    w=runif(ecount(g));#weights
    for (i in 1:2){
        #find vertices that are in the path
        v=shortest_paths(g,1,x*y,weights=w)$vpath[[1]];
        #set all weights to 1 except those that are in the current found path that set to 0
        w[]=1;
        w[E(g)[v%--%v]]=0;
    }
    a[v]="#";
    cat(rbind(a,"\n"),sep="")
}

Answer 5

JavaScript (ES7), 333 331 330 329 324 318 312 bytes

f=
(h,w,c=[...Array(h)].map(_=>Array(w).fill` `),g=a=>{for(z of b=[[[h-1,w-1]]])a.map(([x,y])=>b.every(([[i,j]])=>i-x|j-y)&(z[0][0]-x)**2+(z[0][1]-y)**2<2&&b.push([[x,y],...z]));return b.find(([[x,y]])=>!x&!y)||g([...a,[h,w].map(n=>Math.random()*n|0)])})=>g([]).map(([x,y])=>c[x][y]=`#`)&&c.map(a=>a.join``).join`
`

Height: <input type=number min=1 id=h>Width: <input type=number min=1 id=w><input type=button value="Generate!" onclick=o.textContent=f(+h.value,+w.value)><pre id=o>

Expanation: #s are randomly placed in the array until a path is found through the field using a breadth-first search; the first, and therefore shortest, such path is then output; this guarantees that the path does not intersect itself. Note that particularly for larger fields it's possible to exceed the JS engine's stack before a path is found. Ungolfed:

function r(n) {
    return Math.floor(Math.random() * n);
}
function f(h, w) {
    var a = []; // array of placed #s
    var b; // breadth-first search results
    var c;
    do {
        a.push([r(h), r(w)]); // place a # randomly
        b = [[[h - 1, w - 1]]]; // start from bottom right corner
        for (z of b) // breadth-first search
            for ([x, y] of a) // find possible next steps
                if (!b.some(([[i, j]]) => i == x && j == y))
                    if ((z[0][0] - x) ** 2 + (z[0][1] - y) ** 2 < 2)
                        if (x || y)
                            b.push([[x, y], ...z]); // add to search
                        else if (!c)
                            c = [[x, y], ...z]; // found path
    } while (!c);
    a = [...Array(h)].map(() => Array(w).fill(' '));
    for ([x, y] of c) // convert path to output
        a[x][y] = '#';
    return a.map(b => b.join('')).join('\n');
}