Ihr Ziel ist es, ein Programm zu schreiben, das eine zufällige 10x10-Karte mit 0, 1und erstellt 2und den kürzesten Pfad von links oben nach rechts unten findet, vorausgesetzt, dass:

0 steht für eine Rasenfläche: jeder kann darauf laufen;
1 stellt eine Mauer dar: man kann sie nicht überqueren;
2 steht für ein Portal: Wenn Sie ein Portal betreten, können Sie zu einem beliebigen anderen Portal in der Karte wechseln.

Technische Daten:

• Das Element oben links und das Element unten rechts müssen 0 sein .
• Bei der Erstellung der Zufallskarte sollte jedes Feld eine 60% ige Chance haben, eine 0 , 30% eine 1 und 10% eine 2 zu sein .
• Sie können sich in ein beliebiges benachbartes Feld bewegen (auch diagonale).
• Ihr Programm sollte die Karte und die Anzahl der Schritte des kürzesten Pfades ausgeben.
• Wenn es keinen gültigen Pfad gibt, der zum Feld unten rechts führt, sollte Ihr Programm nur die Karte ausgeben.
• Sie können jede Ressource verwenden, die Sie möchten.
• Kürzester Code gewinnt.

Berechnen von Schritten:
Ein Schritt ist eine tatsächliche Bewegung; Jedes Mal, wenn Sie das Feld ändern, erhöhen Sie den Zähler.

Ausgabe:

0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100

9

GolfScript, 182 Zeichen

;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<{;}*

Beispiele:

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

Mathematica (344)

Bonus: Hervorhebung des Pfades

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]

Ich erstelle den Graphen aller möglichen Filme zu Nachbarspitzen und füge alle möglichen "Teleports" hinzu.

Mathematica, 208 202 Zeichen

Basis sind die Lösungen von David Carraher und ybeltukov. Und dank des Vorschlags von ybeltukov.

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]

Python 3, 279

Einige Dijkstra-Varianten. Hässlich, aber so viel Golf gespielt wie ich konnte ...

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]

Probelauf

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

Mathematica 316 279 275

Das Basisobjekt ist ein 10 × 10-Array mit ungefähr 60 0, 30 1 und 10 2. Das Array wird verwendet, um eine 10x10 zu ändern GridGraph, wobei alle Kanten verbunden sind. Die Knoten, die den Zellen entsprechen, die 1 im Array enthalten, werden aus dem Diagramm entfernt. Diese Knoten, die "2en halten", sind alle miteinander verbunden. Dann wird der kürzeste Pfad zwischen Scheitelpunkt 1 und Scheitelpunkt 100 gesucht. Wenn ein solcher Pfad nicht existiert, wird die Karte zurückgegeben; Wenn ein solcher Pfad existiert, werden die Karte und die kürzeste Pfadlänge angezeigt.

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]

Probelauf :

Python (1923)

Zugegeben, nicht die kürzeste oder effizienteste, obwohl es einige Memoization gibt.

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

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)

Die Diagrammgenerierung erfolgt in den ersten fünf Zeilen. fenthält die Felder, phält die Portale. Die eigentliche Suche erfolgt über BFS.

Beispielausgabe:

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

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!

Beispielausgabe:

0000202000
2011000111
0000002000
0101001000
0000100110
1110100101
0020101000
0011200000
1010101010
0000001000

6

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)

Es ist eine widerliche Implementierung von Bellman-Ford. Dieser Algorithmus ist O (n ^ 6)! (Welches ist in Ordnung für n = 10)