Biorąc pod uwagę 2 liczby całkowite reprezentujące rozmiar pola xi ywyprowadzamy ścieżkę przez pole.

Przykładowe dane wyjściowe dla 5, 4:

#    
#    
# ###
### #

Całe pole ma wymiary 5 na 4, a ścieżka składa się z krzyżyków przecinających pole.

Ścieżka powinna zawsze zaczynać się w lewym górnym rogu i przechodzić do prawego dolnego rogu. Cała ścieżka powinna być losowa przy każdym uruchomieniu programu. Każda poprawna ścieżka powinna być możliwym wyjściem.

Reguły dla ścieżek są następujące:

• Wykonane z hashmarków

• Każdy skrót jest połączony tylko z 2 innymi skrótami (tzn. Ścieżka nie przecina się ani nie biegnie obok siebie)

Nie-hash spacje mogą być wypełnione dowolnym innym znakiem, ale muszą być spójne (tj. Wszystkie spacje, wszystkie kropki itp.)

Przykłady:

2, 2

##
 #

3, 4

##
 ##
  #
  #

5, 5

#####
    #
    #
    #
    #

6, 5

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

7, 9

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

Ten rodzaj ścieżki jest podobny do unikającego się losowego marszu, jednak nie może przylegać do siebie w przeciwieństwie do prawdziwej SAW.

Ciągłość ścieżki i dotykanie ścieżki są zdefiniowane bez przekątnych.

MATLAB, 316 305 300 293 bajtów

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,'']

Dzięki @LuisMendo za różne sugestie i kilka bajtów =)

Wypróbuj online! (Bez gwarancji: Należy pamiętać, że trzeba było wprowadzić kilka poprawek, aby działało ono w systemie Octave: po pierwsze musiałem usunąć functionsłowo kluczowe i zakodować wartości, po drugie: spacje nie są drukowane poprawnie, jak w Matlabie. Również nie sprawdź polecenia splotu Octave, które mogą działać inaczej.)

Przykładowe dane wyjściowe dla danych wejściowych (7,10)(może to już potrwać dość długo):

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

Wyjaśnienie

To generuje ścieżki sekwencyjnie od górnego lewego do dolnego prawego z pożądaną 4-łącznością, a następnie wykorzystuje próbkowanie odrzucania, aby odrzucić ścieżki, które naruszają kryterium, że nie można mieć sąsiednich części.

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,''];

No i jak zawsze:

Konwolucja jest kluczem do sukcesu.

Befunge, 344 bajty

&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-+!#^_

Wypróbuj online!

Jak wspomniano @flawr w odpowiedzi MATLAB, może to trochę potrwać, jeśli rozmiar pola ma dowolny nietrywialny rozmiar. W rzeczywistości dość łatwo jest wpaść w sytuację, w której naprawdę nie warto czekać na jej zakończenie, ponieważ prawdopodobnie czekasz do końca czasu.

Aby zrozumieć, dlaczego tak się dzieje, pomocne jest wyświetlenie programu uruchamianego w jednym z wielu „wizualnych debuggerów” Befunge. Ponieważ dane i kod są takie same w Befunge, będziesz mógł zobaczyć ścieżkę, która zmienia się w czasie. Na przykład, tutaj jest krótka animacja pokazująca, jak może wyglądać część biegu na wolnej ścieżce.

Gdy algorytm zdecyduje się wykonać ten fatalny zwrot w lewo u dołu granicy pola, zasadniczo skazał się na całe życie bezcelowej wędrówki. Od tego momentu musi podążać każdą możliwą ścieżką na tym odgrodzonym terenie, zanim będzie mógł się wycofać i spróbować skręcić w prawo. A liczba potencjalnych ścieżek w tych przypadkach może łatwo stać się astronomiczna.

Konkluzja: Jeśli wydaje się, że zajmuje to dużo czasu, prawdopodobnie dobrym pomysłem jest po prostu przerwać wykonywanie i zacząć od nowa.

Wyjaśnienie

Jest to w zasadzie algorytm rekurencyjny, wypróbowujący każdą możliwą ścieżkę przez pole, a następnie odwijający kroki, które zostały już wykonane, gdy tylko utknie. Ponieważ Befunge nie ma pojęcia funkcji, funkcja rekurencyjna nie wchodzi w rachubę, ale możemy naśladować ten proces, śledząc stan na stosie.

Działa to poprzez wypełnienie stosu potencjalnymi współrzędnymi, które możemy chcieć śledzić. Następnie wyciągamy jeden zestaw ze stosu i sprawdzamy, czy jest on odpowiedni (tj. W zasięgu i nie pokrywa się z istniejącą ścieżką). Kiedy już znajdziemy dobre miejsce, zapisujemy #na polu gry w tej lokalizacji i dodajemy te szczegóły do ​​stosu, na wypadek, gdybyśmy musieli później wrócić.

