Дано 2 целочисленных ввода, представляющих размер поля, xи yвыведите путь через поле.

Пример вывода для 5, 4:

#    
#    
# ###
### #

Все поле 5 на 4, и есть путь, состоящий из хеш-меток, пересекающих поле.

Путь должен всегда начинаться в верхнем левом углу и идти внизу справа. Весь путь должен быть рандомизирован каждый раз при запуске программы. Каждый допустимый путь должен быть возможным выходом.

Правила для путей:

• Сделано из hashmarks

• Каждый хеш связан только с 2 другими хешами (т. Е. Путь не пересекается и не проходит рядом с самим собой)

Нехэш-пробелы могут быть заполнены любым другим символом, но он должен быть согласованным (т. Е. Все пробелы, все точки и т. Д.)

Примеры:

2, 2

##
 #

3, 4

##
 ##
  #
  #

5, 5

#####
    #
    #
    #
    #

6, 5

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

7, 9

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

Этот тип пути похож на случайную прогулку, избегающую себя, однако он не может быть смежным с самим собой, в отличие от настоящего ПИЛА.

Непрерывность пути и касание пути определены без диагоналей.

MATLAB, 316 305 300 293 байта

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

Спасибо @LuisMendo за различные предложения и кучу байтов =)

Попробуйте онлайн! (Без гарантии: обратите внимание, что для его запуска в Octave потребовалось несколько настроек: во-первых, мне нужно было удалить functionключевое слово и жестко закодировать значения, во-вторых: пробелы не выводятся правильно, как в Matlab. Также я этого не делал проверьте команды свертки Octave, которые могут действовать по-другому.)

Пример вывода для ввода (7,10)(это может занять довольно много времени):

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

объяснение

Это генерирует пути последовательно от верхнего левого до нижнего правого с желаемой 4-связностью, а затем использует выборку отклонения, чтобы отклонить пути, которые действительно нарушают критерий, что у вас не может быть прилегающих частей.

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

Ну и как всегда

Свертка - ключ к успеху.

Befunge, 344 байта

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

Попробуйте онлайн!

Как упомянул @flawr в своем ответе на MATLAB, это может занять некоторое время, если размер поля любого нетривиального размера. На самом деле, довольно легко попасть в ситуацию, когда действительно не стоит пытаться дождаться его окончания, потому что вы, скорее всего, будете ждать до конца времени.

Чтобы понять, почему это происходит, полезно посмотреть, как выполняется программа, в одном из многочисленных «визуальных отладчиков» Befunge. Поскольку в Befunge данные и код - это одно и то же, вы увидите путь, который меняется с течением времени. Например, вот короткая анимация, показывающая, как может выглядеть часть бега по медленному пути.

Как только алгоритм решает совершить этот роковой поворот налево в нижней части границы поля, он по существу обрекает себя на целую жизнь бесцельного блуждания. С этого момента он должен пройти каждый возможный путь в этой огороженной области, прежде чем он сможет отступить и попытаться повернуть направо. И количество потенциальных путей в этих случаях может легко стать астрономическим.

Итог: если кажется, что это занимает много времени, возможно, хорошей идеей будет просто прервать выполнение и начать заново.

объяснение

Это в основном рекурсивный алгоритм, который пробует все возможные пути через поле, а затем раскручивает шаги, которые уже выполнялись, когда он застревал. Поскольку у Befunge нет понятия функций, о рекурсивной функции не может быть и речи, но мы можем эмулировать процесс, отслеживая состояние в стеке.

Это работает, заполняя стек потенциальными координатами, которым мы можем следовать. Затем мы извлекаем один набор из стека и проверяем, подходит ли он (то есть в диапазоне и не перекрывается ли существующий путь). Как только у нас будет подходящее место, мы записываем #в игровое поле в этом месте и добавляем эти детали в стек на случай, если нам понадобится вернуться позже.

Затем мы помещаем дополнительные четыре набора координат в стек (в случайном порядке), указывая потенциальные пути, которые мы можем взять из этого нового местоположения, и возвращаемся к началу цикла. Если ни один из возможных путей не выполним, мы дойдем до той точки в стеке, где мы сохранили местоположение записанного #нами, поэтому мы отменим этот шаг и продолжим пробовать потенциальные координаты с одного предыдущего шага.

Вот как выглядит код с выделенными различными компонентами:

Прочитайте ширину и высоту поля и нажмите начальные координаты вместе с 0маркером типа, чтобы указать потенциальный путь, а не место возврата.
Проверьте места обратного отслеживания (обозначенные 1маркером типа), которые возвращаются с помощью простой pкоманды, поскольку они хранятся в точном формате, необходимом для записи пробела обратно в игровое поле.
Проверьте, находятся ли координаты внутри игрового поля. Если они находятся за пределами диапазона, отбросьте их из стека и вернитесь назад, чтобы попробовать следующие потенциальные координаты.
Если они находятся в диапазоне, получите следующие два значения из стека, который является местоположением предыдущего шага (требуется в следующем тесте).
Проверьте, вступят ли координаты в контакт с существующим сегментом пути. Местоположение предыдущего шага, очевидно, игнорируется этой проверкой.
Если все тесты пройдены успешно, напишите #в игровое поле и проверьте, достигли ли мы места назначения.
Если у нас есть, запишите окончательный путь и выйдите.
В противном случае сохраните координаты в стек с 1маркером типа для последующего возврата.
Это прерывается вычислением случайного числа, которое нам скоро понадобится.
Нажмите четыре потенциальных места назначения, которые могут быть достигнуты из текущего местоположения. Случайное число определяет порядок, в котором они выдвигаются, и, следовательно, порядок их следования.
Вернитесь к началу основного цикла и обработайте следующие значения в стеке.

QBasic, 259 байт

Я уверен, что люблю GOTOс.

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
?"#"

Основная стратегия: на каждом шаге выведите a #в текущее местоположение и двигайтесь в произвольном направлении. Массив a0 и 1 отслеживает, где мы были. Если движение допустимо и приводит нас к конечной точке, GOTO 9чтобы выйти из цикла и вывести финал #. Иначе, если ход законен, сделайте еще один шаг. Иначе, очистите экран и начните все сначала (гораздо сложнее, чем кодировать алгоритм возврата!).

Протестировано на моем ноутбуке в QB64, это обычно дает результат в течение 9, 9пяти секунд или меньше. Пробеги 10, 10заняли где-то от трех до 45 секунд. Теоретически, все допустимые пути имеют ненулевую вероятность, но вероятность пути с большими кривыми исчезающе мала. Я иногда видел пути с одной или двумя маленькими кривыми, хотя:

Необработанная версия и / или подробное объяснение доступны по запросу.

R 225 байт

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

Объяснение:

Мы генерируем регулярный (решетчатый) [x * y] неориентированный граф со случайными весами на ребрах, затем находим кратчайший путь от начала до конца. Однако в сгенерированном пути могут быть ячейки, которые имеют более двух соседей, например:

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

Таким образом, мы должны применить алгоритм кратчайшего пути два раза. Во второй раз мы устанавливаем все веса в 1, кроме тех, которые находятся в текущем найденном пути, которые установлены в 0;

результат

#
#
### 
  # 
  #
  ###

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

JavaScript (ES7), 333 331 330 329 324 318 312 байт

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>

Расширение: #s случайно помещаются в массив, пока путь не будет найден через поле с использованием поиска в ширину; первый и, следовательно, самый короткий, такой путь затем выводится; это гарантирует, что путь не пересекает себя. Обратите внимание, что, в частности, для больших полей возможно превышение стека механизма JS, прежде чем будет найден путь. 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');
}