Camino más corto del laberinto del portal

16

Su objetivo es escribir un programa que crea un mapa utilizando al azar 10x10 0, 1y 2, y encuentra el camino más corto desde la parte superior izquierda a la inferior derecha, en el supuesto de que:

0 representa un campo de hierba: cualquiera puede caminar sobre él;
1 representa un muro: no puedes cruzarlo;
2 representa un portal: al ingresar a un portal, puede moverse a cualquier otro portal en el mapa.

Especificaciones:

  • El elemento superior izquierdo y el inferior derecho deben ser 0 ;
  • Al crear el mapa aleatorio, cada campo debe tener un 60% de posibilidades de ser un 0 , un 30% de ser un 1 y un 10% de ser un 2 ;
  • Puedes moverte en cualquier campo adyacente (incluso los diagonales);
  • Su programa debe generar el mapa y el número de pasos de la ruta más corta;
  • Si no hay una ruta válida que conduzca al campo inferior derecho, su programa solo debería generar el mapa;
  • Puede usar cualquier recurso que desee;
  • El código más corto gana.

Cálculo de pasos:
un paso es un movimiento real; Cada vez que cambia de campo, incrementa el contador.

Salida:

0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100

9
Vereos
fuente
¿No podemos producir el programa para el camino más corto? Generar es otra pregunta.
Mikaël Mayer
No especificó que el mapa aleatorio debe ser diferente cada vez :)
marinus
@marinus LoooL! Bueno, en las especificaciones escribí las posibilidades de generación, así que supongo que escribir un mapa estándar con 60 0, 30 1 y 10 2 no será la solución correcta: P
Vereos
@ MikaëlMayer Creo que tienes razón, pero creo que sería más desafiante como este. ¿Me equivoco?
Vereos
Como esta es una pregunta de código de golf, el criterio ganador es el código más corto. ¿Qué sucede si ese código es realmente lento y tarda siglos en ejecutarse?
Victor Stafusa

Respuestas:

3

GolfScript, 182 caracteres

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

Ejemplos:

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
fuente
4

Mathematica (344)

Bonus: resaltado del camino

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]

ingrese la descripción de la imagen aquí

Creo el gráfico de todas las películas posibles en vértices vecinos y agrego todos los "teletransportes" posibles.

ybeltukov
fuente
3

Mathematica, 208 caracteres

Base en las soluciones de David Carraher y ybeltukov. Y gracias a la sugerencia de 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]
alephalpha
fuente
Bien, +1! Optimización adicional: en n/nlugar de n/10:)
ybeltukov
Buena racionalización. E imprime el mapa de inmediato.
DavidC
Y 〚 〛para los corchetes (son símbolos Unicode correctos)
ybeltukov
¿Puede explicar el criterio de selección?Norm[# - #2] & @@ # < 2 || # \[Union] u == u &
DavidC
@DavidCarraher Norm[# - #2] & @@ # < 2significa que la distancia entre dos puntos es menor que 2, por lo que deben ser adyacentes. # ⋃ u == usignifica que ambos puntos están en u.
alephalpha
2

Pitón 3, 279

Alguna variante de Dijkstra. Feo, pero jugué tanto como pude ...

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]

Ejecución de muestra

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
Reinstalar a Mónica
fuente
1

Mathematica 316 279 275

El objeto básico es una matriz de 10x10 con aproximadamente 60 0, 30 1 y 10 2. La matriz se utiliza para modificar un 10x10 GridGraph, con todos los bordes conectados. Los nodos que corresponden a las celdas que contienen 1 en la matriz se eliminan del gráfico. Esos nodos "que sostienen 2" están todos conectados entre sí. Luego se busca la ruta más corta entre el vértice 1 y el vértice 100. Si dicha ruta no existe, se devuelve el mapa; si existe tal ruta, se muestran el mapa y la longitud de ruta más corta.

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]

Ejecución de muestra :

grafico

DavidC
fuente
1
"Puedes moverte en cualquier campo adyacente (incluso los diagonales)".
alephalpha
0

Pitón (1923)

Búsqueda de retroceso

Es cierto que no es el más corto ni el más eficiente, aunque hay algunas memorias presentes.

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
fuente
1
Wow, ahora que es un recuento de caracteres para un código de golf! Creo que tu bola aterrizó en bruto.
Tim Seguine
Jaja, sí, no me molesté en jugar golf el código o tratar de encontrar la implementación más corta, pero puse el recuento de caracteres para que la gente supiera que podían ignorar esta solución. Simplemente parecía un problema divertido.
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)

La generación de gráficos ocurre en las primeras cinco líneas. fcontiene los campos, pcontiene los portales. La búsqueda real se implementa a través de BFS.

Salida de ejemplo:

> nodo 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]
> nodo 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 5
Zeta
fuente
0

Pitón 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!

Salida de ejemplo:

0000202000
2011000111
0000002000
0101001000
0000100110
1110100101
0020101000
0011200000
1010101010
0000001000

6
muede
fuente
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)


Es una implementación desagradable de Bellman-Ford. Este algoritmo es O (n ^ 6)! (Lo cual está bien para n = 10)

Sanjeev Murty
fuente
El mapa se ve realmente feo. ¿Funciona esto si se necesitan más de 10 pasos?
Vuelva a instalar a Mónica el
@WolframH Por supuesto: en.wikipedia.org/wiki/…
Sanjeev Murty
Podría hacerlo print '\n'.join(map(str,a)); Lo hice print apor el bien del golf.
Sanjeev Murty
No dudé de la exactitud del algoritmo :-). Simplemente no me había dado cuenta de que haces un bucle con suficiente frecuencia (lo que haces; r*10tiene 100 elementos).
Reinstale a Mónica el
Si. En realidad 100 es exagerado; 99 es todo lo que se necesita.
Sanjeev Murty