Portal Maze Shortest Path

16

Twoim celem jest napisanie programu, który utworzy losową mapę 10x10 za pomocą 0, 1i 2, i znajdzie najkrótszą ścieżkę od górnego lewego do prawego dolnego, zakładając, że:

0 oznacza pole trawiaste: każdy może po nim chodzić;
1 oznacza ścianę: nie można jej przekroczyć;
2 reprezentuje portal: wchodząc do portalu możesz przejść do dowolnego innego portalu na mapie.

Okular:

  • Lewy górny element i prawy dolny element muszą mieć wartość 0 ;
  • Podczas tworzenia losowej mapy każde pole powinno mieć 60% szansy na 0 , 30% na 1 i 10% na 2 ;
  • Możesz poruszać się po dowolnym sąsiednim polu (nawet ukośnym);
  • Twój program powinien wypisać mapę i liczbę kroków najkrótszej ścieżki;
  • Jeśli nie ma prawidłowej ścieżki prowadzącej do prawego dolnego pola, twój program powinien wypisać tylko mapę;
  • Możesz użyć dowolnego zasobu, który chcesz;
  • Najkrótszy kod wygrywa.

Obliczanie kroków:
Krok jest rzeczywistym ruchem; za każdym razem, gdy zmieniasz pole, zwiększasz licznik.

Wynik:

0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100

9
code-golf  path-finding  maze 
— Vereos
źródło
Czy nie możemy po prostu stworzyć programu na najkrótszą ścieżkę? Generowanie to kolejne pytanie.
— Mikaël Mayer
Nie określiłeś, że losowa mapa za każdym razem musi być inna :)
— marinus
@marinus LoooL! Cóż, w specyfikacjach napisałem szanse na generowanie, więc myślę, że napisanie standardowej mapy z 60 0, 30 1 i 10 2 nie będzie właściwym rozwiązaniem: P
— Vereos
@ MikaëlMayer Chyba masz rację, ale myślę, że byłoby to trudniejsze. Czy się mylę?
— Vereos
Ponieważ jest to pytanie związane z golfem, zwycięskim kryterium jest najkrótszy kod. Co się stanie, jeśli ten kod jest naprawdę wolny i trwa setki lat?
— Victor Stafusa

Odpowiedzi:

3

GolfScript, 182 znaki

