Создайте многоуровневый лабиринт 5х5х5 с одним решением

11

Цель этого задания - создать кратчайший код (в символах), который успешно выполняет следующие действия:

Технические характеристики :

  • Должен создать 5x5x5 labyrinthс точно 1 possible solution(не больше, не меньше)
  • Лабиринт должен быть создан randomly Должно быть в состоянии генерировать каждое существующее решение, если оно будет работать годами
  • startИ finishдолжны быть помещены в*opposite corners
  • Карта outputдолжна быть в одном из следующих форматов:

Вариант выходного формата 1 strings, printed or alerted :

xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx

Вариант формата вывода 2 arrays :

[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]

Выходные заметки:

  • Используйте 0для emptyи 1дляsquares

  • Линии разрыва НЕ нужны

  • Вы сами решаете, что к indexчему, но не забудьте объяснить это хорошо


* Вот пример того, что я имею в виду под противоположными углами:

введите описание изображения здесь

Пояснения :

  • Может НЕ двигаться вdiagonal
  • Может НЕ проходить дважды по тому же пути
  • Имея inaccessible areasразрешено
  • Вы можете go up/downболее одного уровня подряд

Подсказки:

  • Не рассматривайте их как стены, вместо этого рассматривайте их как 5x5x5стопку квадратов, которые некоторые из них отсутствуют, и вы можете пройти через пропущенные
ajax333221
источник
Если что-то неясно, просто спросите меня :)
ajax333221
3
Тем не менее, есть одна деталь, которую я хотел бы прояснить: стены расположены между квадратами или стена заполняет целый квадрат?
Ильмари Каронен
1
Вы говорите 5x5 (2D-массив) в нескольких местах, но примеры кода и изображения предлагают 5x5x5 (3D-массив). Я полагаю, что подразумевается под 3D-массивом?
Кае Веренс
1
как решено, что решение является действительным лабиринтом? Я имею в виду, это количество ответвлений, которое имеет правильный путь? это как-то связано с отношением 1 к 0?
Кае Веренс
2
Когда вы говорите: «Лабиринт должен создаваться случайно», на какие ограничения мы должны опираться? Я предполагаю, например, что вы не намерены разрешать, как буквальное прочтение правил в настоящее время, программу, которая случайным образом выбирает между двумя жестко закодированными выходами.
Питер Тейлор

Ответы:

10

C ++ C, около 1000 670 643 395 297 248 символов

Пример вывода:

00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

Как это работает: программа использует Brownian Motion для генерации решений. Начальная точка установлена. Затем случайная точка выбирается и многократно перемещается случайным образом, пока она не коснется одной и только одной точки в начальной ветви. Затем точка устанавливается, и, если она также касается конечной точки, программа завершается и отображается матрица. Поскольку ни одна точка не может соединить две ветви, через лабиринт проходит только один путь. Программа использует функцию rand и целочисленный аргумент командной строки в качестве начального числа, поэтому при наличии достаточной функции rand должна быть возможность в конечном итоге сгенерировать все действительные лабиринты (однако этот алгоритм не будет создавать неподключенные области, поэтому он не будет генерировать все возможные лабиринты).

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

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

#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

Я добавил новые строки и отступы в отображаемый код для удобства чтения.

Sir_Lagsalot
источник
Я думаю, что вы выиграете в этом ;-) я бы ни за что не смог сжать свою шахту
Kae Verens
Я действительно наслаждался соревнованием :-) Я немного удивлен, что мы все еще единственные ответы, я ожидал, что сценарист по гольфу или что-то подобное уже победили бы нас обоих.
Sir_Lagsalot
Каким-то образом простой путь без вилок и узлов принятия решений, похоже, не считается настоящим лабиринтом. Попробуйте добавить несколько тупиков.
DavidC
@David Carraher Алгоритм генерирует тупики и пути ветвления, как показано в примере. Отсутствие возможности присоединения новой точки к двум уже существующим ветвям просто предотвращает множество решений или циклов в лабиринте.
Sir_Lagsalot
@Sir_Lagsalot Спасибо за разъяснения
DavidC
5

JavaScript, 874 816 788 686 682 668 637 символов

образец вывода:

00000,10111,10111,01010,11000
01011,01000,01010,01111,00011
00100,11010,00111,10111,11010
01111,10001,01110,01010,01000
00000,11110,00001,10101,10110

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

если любой новый 0 находится рядом с точкой выхода (x * y * z == 48), тогда мы открываем выход.

golfed

