コードゴルフ：迷路を解く

Question

最小限のコードで解決するのは興味深い問題です。再帰的な解決策が最も人気があると思います。

私たちは文字のマップとして定義されている迷路を持っています。=は壁、スペースはパス、+を出発点とし、#は終点です。

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

あなたができるだけ少ないコードでは、このスタイルで迷路を解決するための最短経路を見つけるためのプログラムを書くことができます信じられないほど簡単な例はとても似ているのですか？

パスが迷路入力を超えているか、巨大な数の枝があるなど、すべての迷路入力に適用された場合のボーナスポイント。プログラムは大きな迷路（例えば、1024x1024 - 1 MB）で動作するはずです。迷路をプログラムに渡す方法は重要ではありません。

「プレーヤー」が斜めに動くことがあります。入力された迷路は決して対角線の通路を持たないので、動きの基本セットは上下左右になります。斜め方向の動きは、上/下と左/右がマージできるかどうかを判断するために少し先を見ているだけです。

出力は、アスタリスク文字（*）を使用して最短パスが強調表示されている迷路自体でなければなりません。

Answer 1

パイソン

387文字

は、標準入力から入力を受け取り。

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

CPUサイクルが最小の（固定サイズの）任意の迷路に対応しています（BFG2000が十分に大きい場合）。コンパイラが非常に効率的であるため、ソースサイズは無関係です。

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＃、非常に短くはない（空白ではない72行）が読みやすい。私は仕様を少し変更した。私は元の迷路が壁に完全に囲まれた長方形であると仮定し、私は異なる文字を使用します（私の目を傷つけることはありません）。私は1つだけのサンプル迷路を試した。 xとyの添え字をめくることを除いて、最初はうまくいったので、私はそれが正しいと思います（私が与えた1つのサンプルの解決策ではありません）。

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

が、それはある程度の成功に働いて得ることができたし、それが楽しい小さな挑戦だ（それは前のインタビュープログラミング挑戦だった）後、私は就職の面接のためにこの種のものをしました。