Code Golf: Résoudre un labyrinthe

Question

Voici un problème intéressant à résoudre en quantité minimale de code. Je m'attends à ce que les solutions récursives soient les plus populaires.

Nous avons un labyrinthe qui est défini comme une carte de caractères, où = est un mur, un espace est un chemin, + est votre point de départ et # est votre point de fin. Un exemple très simple comme ceci:

==== 
+ = 
= == 
= # 
==== 

Pouvez-vous écrire un programme pour trouver le chemin le plus court pour résoudre un labyrinthe dans ce style, en aussi peu que possible le code?

Points bonus si cela fonctionne pour toutes les entrées de labyrinthe, comme celles avec un chemin qui se croise sur lui-même ou avec un grand nombre de branches. Le programme devrait être en mesure de travailler pour de grands labyrinthes (disons, 1024x1024 - 1 Mo), et la façon dont vous passez le labyrinthe au programme n'est pas important.

Le "joueur" peut se déplacer en diagonale. Le labyrinthe d'entrée n'aura jamais de passage en diagonale, donc votre ensemble de mouvements de base sera en haut, en bas, à gauche, à droite. Un mouvement en diagonale serait simplement regarder un peu en avant pour déterminer si un haut/bas et gauche/droite pourrait être fusionné.

La sortie doit être le labyrinthe lui-même avec le chemin le plus court mis en surbrillance à l'aide du caractère astérisque (*).

Answer 1

python

387 caractères

accepte une entrée à partir de l'entrée standard.

import sys 
m,n,p=sys.stdin.readlines(),[],'+' 
R=lambda m:[r.replace(p,'*')for r in m] 
while'#'in`m`:n+=[R(m)[:r]+[R(m)[r][:c]+p+R(m)[r][c+1:]]+R(m)[r+1:]for r,c in[(r,c)for r,c in[map(sum,zip((m.index(filter(lambda i:p in i,m)[0]),[w.find(p)for w in m if p in w][0]),P))for P in zip((-1,0,1,0),(0,1,0,-1))]if 0<=r<len(m)and 0<=c<len(m[0])and m[r][c]in'# ']];m=n.pop(0) 
print''.join(R(m)) 

Answer 2

Fonctionne pour n'importe quel labyrinthe (de taille fixe) avec un minimum de cycles CPU (avec un BFG2000 assez grand). La taille de la source est sans importance puisque le compilateur est incroyablement efficace.

while curr.x != target.x and curr.y != target.y: 
    case: 
     target.x > curr.x : dx = 1 
     target.x < curr.x : dx = -1 
     else    : dx = 0 
    case: 
     target.y > curr.y : dy = 1 
     target.y < curr.y : dy = -1 
     else    : dy = 0 
    if cell[curr.x+dx,curr.y+dy] == wall: 
     destroy cell[curr.x+dx,curr.y+dy] with patented BFG2000 gun. 
    curr.x += dx 
    curr.y += dy 
survey shattered landscape 

Answer 3

F #, pas très court (72 lignes non vides), mais lisible. J'ai changé/aiguisé la spécification un peu; Je suppose que le labyrinthe d'origine est un rectangle entièrement entouré de murs, j'utilise des caractères différents (qui ne me font pas mal aux yeux), je ne permets que des mouvements orthogonaux (pas diagonaux). J'ai seulement essayé un labyrinthe d'échantillon. Excepté un bug sur le retournement des indices x et y, cela a fonctionné la première fois, donc je m'attends à ce que ce soit correct (je n'ai rien fait pour valider autre que la solution sur l'échantillon que je lui ai donné).

open System 

[<Literal>] 
let WALL = '#' 
[<Literal>] 
let OPEN = ' ' 
[<Literal>] 
let START = '^' 
[<Literal>] 
let END = '$' 
[<Literal>] 
let WALK = '.' 

let sampleMaze = @"############### 
# # #  # 
# ^# # # ### # 
# # # # # # # 
#  # # # 
############ # 
# $  # 
###############" 

let lines = sampleMaze.Split([|'\r';'\n'|], StringSplitOptions.RemoveEmptyEntries) 
let width = lines |> Array.map (fun l -> l.Length) |> Array.max 
let height = lines.Length 
type BestInfo = (int * int) list * int // path to here, num steps 
let bestPathToHere : BestInfo option [,] = Array2D.create width height None 

let mutable startX = 0 
let mutable startY = 0 
for x in 0..width-1 do 
    for y in 0..height-1 do 
     if lines.[y].[x] = START then 
      startX <- x 
      startY <- y 
bestPathToHere.[startX,startY] <- Some([],0) 

let q = new System.Collections.Generic.Queue<_>() 
q.Enqueue((startX,startY)) 
let StepTo newX newY (path,count) = 
    match lines.[newY].[newX] with 
    | WALL ->() 
    | OPEN | START | END -> 
     match bestPathToHere.[newX,newY] with 
     | None -> 
      bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1) 
      q.Enqueue((newX,newY)) 
     | Some(_,oldCount) when oldCount > count+1 -> 
      bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1) 
      q.Enqueue((newX,newY)) 
     | _ ->() 
    | c -> failwith "unexpected maze char: '%c'" c 
while not(q.Count = 0) do 
    let x,y = q.Dequeue() 
    let (Some(path,count)) = bestPathToHere.[x,y] 
    StepTo (x+1) (y) (path,count) 
    StepTo (x) (y+1) (path,count) 
    StepTo (x-1) (y) (path,count) 
    StepTo (x) (y-1) (path,count) 

let mutable endX = 0 
let mutable endY = 0 
for x in 0..width-1 do 
    for y in 0..height-1 do 
     if lines.[y].[x] = END then 
      endX <- x 
      endY <- y 

printfn "Original maze:" 
printfn "%s" sampleMaze 
let bestPath, bestCount = bestPathToHere.[endX,endY].Value 
printfn "The best path takes %d steps." bestCount 
let resultMaze = Array2D.init width height (fun x y -> lines.[y].[x]) 
bestPath |> List.tl |> List.iter (fun (x,y) -> resultMaze.[x,y] <- WALK) 
for y in 0..height-1 do 
    for x in 0..width-1 do 
     printf "%c" resultMaze.[x,y] 
    printfn "" 

//Output: 
//Original maze: 
//############### 
//# # #  # 
//# ^# # # ### # 
//# # # # # # # 
//#  # # # 
//############ # 
//# $  # 
//############### 
//The best path takes 27 steps. 
//############### 
//# # #....... # 
//# ^# #.# ###. # 
//# .# #.# # #. # 
//# .....# #. # 
//############. # 
//# $....... # 
//############### 

Answer 4

j'ai fait ce genre de chose pour une entrevue d'emploi une fois (il a été un défi de programmation pré-interview)

a réussi à le faire fonctionner à un certain degré de succès et il est un petit défi amusant.