;0`{41 3 10rand?/3%`}98*0`]10/n*n+.[12n*.]*.0{[`/(,\+{,)1$+}*;]}:K~\2K:P+${[.12=(]}%.,,{.{\1==}+2$\,{~;.P?0<!P*3,{10+}%1+{2$1$-\3$+}%+~}%`{2$~0<@@?-1>&2$[~;@)](\@if}++%}/-1=1=.0<{;}*

Przykłady:

0000001002
1010000001
0011010000
2001020000
0100100011
0110100000
0100000100
0010002010
0100110000
0012000210
6

0000100000
0100000001
1100000000
1011010000
0010001100
0101010200
0000200012
1100100110
0000011001
2201010000
11

0012010000
1000100122
0000001000
0111010100
0010012001
1020100110
1010101000
0102011111
0100100010
2102100110
— Howard
źródło
4

Matematyka (344)

Bonus: wyróżnienie ścieżki

n = 10;
m = RandomChoice[{6, 3, 1} -> {0, 1, 2}, {n, n}];
m[[1, 1]] = m[[n, n]] = 0;

p = FindShortestPath[Graph@DeleteDuplicates@Join[Cases[#, Rule[{ij__}, {k_, l_}] /; 
      0 < k <= n && 0 < l <= n && m[[ij]] != 1 && m[[k, l]] != 1] &@
   Flatten@Table[{i, j} -> {i, j} + d, {i, n}, {j, n}, {d, Tuples[{-1, 0, 1}, 2]}], 
  Rule @@@ Tuples[Position[m, 2], 2]], {1, 1}, {n, n}];

Grid@MapAt[Style[#, Red] &, m, p]
If[# > 0, #-1] &@Length[p]

wprowadź opis zdjęcia tutaj

Tworzę wykres wszystkich możliwych filmów do sąsiednich wierzchołków i dodam wszystkie możliwe „teleporty”.

— Ybeltukov
źródło
3

Mathematica, 208 202 znaków

Oprzyj się na rozwiązaniach Davida Carrahera i Ybeltukova. I dzięki sugestii Ybeltukova.

m=RandomChoice[{6,3,1}->{0,1,2},n={10,10}];m〚1,1〛=m〚10,10〛=0;Grid@m
{s,u}=m~Position~#&/@{0,2};If[#<∞,#]&@GraphDistance[Graph[{n/n,n},#<->#2&@@@Select[Subsets[s⋃u,{2}],Norm[#-#2]&@@#<2||#⋃u==u&]],n/n,n]
— alephalpha
źródło
Fajnie, +1! Dalsza optymalizacja: n/nzamiast n/10:)
— ybeltukov
Ładne usprawnienie. I wydrukujesz mapę od razu.
— DavidC
A 〚 〛w nawiasach (to poprawne symbole Unicode)
— ybeltukov
Czy możesz wyjaśnić kryterium wyboru,Norm[# - #2] & @@ # < 2 || # \[Union] u == u &
— DavidC
@DavidCarraher Norm[# - #2] & @@ # < 2oznacza, że ​​odległość między dwoma punktami jest mniejsza niż 2, więc muszą się one sąsiadować. # ⋃ u == uoznacza, że ​​oba punkty są w tobie.
— alephalpha
2

Python 3, 279

Niektóre warianty Dijkstra. Brzydkie, ale grałem w golfa tak bardzo, jak tylko mogłem ...

from random import*
R=range(10)
A={(i,j):choice([0,0,1]*3+[2])for i in R for j in R}
A[0,0]=A[9,9]=0
for y in R:print(*(A[x,y]for x in R))
S=[(0,0,0,0)]
for x,y,a,c in S:A[x,y]=1;x*y-81or print(c)+exit();S+=[(X,Y,b,c+1)for(X,Y),b in A.items()if a+b>3or~-b and-2<X-x<2and-2<Y-y<2]

Przykładowy przebieg

0 1 1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 1 0 0
0 1 2 1 2 1 0 0 1 0
0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 1
1 0 0 1 0 0 1 1 1 0
0 0 0 0 1 0 0 0 0 1
0 1 2 1 0 1 1 0 0 0
10
— Przywróć Monikę
źródło
1

Mathematica 316 279 275

Podstawowym obiektem jest tablica 10x10 z około 60 0, 30 1 i 10 2. Tablica służy do modyfikacji 10x10 GridGraph, z połączonymi wszystkimi krawędziami. Te węzły, które odpowiadają komórkom zawierającym 1 w tablicy są usuwane z wykresu. Wszystkie węzły „posiadające 2” są ze sobą połączone. Następnie szukana jest Najkrótsza Ścieżka między wierzchołkiem 1 a wierzchołkiem 100. Jeśli taka ścieżka nie istnieje, mapa jest zwracana; jeśli taka ścieżka istnieje, wyświetlana jest mapa i najkrótsza długość ścieżki.

m = Join[{0}, RandomChoice[{6, 3, 1} -> {0, 1, 2}, 98], {0}];
{s,t,u}=(Flatten@Position[m,#]&/@{0,1,2});
g=Graph@Union[EdgeList[VertexDelete[GridGraph@{10,10},t]],Subsets[u,{2}] 
/.{a_,b_}:>a \[UndirectedEdge] b];
If[IntegerQ@GraphDistance[g,1,100],{w=Grid@Partition[m,10],  
Length@FindShortestPath[g,1,100]-1},w]

Przykładowy przebieg :

wykres

— DavidC
źródło
1
„Możesz poruszać się w dowolnym sąsiednim polu (nawet ukośnym)”.
— alephalpha
0

Python (1923)

Wyszukiwanie powrotne

Trzeba przyznać, że nie jest to najkrótsza ani najwydajniejsza, choć istnieje pewna zapamiętywanie.

import random
l = 10
map = [
    [(lambda i: 0 if i < 7 else 1 if i < 10 else 2)(random.randint(1, 10))
     for i in range(0, l)]
    for i in range(0, l)
    ]
map[0][0] = map[l-1][l-1] = 0
print "\n".join([" ".join([str(i) for i in x]) for x in map])

paths = {}
def step(past_path, x, y):
    shortest = float("inf")
    shortest_path = []

    current_path = past_path + [(x, y)]
    pos = map[x][y]
    if (x, y) != (0, 0):
        past_pos = map[past_path[-1][0]][past_path[-1][1]]

    if (((x, y) in paths or str(current_path) in paths)
        and (pos != 2 or past_pos == 2)):
        return paths[(x, y)]
    elif x == l-1 and y == l-1:
        return ([(x, y)], 1)

    if pos == 1:
        return (shortest_path, shortest)
    if pos == 2 and past_pos != 2:
        for i2 in range(0, l):
            for j2 in range(0, l):
                pos2 = map[i2][j2]
                if pos2 == 2 and (i2, j2) not in current_path:
                    path, dist = step(current_path, i2, j2)
                    if dist < shortest and (x, y) not in path:
                        shortest = dist
                        shortest_path = path
    else:
        for i in range(x - 1, x + 2):
            for j in range(y - 1, y + 2):
                if i in range(0, l) and j in range(0, l):
                    pos = map[i][j]
                    if pos in [0, 2] and (i, j) not in current_path:
                        path, dist = step(current_path, i, j)
                        if dist < shortest and (x, y) not in path:
                            shortest = dist
                            shortest_path = path
    dist = 1 + shortest
    path = [(x, y)] + shortest_path
    if dist != float("inf"):
        paths[(x, y)] = (path, dist)
    else:
        paths[str(current_path)] = (path, dist)
    return (path, dist)

p, d = step([], 0, 0)
if d != float("inf"):
    print p, d
— vinod
źródło
1
Wow, teraz to liczba znaków dla golfa kodowego! Myślę, że twoja piłka wylądowała w złym stanie.
— Tim Seguine,
Haha tak, nie zawracałem sobie głowy graniem w kod lub próbowaniem znalezienia najkrótszej implementacji, ale policzyłem liczbę znaków, aby ludzie wiedzieli, że mogą zignorować to rozwiązanie. Wydawało się, że to zabawny problem.
— vinod
0

JavaScript (541)

z=10
l=[[0]]
p=[]
f=[[0]]
P=[]
for(i=0;++i<z;)l[i]=[],f[i]=[]
for(i=0;++i<99;)P[i]=0,l[i/z|0][i%z]=99,f[i/z|0][i%z]=(m=Math.random(),m<=.6?0:m<=.9?1:(p.push(i),2))
f[9][9]=0
l[9][9]=99
Q=[0]
for(o=Math.min;Q.length;){if(!P[s=Q.splice(0,1)[0]]){P[s]=1
for(i=-2;++i<2;)for(j=-2;++j<2;){a=i+s/z|0,b=j+s%z
if(!(a<0||a>9||b<0||b>9)){q=l[a][b]=o(l[s/z|0][s%z]+1,l[a][b])
if(f[a][b]>1){Q=Q.concat(p)
for(m=0;t=p[m];m++)l[t/z|0][t%z]=o(l[t/z|0][t%z],q+1)}!f[a][b]?Q.push(a*z+b):''}}}}for(i=0;i<z;)console.log(f[i++])
console.log((k=l[9][9])>98?"":k)

Generowanie wykresu następuje w pierwszych pięciu wierszach. fzawiera pola, pzawiera portale. Rzeczywiste wyszukiwanie jest realizowane przez BFS.

Przykładowe dane wyjściowe:

> node maze.js
[0, 0, 0, 0, 1, 0, 0, 0, 2, 0]
[0, 1, 1, 0, 0, 1, 0, 0, 0, 2]
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0]
[1, 1, 1, 0, 2, 2, 0, 1, 0, 1]
[1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[1, 1, 0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 1, 0, 0, 2, 0]
[0, 0, 1, 0, 1, 2, 0, 1, 0, 1]
[1, 0, 0, 0, 1, 1, 1, 0, 1, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0]

> node maze.js
[0, 0, 0, 0, 1, 0, 1, 0, 0, 1]
[0, 2, 0, 1, 1, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 2, 1, 1, 0, 1, 0]
[2, 0, 1, 0, 2, 2, 2, 0, 1, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 1, 0, 0]
[0, 1, 2, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 2, 1, 0, 1, 2, 0, 0, 1]
[0, 1, 2, 0, 0, 0, 0, 0, 0, 0]
5
— Zeta
źródło
0

Python 3 (695)

import random as r
if __name__=='__main__':
    x=144
    g,t=[1]*x,[]
    p=lambda i:12<i<131 and 0<i%12<11
    for i in range(x):
        if p(i):
            v=r.random()
            g[i]=int((v<=0.6 or i in (13,130)) and .1 or v<=0.9 and 1 or 2)
            if g[i]>1:t+=[i]
            print(g[i],end='\n' if i%12==10 else '')
    d=[99]*x
    d[13]=0
    n = list(range(x))
    m = lambda i:[i-1,i+1,i-12,i+12,i-13,i+11,i+11,i+13]
    while n:
        v = min(n,key=lambda x:d[x])
        n.remove(v)
        for s in m(v)+(t if g[v]==2 else []):
            if p(s) and g[s]!=1 and d[v]+(g[s]+g[v]<4)<d[s]:
                d[s]=d[v]+(g[s]+g[v]<3)
    if d[130]<99:print('\n'+str(d[130]))

Dijkstra!

Przykładowe dane wyjściowe:

0000202000
2011000111
0000002000
0101001000
0000100110
1110100101
0020101000
0011200000
1010101010
0000001000

6
— muede
źródło
0

Python, 314

import random,itertools as t
r=range(10)
a,d=[[random.choice([0]*6+[1]*3+[2])for i in r]for j in r],eval(`[[99]*10]*10`)
a[0][0]=a[9][9]=d[0][0]=0
for q,i,j,m,n in t.product(r*10,r,r,r,r):
 if a[m][n]!=1and abs(m-i)<2and abs(n-j)<2or a[i][j]==a[m][n]==2:d[m][n]=min(d[i][j]+1,d[m][n])
w=d[9][9]
print a,`w`*(w!=99)


To obrzydliwe wdrożenie Bellman-Ford. Ten algorytm to O (n ^ 6)! (Co jest w porządku dla n = 10)

— Sanjeev Murty
źródło
Mapa wygląda naprawdę brzydko. Czy to działa, jeśli potrzeba więcej niż 10 kroków?
— Przywróć Monikę
@WolframH Oczywiście: en.wikipedia.org/wiki/…
— Sanjeev Murty
Mógłbym to zrobić print '\n'.join(map(str,a)); Zrobiłem print aze względu na golfa.
— Sanjeev Murty
Nie wątpiłem w poprawność algorytmu :-). Po prostu nie zdawałem sobie sprawy, że często zapętlasz (co robisz; r*10ma 100 elementów).
— Przywróć Monikę
Tak. W rzeczywistości 100 to przesada; 99 jest wszystkim, czego potrzeba.
— Sanjeev Murty
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.