b=[]
I=Math.random
for(i=5;i--;)for(j=5,b[i]=[];j--;)b[i][j]=[1,1,1,1,1]
b[0][0][0]=0
k=[[0,0,0]]
function q(x,y,z){J=b[x]
if(x<0||y<0||z<0||x>4||y>4||z>4||!J[y][z])return 
n=6-!x||b[x-1][y][z]
n-=!y||J[y-1][z]
n-=!z||J[y][z-1]
n-=x==4||b[x+1][y][z]
n-=y==4||J[y+1][z]
n-=z==4||J[y][z+1]
n==1&&v.push([x,y,z])}while(I){F=k.length
B=k[C=0|I(v=[])*F]
x=B[0]
q(x-1,y=B[1],z=B[2])
q(x,y-1,z)
q(x,y,z-1)
q(x+1,y,z)
q(x,y+1,z)
q(x,y,z+1)
if(D=v.length){k.push(A=v[0|I()*D])
b[A[0]][A[1]][A[2]]=0
if(A[0]*A[1]*A[2]==48)b[4][4][4]=I=0}else{for(E=[];F--;)F^C&&E.push(k[F])
k=E}}for(i=25;i--;)b[H=0|i/5][i%5]=b[H][i%5].join('')
alert(b.join("\n"))

оригинал

window.map=[];
for (i=0;i<5;++i) {
  map[i]=[];
  for (j=0;j<5;++j) {
    map[i][j]=[1,1,1,1,1];
  } 
} 
points=[[0,0,0]];
map[0][0][0]=0;
function spaces(x,y,z) {
  var n=6;
  if (x<0 || y<0 || z<0) return 0;
  if (x>4 || y>4 || z>4) return 0;
  if (!map[x][y][z]) return 0;
  if (!x || map[x-1][y][z]) n--;
  if (!y || map[x][y-1][z]) n--;
  if (!z || map[x][y][z-1]) n--;
  if (x==4 || map[x+1][y][z]) n--;
  if (y==4 || map[x][y+1][z]) n--;
  if (z==4 || map[x][y][z+1]) n--;
  return n;
} 
do {
  var index=Math.floor(Math.random()*points.length);
  point=points[index];
  v=[];
  x=point[0];
  y=point[1];
  z=point[2];
  spaces(x-1,y,z)==1 && v.push([x-1,y,z]);
  spaces(x,y-1,z)==1 && v.push([x,y-1,z]);
  spaces(x,y,z-1)==1 && v.push([x,y,z-1]);
  spaces(x+1,y,z)==1 && v.push([x+1,y,z]);
  spaces(x,y+1,z)==1 && v.push([x,y+1,z]);
  spaces(x,y,z+1)==1 && v.push([x,y,z+1]);
  if (v.length) {
    var point=v[Math.floor(Math.random()*v.length)];
    points.push(point);
    map[point[0]][point[1]][point[2]]=0;
    if (point[0]*point[1]*point[2]==48) {
      map[4][4][4]=0;
    } 
  } 
  else {
    var np=[];
    for (var i=0;i<points.length;++i) {
      i!=index && np.push(points[i]); 
    } 
    points=np;
  } 
} while(points.length);
for (i=0;i<5;++i) {
  for (j=0;j<5;++j) {
    map[i][j]=map[i][j].join('');
  } 
  map[i]=map[i].join();
} 
alert(map.join("\n"));
Кае Веренс
источник
4

Mathematica: настоящий лабиринт (827 символов)

Первоначально я создал путь от {1,1,1} до {5,5,5}, но поскольку не было возможных неправильных поворотов, я ввел вилки или «точки принятия решения» (вершины степени> 2), где нужно было бы решить, в какую сторону идти. В результате получается настоящий лабиринт или лабиринт.

«Слепые переулки» решить гораздо сложнее, чем найти простой прямой путь. Самым сложным было устранить циклы на пути, позволяя циклам отклоняться от пути решения.

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

o = Sequence[VertexLabels -> "Name", ImagePadding -> 10, GraphHighlightStyle -> "Thick", 
    ImageSize -> 600];

o2 = Sequence[ImagePadding -> 10, GraphHighlightStyle -> "Thick", ImageSize -> 600];

Используемый код:

e[c_] := Cases[EdgeList[GridGraph[ConstantArray[5, 3]]], j_ \[UndirectedEdge] k_ /; (MemberQ[c, j] && MemberQ[c, k])]

