16

Votre objectif est d'écrire un programme qui crée une carte aléatoire 10 x 10 à l'aide de 0, 1et 2, et trouve le chemin le plus court de haut en bas à bas à droite, en supposant que:

0 représente un champ d'herbe: n'importe qui peut marcher dessus;
1 représente un mur: vous ne pouvez pas le traverser;
2 représente un portail: lorsque vous entrez dans un portail, vous pouvez vous déplacer vers n'importe quel autre portail de la carte.

Spécifications:

L'élément en haut à gauche et celui en bas à droite doivent être 0 ;
Lors de la création de la carte aléatoire, chaque champ devrait avoir 60% de chances d'être un 0 , 30% d'être un 1 et 10% d'être un 2 ;
Vous pouvez vous déplacer dans n'importe quel champ adjacent (même en diagonale);
Votre programme doit afficher la carte et le nombre d'étapes du chemin le plus court;
S'il n'y a pas de chemin valide menant au champ en bas à droite, votre programme doit sortir la carte uniquement;
Vous pouvez utiliser n'importe quelle ressource que vous souhaitez;
Le code le plus court gagne.

Calcul des étapes:
Une étape est un mouvement réel; chaque fois que vous changez de champ, vous incrémentez le compteur.

Production:

code-golf path-finding maze Vereos
la source

Ne pouvons-nous pas simplement produire le programme pour le chemin le plus court? Générer est une autre question.

Mikaël Mayer

Vous n'avez pas spécifié que la carte aléatoire doit être différente à chaque fois :)

marinus

@marinus LoooL! Eh bien, dans les spécifications, j'ai écrit les chances de génération, donc je suppose que l'écriture d'une carte standard avec 60 0, 30 1 et 10 2 ne sera pas une bonne solution: P

Vereos

@ MikaëlMayer Je suppose que vous avez raison, mais je pense que ce serait plus difficile comme ça. Ai-je tort?

Vereos

Comme il s'agit d'une question de code-golf, le critère de gain est le code le plus court. Que se passe-t-il si ce code est vraiment lent et prend des siècles à fonctionner?

Victor Stafusa

3

GolfScript, 182 caractères

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

Exemples:

Howard
la source

4

Mathematica (344)

Bonus: mise en évidence du chemin

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]

entrez la description de l'image ici

Je crée le graphique de tous les films possibles aux sommets voisins et j'ajoute tous les "téléports" possibles.

ybeltukov
la source

3

Mathematica, 208 202 caractères

Base sur les solutions de David Carraher et d'Ybeltukov. Et merci à la suggestion d'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
la source

Nice, +1! Optimisation supplémentaire: n/nau lieu de n/10:)

ybeltukov

Belle rationalisation. Et vous imprimez la carte tout de suite.

DavidC

Et 〚〛pour les crochets (ce sont des symboles Unicode corrects)

ybeltukov

Pouvez-vous expliquer le critère de sélection,Norm[# - #2] & @@ # < 2 || # \[Union] u == u &

DavidC

@DavidCarraher Norm[# - #2] & @@ # < 2signifie que la distance entre deux points est inférieure à 2, ils doivent donc être adjacents. # ⋃ u == usignifie que les deux points sont en u.

alephalpha

2

Python 3, 279

Une variante de Dijkstra. Moche, mais j'ai joué au golf autant que j'ai pu ...

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]

Sample Run

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

Réintégrer Monica
la source

1

Mathematica 316 279 275

L'objet de base est un tableau 10x10 avec environ 60 0, 30 1 et 10 2. Le tableau est utilisé pour modifier un 10x10 GridGraph, avec tous les bords connectés. Les nœuds qui correspondent aux cellules contenant 1 dans le tableau sont supprimés du graphique. Ces nœuds "contenant 2" sont tous connectés les uns aux autres. Ensuite, le chemin le plus court est recherché entre le sommet 1 et le sommet 100. Si un tel chemin n'existe pas, la carte est renvoyée; si un tel chemin existe, la carte et la longueur de chemin la plus courte sont affichées.

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]

Exemple d'exécution :

graphique

DavidC
la source

1

"Vous pouvez vous déplacer dans n'importe quel champ adjacent (même en diagonale)".

alephalpha

0

Python (1923)

Recherche de retour en arrière

Certes pas le plus court ou le plus efficace, bien qu'il y ait une certaine mémorisation présente.

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
la source

1

Wow, maintenant c'est un nombre de caractères pour un golf de code! Je pense que votre balle a atterri à l'état brut.

Tim Seguine du

Haha ouais je n'ai pas pris la peine de jouer au code ou d'essayer de trouver la mise en œuvre la plus courte, mais j'ai augmenté le nombre de caractères pour que les gens sachent qu'ils pourraient ignorer cette solution. Cela semblait être un problème amusant.

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 génération du graphique se produit dans les cinq premières lignes. fcontient les champs, pdétient les portails. La recherche proprement dite est implémentée via BFS.

Exemple de sortie:

> 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
la source

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!

Exemple de sortie:

muede
la source

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)

C'est une mise en œuvre dégoûtante de Bellman-Ford. Cet algorithme est O (n ^ 6)! (Ce qui est correct pour n = 10)

Sanjeev Murty
la source

La carte a l'air vraiment moche. Est-ce que cela fonctionne si plus de 10 étapes sont nécessaires?

Rétablir Monica le

@WolframH Bien sûr: en.wikipedia.org/wiki/…

Sanjeev Murty

Je pourrais le faire print '\n'.join(map(str,a)); Je l'ai fait print apour le golf.

Sanjeev Murty

Je ne doutais pas de l'exactitude de l'algorithme :-). Je n'avais simplement pas réalisé que vous boucliez assez souvent (ce que vous faites; r*10a 100 éléments).

Rétablir Monica le

Ouais. En fait, 100 est exagéré; 99 est tout ce qui est nécessaire.

Sanjeev Murty

Portal Maze Shortest Path

Réponses:

GolfScript, 182 caractères

Mathematica (344)

Mathematica, 208 202 caractères

Python 3, 279

Mathematica 316 279 275

Python (1923)

JavaScript (541)

Exemple de sortie:

Python 3 (695)

Exemple de sortie:

Python, 314