Następnie wypychamy dodatkowe cztery zestawy współrzędnych na stos (w losowej kolejności), wskazując potencjalne ścieżki, które możemy wziąć z tej nowej lokalizacji, i przeskakujemy z powrotem na początek pętli. Jeśli żadna z potencjalnych ścieżek nie jest wykonalna, przejdziemy do punktu na stosie, w którym zapisaliśmy lokalizację, #którą wypisaliśmy, więc cofniemy ten krok i będziemy kontynuować próbę potencjalnych współrzędnych z poprzedniego kroku.

Oto jak wygląda kod z wyróżnionymi różnymi częściami komponentu:

Odczytaj szerokość i wysokość pola i popchnij współrzędne początkowe wraz ze 0znacznikiem typu, aby wskazać potencjalną ścieżkę, a nie lokalizację cofania.
Sprawdź lokalizacje cofania (wskazane przez 1znacznik typu), które są cofane za pomocą prostej pkomendy, ponieważ są przechowywane w dokładnie takim formacie, jaki jest potrzebny do zapisania miejsca z powrotem na polu gry.
Sprawdź, czy współrzędne nadal znajdują się na polu gry. Jeśli są poza zasięgiem, upuść je ze stosu i zapętl z powrotem, aby wypróbować następne potencjalne współrzędne.
Jeśli są w zasięgu, pobierz dwie kolejne wartości ze stosu, czyli lokalizacji z poprzedniego kroku (wymagane w teście, który następuje po tym).
Sprawdź, czy współrzędne mają zetknąć się z istniejącym segmentem ścieżki. Lokalizacja poprzedniego kroku jest oczywiście ignorowana podczas tej kontroli.
Jeśli wszystkie testy zakończą się pomyślnie, napisz #na pole gry i sprawdź, czy dotarliśmy do miejsca docelowego.
Jeśli tak, napisz ostatnią ścieżkę i wyjdź.
W przeciwnym razie zapisz współrzędne na stosie ze 1znacznikiem typu do późniejszego cofnięcia.
Jest to przerywane obliczaniem liczb losowych, które wkrótce będziemy potrzebować.
Wciśnij cztery potencjalne miejsca docelowe, do których można dotrzeć z bieżącej lokalizacji. Liczba losowa określa kolejność ich wypychania, a tym samym kolejność, w jakiej będą przestrzegane.
Zawiń z powrotem na początek głównej pętli i przetwarzaj kolejne wartości na stosie.

QBasic, 259 bajtów

Na pewno kocham 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
?"#"

Podstawowa strategia: na każdym kroku drukuj a #do bieżącej lokalizacji i poruszaj się w losowym kierunku. Tablica azer i jedynek śledzi, gdzie byliśmy. Jeśli ruch jest legalny i zabiera nas do punktu końcowego, GOTO 9należy wyjść z pętli i wydrukować końcowy #. W przeciwnym razie, jeśli ruch jest legalny, zrób kolejny krok. W przeciwnym razie wyczyść ekran i zacznij od nowa (znacznie bardziej golfista niż kodowanie algorytmu cofania!).

Testowany na moim laptopie w QB64, generalnie daje wynik 9, 9w ciągu pięciu sekund lub krócej. Trasy 10, 10trwały od trzech do 45 sekund. Teoretycznie wszystkie legalne ścieżki mają niezerowe prawdopodobieństwo, ale prawdopodobieństwo ścieżki o dużych krzywych jest znikomo małe. Od czasu do czasu widziałem ścieżki z jedną lub dwiema małymi krzywymi:

Wersja bez golfa i / lub szczegółowe wyjaśnienia dostępne na żądanie.

R, 225 bajtów

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="")}

Wyjaśnienie:

Generujemy zwykły (kratowy) [x * y] niekierowany wykres z losowymi ciężarami na krawędziach, a następnie znajdujemy najkrótszą ścieżkę od początku do końca. Jednak w wygenerowanej ścieżce mogą znajdować się komórki, które mają na przykład więcej niż dwóch sąsiadów:

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

Powinniśmy więc zastosować algorytm najkrótszej ścieżki dwa razy. Za drugim razem ustawiamy wszystkie wagi na 1, z wyjątkiem tych, które znajdują się w bieżącej znalezionej ścieżce, która jest ustawiona na 0;

wynik

#
#
### 
  # 
  #
  ###

Nie golfowany:

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="")
}

JavaScript (ES7), 333 331 330 329 324 318 312 bajtów

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>

Objaśnienie: #s są losowo umieszczane w tablicy, dopóki ścieżka nie zostanie znaleziona w polu za pomocą wyszukiwania szerokości pierwszego; pierwsza, a zatem najkrótsza, taka ścieżka jest następnie wyprowadzana; gwarantuje to, że ścieżka się nie przecina. Zauważ, że szczególnie w przypadku większych pól możliwe jest przekroczenie stosu silnika JS przed znalezieniem ścieżki. Nie golfowany:

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');
}