m[] :=
Module[{d = 5, v = {1, 125}},
   While[\[Not] MatchQ[FindShortestPath[Graph[e[v]], 1, 125], {1, __, 125}],

v = Join[v, RandomSample[Complement[Range[125], v], 1]]];
   Graph[e[Select[ConnectedComponents[Graph[e[v]]], MemberQ[#, 1] &][[1]]]]]

w[gr_, p_] := EdgeDelete[gr, EdgeList[PathGraph[p]]]

y[p_, u_] := Select[Intersection[#, p] & /@ ConnectedComponents[u], Length[#] > 1 &]

g = HighlightGraph[lab = m[],  PathGraph[s = FindShortestPath[lab, 1, 125]],o]
u = w[g, s]
q = y[s, u]

While[y[s, u] != {}, u =  EdgeDelete[u, Take[FindShortestPath[u,  q[[1, r = RandomInteger[Length@q[[1]] - 2] + 1]], 
  q[[1, r + 1]]], 2] /. {{a_, b_} :> a \[UndirectedEdge] b}];

q = y[s, u]]

g = EdgeAdd[u, EdgeList@PathGraph[s]];

Partition[StringJoin /@ Partition[ReplacePart[Table["x", {125}], 
Transpose[{VertexList[g], Table["o", {Length[VertexList@g]}]}]/. {{a_, b_} :>  a -> b}], {5}], 5]

Образец вывода

{{"oxooo", "xxooo", "xoxxo", "xoxxo", "xxoox"}, {"ooxoo", "xoooo", "ooxox", "oooxx", "xooxx"}, {"oooxx", "ooxxo", "ooxox", "xoxoo", "xxxoo"}, {"oxxxx", "oooox", "xooox", "xoxxx", "oooxx"}, {"xxxxx", "ooxox", "oooox "," xoxoo "," oooxo "}}

Под капотом

На рисунке ниже показан лабиринт или лабиринт, который соответствует решению, ({{"ooxoo",...}}показанному выше:

solution1

Вот тот самый лабиринт, вставленный в 5х5х5 GridGraph. Нумерованные вершины - это узлы на кратчайшем пути из лабиринта. Обратите внимание на разветвления или точки принятия решений на 34, 64 и 114. Я включу код, используемый для визуализации графика, даже если он не является частью решения:

HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], g,  
 GraphHighlightStyle ->"DehighlightFade", 
 VertexLabels -> Rule @@@ Transpose[{s, s}] ]

solution2

И этот график показывает только решение лабиринта:

HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], 
   Join[s, e[s]], GraphHighlightStyle -> "DehighlightFade", VertexLabels -> Rule @@@    Transpose[{s, s}] ]

solution3

Наконец, некоторые определения, которые могут помочь при чтении кода:

определения


Оригинальное решение (432 знака, Произведен путь, но не настоящий лабиринт или лабиринт)

Представьте себе большой твердый куб 5x5x5, состоящий из отдельных единичных кубов. Следующее начинается без единичных кубов в {1,1,1} и {5,5,5}, так как мы знаем, что они должны быть частью решения. Затем он удаляет случайные кубы, пока не появится беспрепятственный путь от {1,1,1} до {5,5,5}.

«Лабиринт» - это кратчайший путь (если возможно более одного) из кубов, которые были удалены.

d=5
v={1,d^3}
edges[g_,c_]:=Cases[g,j_\[UndirectedEdge] k_/;(MemberQ[c,j]&&MemberQ[c,k])]

g:=Graph[v,edges[EdgeList[GridGraph[ConstantArray[d,d]]],v]];

While[\[Not]FindShortestPath[g,1,d^3]!={},
    v=Join[v,RandomSample[Complement[Range[d^3],v],1]]]

Partition[Partition[ReplacePart[
   Table["x",{d^3}],Transpose[{FindShortestPath[g,1,d^3],Table["o",{Length[s]}]}]
      /.{{a_,b_}:>  a->b}],{d}]/.{a_,b_,c_,d_,e_}:>  StringJoin[a,b,c,d,e],5]

Пример:

{{"ooxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxx"}, 
 {"xoxxx", "xoooo", "xxxxo", "xxxxo", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}}

Технически это еще не настоящий лабиринт, поскольку нет неправильных поворотов, которые можно совершить. Но я подумал, что это интересно с самого начала, поскольку он опирается на теорию графов.

Рутина на самом деле делает лабиринт, но я заткнул все пустые места, которые могли вызвать циклы. Если я найду способ удалить циклы, я включу этот код здесь.

DavidC
источник
Хорошее обновление, мне нравится, что ваше обновленное решение допускает циклы на не-путях решения, это создает более запутанный лабиринт.
Sir_Lagsalot
Спасибо. Я все еще хотел бы, чтобы сам путь решения время от времени отклонялся от конечного узла. Это в настоящее время не рекомендуется (но не полностью предотвращено) FindShortestPath.
DavidC
Я не слишком знаком с matlab, но не могли бы вы сделать что-то вроде FindShortestPath, добавить смещение против каждого узла в кратчайшем пути, а затем снова запустить FindShortestPath с учетом смещения, чтобы избежать узлов в самом коротком решении? Это может быть сделано итеративно. Мне было бы интересно посмотреть, какой тип пути это даст.
Sir_Lagsalot
@Sir_Lagsalot Я разместил это как вопрос для группы Mathematica SE здесь ( mathematica.stackexchange.com/questions/4084/… )
DavidC